RPA method eval.

3 files changed, 179 insertions, 26 deletions

diff --git a/configuration_space.ipynb b/configuration_space.ipynb
index 0fa72c0..165201c 100644
--- a/configuration_space.ipynb
+++ b/configuration_space.ipynb
@@ -95,7 +95,17 @@
    "metadata": {},
    "outputs": [],
    "source": [
-    "print(total // (6*2*4*4*3*2))"
+    "no_indep = (6*2*4*4*3*2)\n",
+    "no_ff = (6*2)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "print(total // no_indep)"
    ]
   },
   {
@@ -138,7 +148,8 @@
    "metadata": {},
    "source": [
     "We see that when we fixed all parameters except for the scalar multiplier arguments \n",
-    "(see the `LTRMultiplier` constructor) we obtained 1120 configurations. That number expresses all of the possible ways to use addition formulas for the `projective` coordinate system in the binary left-to-right multiplier as well as internal options of that multiplier:\n",
+    "(see the `LTRMultiplier` constructor) we obtained 1280 configurations. That number expresses all of the possible ways to use addition formulas for the `projective` coordinate system in the binary left-to-right multiplier as well as internal options of that multiplier:\n",
+    "\n",
     " - whether it is \"complete\" in a sense that it starts processing at a constant bit (the bit-length od the order)\n",
     " - whether it is \"double-and-add-always\"\n",
     " - whether it \"short-circuits\" the formulas, i.e. detects that an exceptional point was input into them and returns correctly\n",
@@ -177,8 +188,8 @@
     "\tcount = sum(1 for _ in all_configurations(model=model, **independent_opts))\n",
     "\tcount_no_scl = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={\"scl\": None}))\n",
     "\tcount_no_opts = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={\"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
-    "\tmodel_counts.append([name, count * (6*2*4*4*3*2), count, count_no_scl, count_no_opts])\n",
-    "\ttotals[1] += count * (6*2*4*4*3*2)\n",
+    "\tmodel_counts.append([name, count * no_ff, count, count_no_scl, count_no_opts])\n",
+    "\ttotals[1] += count * no_ff\n",
     "\ttotals[2] += count\n",
     "\ttotals[3] += count_no_scl\n",
     "\ttotals[4] += count_no_opts\n",
@@ -215,7 +226,7 @@
     "\t\tcount = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts))\n",
     "\t\tcount_no_scl = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={\"scl\": None}))\n",
     "\t\tcount_no_opts = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={\"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
-    "\t\tcoords_counts.append([\"\", coords_name, count * (6*2*4*4*3*2), count, count_no_scl, count_no_opts])\n",
+    "\t\tcoords_counts.append([\"\", coords_name, count * no_ff, count, count_no_scl, count_no_opts])\n",
     "display(HTML(tabulate.tabulate(coords_counts, tablefmt=\"html\", headers=\"firstrow\")))"
    ]
   },
@@ -249,7 +260,7 @@
     "\tcount = sum(1 for _ in all_configurations(**independent_opts, scalarmult=mult_cls))\n",
     "\tcount_no_scl = sum(1 for _ in all_configurations(**independent_opts, scalarmult={\"cls\": mult_cls, \"scl\": None}))\n",
     "\tcount_no_opts = sum(1 for _ in all_configurations(**independent_opts, scalarmult={\"cls\": mult_cls, \"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
-    "\tmult_counts.append([mult_cls.__name__, count * (6*2*4*4*3*2), count, count_no_scl, count_no_opts])\n",
+    "\tmult_counts.append([mult_cls.__name__, count * no_ff, count, count_no_scl, count_no_opts])\n",
     "display(HTML(tabulate.tabulate(mult_counts, tablefmt=\"html\", headers=\"firstrow\")))\n"
    ]
   },
@@ -282,7 +293,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.11.5"
+   "version": "3.11.4"
   },
   "latex_envs": {
    "LaTeX_envs_menu_present": true,
diff --git a/re/rpa.ipynb b/re/rpa.ipynb
index 3a1f2d4..6690740 100644
--- a/re/rpa.ipynb
+++ b/re/rpa.ipynb
@@ -26,6 +26,7 @@
     "from collections import Counter\n",
     "from math import sqrt\n",
     "import numpy as np\n",
+    "import xarray as xr\n",
     "import holoviews as hv\n",
     "import matplotlib.pyplot as plt\n",
     "from scipy.signal import find_peaks\n",
@@ -46,9 +47,9 @@
     "from pyecsca.ec.point import Point\n",
     "from pyecsca.ec.mod import Mod\n",
     "from pyecsca.ec.mult import *\n",
-    "from pyecsca.misc.utils import silent\n",
+    "from pyecsca.misc.utils import silent, TaskExecutor\n",
     "from pyecsca.sca.trace.sampling import downsample_average, downsample_max\n",
-    "from pyecsca.sca.trace.process import normalize, rolling_mean\n",
+    "from pyecsca.sca.trace.process import normalize, rolling_mean, absolute\n",
     "from pyecsca.sca.trace.combine import average, subtract\n",
     "from pyecsca.sca.trace.test import welch_ttest\n",
     "from pyecsca.sca.attack.leakage_model import HammingWeight, NormalNoice\n",
@@ -631,22 +632,19 @@
     "    ctx.actions.walk(callback)\n",
     "    return Trace(np.array(trace))\n",
     "\n",
-    "def simulated_rpa_trace(mult, scalar, affine_point, noise):\n",
-    "    target_point = affine_point.to_model(params.curve.coordinate_model, params.curve)\n",
-    "    random_point = params.curve.affine_random().to_model(params.curve.coordinate_model, params.curve)\n",
-    "\n",
-    "    random_traces = [noise(simulate_trace(mult, scalar, random_point)) for _ in range(10)]\n",
-    "    target_traces = [noise(simulate_trace(mult, scalar, target_point)) for _ in range(500)]\n",
+    "def simulated_rpa_trace(mult, scalar, affine_point, noise, num_target=10, num_random=10):\n",
+    "    random_traces = [noise(normalize(simulate_trace(mult, scalar, params.curve.affine_random().to_model(params.curve.coordinate_model, params.curve, randomized=True)))) for _ in range(num_random)]\n",
+    "    target_traces = [noise(normalize(simulate_trace(mult, scalar, affine_point.to_model(params.curve.coordinate_model, params.curve, randomized=True)))) for _ in range(num_target)]\n",
     "\n",
     "    random_avg = average(*random_traces)\n",
     "    target_avg = average(*target_traces)\n",
     "\n",
-    "    diff_trace = downsample_max(subtract(random_avg, target_avg), 25)\n",
+    "    diff_trace = subtract(random_avg, target_avg)\n",
     "    return diff_trace\n",
     "\n",
-    "def simulated_rpa_oracle(scalar, affine_point, simulate_mult_id = 0):\n",
+    "def simulated_rpa_oracle(scalar, affine_point, simulate_mult_id = 0, variance=1):\n",
     "    real_mult = multipliers[simulate_mult_id]\n",
-    "    noise = NormalNoice(0, 1)\n",
+    "    noise = NormalNoice(0, variance)\n",
     "    diff_trace = normalize(simulated_rpa_trace(real_mult, scalar, affine_point, noise))\n",
     "    peaks, props = find_peaks(diff_trace.samples, height=4)\n",
     "    return len(peaks) != 0"
@@ -660,8 +658,7 @@
    "outputs": [],
    "source": [
     "table = [[\"True multiplier\", \"Reversed\", \"Correct\", \"Remaining\"]]\n",
-    "with TemporaryConfig() as cfg:\n",
-    "    cfg.log.enabled = False\n",
+    "with silent():\n",
     "    for i, mult in tqdm(enumerate(multipliers), total=len(multipliers)):\n",
     "        res = rpa_distinguish(params, multipliers, partial(simulated_rpa_oracle, simulate_mult_id = i))\n",
     "        table.append([mult, res, mult in res, len(res)])\n",
@@ -673,7 +670,7 @@
    "id": "e694b3b3-290d-4528-a611-16a183662944",
    "metadata": {},
    "source": [
-    "Note that the oracle function above has several parameters, like noise amplitude, amount of traces simulated, amount of downsampling and peak finding height threshold. The cell below compares the differential RPA trace when the multiple is computed in the simulation vs when it is not."
+    "Note that the oracle function above has several parameters, like noise standard deviation, amount of traces simulated, and peak finding height threshold. Below we analyze how these parameters influence the resulting error probabilities."
    ]
   },
   {
@@ -683,15 +680,123 @@
    "metadata": {},
    "outputs": [],
    "source": [
-    "diff_real = normalize(simulated_rpa_trace(multipliers[0], scalar, P0_target.to_affine(), NormalNoice(0, 1)))\n",
-    "diff_nothing = normalize(simulated_rpa_trace(multipliers[7], scalar, P0_target.to_affine(), NormalNoice(0, 1)))\n",
-    "plot_traces(diff_real, diff_nothing).opts(responsive=True, height=600)"
+    "def eval(threshold, sdev, tries, num_traces):\n",
+    "    noise = NormalNoice(0, sdev)\n",
+    "    aff = P0_target.to_affine()\n",
+    "    true_pos = 0\n",
+    "    false_pos = 0\n",
+    "    for _ in range(tries):\n",
+    "        diff_real = normalize(simulated_rpa_trace(multipliers[0], scalar, aff, noise, num_random=num_traces, num_target=num_traces))\n",
+    "        true_pos += len(find_peaks(diff_real.samples, height=threshold)[0]) > 0\n",
+    "        diff_nothing = normalize(simulated_rpa_trace(multipliers[7], scalar, aff, noise, num_random=num_traces, num_target=num_traces))\n",
+    "        false_pos += len(find_peaks(diff_nothing.samples, height=threshold)[0]) > 0\n",
+    "    false_neg = tries - true_pos\n",
+    "    true_neg = tries - false_pos\n",
+    "    return true_pos / tries, true_neg / tries, false_pos / tries, false_neg / tries\n",
+    "\n",
+    "threshold_range = [4]\n",
+    "sdev_range = list(range(0, 11))\n",
+    "traces_range = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]\n",
+    "e0 = xr.DataArray(np.zeros((len(threshold_range), len(sdev_range), len(traces_range))),\n",
+    "                  dims=(\"threshold\", \"sdev\", \"traces\"),\n",
+    "                  coords={\"threshold\": threshold_range, \"sdev\": sdev_range, \"traces\": traces_range}, name=\"e0\")\n",
+    "e1 = xr.DataArray(np.zeros((len(threshold_range), len(sdev_range), len(traces_range))),\n",
+    "                  dims=(\"threshold\", \"sdev\", \"traces\"),\n",
+    "                  coords={\"threshold\": threshold_range, \"sdev\": sdev_range, \"traces\": traces_range}, name=\"e1\")\n",
+    "tries = 200\n",
+    "with TaskExecutor(max_workers=30) as pool:\n",
+    "    for threshold in threshold_range:\n",
+    "        for sdev in sdev_range:\n",
+    "            for num_traces in traces_range:\n",
+    "                pool.submit_task((threshold, sdev, num_traces),\n",
+    "                                 eval, threshold, sdev, tries, num_traces)\n",
+    "    for (threshold, sdev, num_traces), future in tqdm(pool.as_completed(), total=len(pool.tasks), smoothing=0):\n",
+    "        true_pos, true_neg, false_pos, false_neg = future.result()\n",
+    "        e0.loc[threshold, sdev, num_traces] = false_pos\n",
+    "        e1.loc[threshold, sdev, num_traces] = false_neg"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "0b915148-4b0d-4c8d-a904-6b6ae85fafd8",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "fig, axs = plt.subplots(ncols=2, figsize=(10, 4), sharey=\"row\")\n",
+    "for i, threshold in enumerate(threshold_range):\n",
+    "    res0 = e0.sel(threshold=threshold).plot(ax=axs[0], vmin=0, vmax=1, cmap=\"plasma\", add_colorbar=False)\n",
+    "    for j, sdev in enumerate(sdev_range):\n",
+    "        for k, traces in enumerate(traces_range):\n",
+    "            val = e0.sel(threshold=threshold, sdev=sdev, traces=traces)\n",
+    "            sval = f\"{val:.2f}\"\n",
+    "            color=\"white\" if val < 0.5 else \"black\"\n",
+    "            if sval == \"0.00\":\n",
+    "                color=\"grey\"\n",
+    "            axs[0].text(traces, sdev, sval.lstrip(\"0\"), ha=\"center\", va=\"center\", color=color)\n",
+    "    axs[0].set_title(\"$e_0$\")\n",
+    "    axs[0].set_ylabel(\"noise $\\sigma$\")\n",
+    "    axs[0].set_xlabel(\"traces per group\")\n",
+    "    res1 = e1.sel(threshold=threshold).plot(ax=axs[1], vmin=0, vmax=1, cmap=\"plasma\", add_colorbar=False)\n",
+    "    for j, sdev in enumerate(sdev_ramge):\n",
+    "        for k, traces in enumerate(traces_range):\n",
+    "            val = e1.sel(threshold=threshold, sdev=sdev, traces=traces)\n",
+    "            sval = f\"{val:.2f}\"\n",
+    "            color=\"white\" if val < 0.5 else \"black\"\n",
+    "            if sval == \"0.00\":\n",
+    "                color=\"grey\"\n",
+    "            axs[1].text(traces, sdev, sval.lstrip(\"0\"), ha=\"center\", va=\"center\", color=color)\n",
+    "    axs[1].set_title(\"$e_1$\")\n",
+    "    axs[1].set_ylabel(\"noise $\\sigma$\")\n",
+    "    axs[1].set_xlabel(\"traces per group\")\n",
+    "    fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))\n",
+    "    cbar_ymin, cbar_ymax = axs[0].get_position().ymin, axs[0].get_position().ymax\n",
+    "    cbar_ax = fig.add_axes((0.92, 0.145, 0.02, 0.77))\n",
+    "    cbar = fig.colorbar(res0, cax=cbar_ax, label=\"error probability\")\n",
+    "    cbar.ax.yaxis.set_label_coords(2.8, 0.5);\n",
+    "    cbar.ax.set_ylabel(\"error probability\", rotation=-90, va=\"bottom\")"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "989bcd51-888a-4a7a-bbfe-2eea4fee7adc",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "fig.savefig(\"rpa_re_errors.pdf\", bbox_inches=\"tight\")"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "381fd20b-8218-4935-97a8-800c9a9c7092",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "fig, axs = plt.subplots(ncols=len(traces_range), nrows=len(var_range), figsize=(10, 12), sharex=\"col\", sharey=\"row\")\n",
+    "for i, traces in enumerate(traces_range):\n",
+    "    for j, var in enumerate(var_range):\n",
+    "        (e0.sel(traces=traces, var=var) + e1.sel(traces=traces, var=var)).plot(ax=axs[j,i], label=\"e0\")\n",
+    "        axs[j, i].set_ylabel(\"error\")\n",
+    "        axs[j,i].set_ylim((0, 1))\n",
+    "fig.tight_layout()"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "0aa654bd-c09b-45a5-81c5-6bb53393ce67",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "fig.savefig(\"rpa_re_errors_all.pdf\", bbox_inches=\"tight\")"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "7d974e88-77fb-4331-9477-25e6d18dc6ba",
+   "id": "1f809503-d572-4051-9731-a8a7d16ede33",
    "metadata": {},
    "outputs": [],
    "source": []
diff --git a/re/zvp.ipynb b/re/zvp.ipynb
index 9d90371..e5e4b3d 100644
--- a/re/zvp.ipynb
+++ b/re/zvp.ipynb
@@ -41,6 +41,7 @@
     "import tempfile\n",
     "import sys\n",
     "import re\n",
+    "from collections import Counter\n",
     "from matplotlib import pyplot as plt\n",
     "from sympy import FF, ZZ, sympify, symbols, Poly\n",
     "from contextlib import contextmanager\n",
@@ -50,7 +51,7 @@
     "from itertools import product\n",
     "from IPython.display import HTML, display\n",
     "from tqdm.notebook import tqdm, trange\n",
-    "from anytree import RenderTree, PreOrderIter\n",
+    "from anytree import RenderTree, LevelOrderIter\n",
     "\n",
     "\n",
     "from pyecsca.ec.model import ShortWeierstrassModel\n",
@@ -1407,6 +1408,42 @@
    "cell_type": "code",
    "execution_count": null,
    "id": "af01658f-6c95-483c-9d8d-ce6f34566cee",
+   "metadata": {
+    "scrolled": true
+   },
+   "outputs": [],
+   "source": [
+    "tree_counter = Counter()\n",
+    "for node in LevelOrderIter(tree_count.root):\n",
+    "    if isinstance(node.response, int):\n",
+    "        tree_counter[node.response] += 1\n",
+    "    if node.children:\n",
+    "        print(list(map(lambda n: n.response, node.children)))\n",
+    "fig, ax = plt.subplots(figsize=(10, 3))\n",
+    "ax.bar(tree_counter.keys(), tree_counter.values(), width=1);"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "cc814452-04d8-4285-8df9-496c96e668e7",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "dmap_counter = Counter()\n",
+    "for col in dmap_count.mapping:\n",
+    "    dmap_counter.update(dmap_count.mapping[col])\n",
+    "\n",
+    "del dmap_counter[-1]\n",
+    "del dmap_counter[0]\n",
+    "fig, ax = plt.subplots(figsize=(10, 3))\n",
+    "ax.bar(dmap_counter.keys(), dmap_counter.values(), width=1);"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "892e02c7-8c39-4467-91ff-b6ae265684aa",
    "metadata": {},
    "outputs": [],
    "source": []