Polish RPA-RE.

1 files changed, 73 insertions, 36 deletions

diff --git a/re/rpa.ipynb b/re/rpa.ipynb
index e153634..5bfbdd6 100644
--- a/re/rpa.ipynb
+++ b/re/rpa.ipynb
@@ -20,7 +20,7 @@
     "import holoviews as hv\n",
     "import matplotlib.pyplot as plt\n",
     "from scipy.signal import find_peaks\n",
-    "from functools import partial\n",
+    "from functools import partial, lru_cache\n",
     "from scipy.stats import bernoulli\n",
     "from concurrent.futures import ProcessPoolExecutor, as_completed\n",
     "\n",
@@ -31,7 +31,7 @@
     "from pyecsca.ec.model import ShortWeierstrassModel\n",
     "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
     "from pyecsca.ec.curve import EllipticCurve\n",
-    "from pyecsca.ec.params import DomainParameters\n",
+    "from pyecsca.ec.params import DomainParameters, get_params\n",
     "from pyecsca.ec.formula import FormulaAction\n",
     "from pyecsca.ec.point import Point\n",
     "from pyecsca.ec.mod import Mod\n",
@@ -117,16 +117,21 @@
     "    BinaryNAFMultiplier(add, dbl, neg, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
     "    WindowNAFMultiplier(add, dbl, neg, 3, None, AccumulationOrder.PeqPR, True, True),\n",
     "    WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, True, True),\n",
-    "    #WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, False, True),\n",
+    "    WindowNAFMultiplier(add, dbl, neg, 5, None, AccumulationOrder.PeqPR, True, True),\n",
+    "    #WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, False, True),  # Same set of multiples as Window NAF with precompute_negation\n",
     "    SlidingWindowMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
+    "    SlidingWindowMultiplier(add, dbl, 4, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
     "    SlidingWindowMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
     "    FixedWindowLTRMultiplier(add, dbl, 4, None, AccumulationOrder.PeqPR, True),\n",
     "    FixedWindowLTRMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True),\n",
+    "    FixedWindowLTRMultiplier(add, dbl, 8, None, AccumulationOrder.PeqPR, True),\n",
     "    FullPrecompMultiplier(add, dbl, None, True, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True),\n",
     "    FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True),\n",
-    "    #FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.RTL, AccumulationOrder.PeqPR, True, True),\n",
+    "    #FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.RTL, AccumulationOrder.PeqPR, True, True),  # Same set of multiples as RTL multiplier\n",
+    "    BGMWMultiplier(add, dbl, 2, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
     "    BGMWMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
     "    BGMWMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),\n",
+    "    CombMultiplier(add, dbl, 2, None, AccumulationOrder.PeqPR, True),\n",
     "    CombMultiplier(add, dbl, 3, None, AccumulationOrder.PeqPR, True),\n",
     "    CombMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True)\n",
     "]"
@@ -212,9 +217,7 @@
    "cell_type": "code",
    "execution_count": null,
    "id": "8113cb3f-dc06-4cb7-955c-11cedb4fbdd7",
-   "metadata": {
-    "scrolled": true
-   },
+   "metadata": {},
    "outputs": [],
    "source": [
     "table = [[\"Multiplier\", \"zero present\", \"multiple computed\"]]\n",
@@ -250,7 +253,6 @@
     "table = [[\"Multiple\", \"Multipliers\"]]\n",
     "for multiple, mults in multiples.items():\n",
     "    table.append([bin(multiple), [mult.__class__.__name__ for mult in mults]])\n",
-    "    #print(multiple, [mult.__class__.__name__ for mult in mults])\n",
     "\n",
     "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
    ]
@@ -272,7 +274,7 @@
     "\n",
     "### Oracle simulation\n",
     "The `simulated_oracle` function simulates an RPA oracle that detect a zero coordinate point in the scalar multiplication.\n",
-    "This can be used by the `rpa_distinguish` function to distinguish the true scalar multiplier. The oracle is parametrized with the simulated multiplier index in the table of multipliers (it simulates this \"real\" multiplier) and its error (flip) probability."
+    "This can be used by the `rpa_distinguish` function to distinguish the true scalar multiplier. The oracle is parametrized with the simulated multiplier index in the table of multipliers (it simulates this \"real\" multiplier). Furthermore, lets also examine a `noisy_oracle` (with a flip probability) and a `biased_oracle` (with asymmetric flip probability)."
    ]
   },
   {
@@ -282,15 +284,28 @@
    "metadata": {},
    "outputs": [],
    "source": [
-    "def simulated_oracle(scalar, affine_point, simulate_mult_id=0, flip_proba=0):\n",
+    "def simulated_oracle(scalar, affine_point, simulate_mult_id=0):\n",
     "    real_mult = multipliers[simulate_mult_id]\n",
-    "    point = affine_point.to_model(params.curve.coordinate_model, params.curve)\n",
+    "    point = affine_point.to_model(p256.curve.coordinate_model, p256.curve)\n",
     "    with local(MultipleContext()) as ctx:\n",
-    "        real_mult.init(params, point)\n",
+    "        real_mult.init(p256, point)\n",
     "        real_mult.multiply(scalar)\n",
     "    real_result = any(map(lambda P: P.X == 0 or P.Y == 0, ctx.points.keys()))\n",
-    "    change = bernoulli(flip_proba).rvs()\n",
-    "    return bool(real_result ^ change)"
+    "    return real_result\n",
+    "\n",
+    "def noisy_oracle(oracle, flip_proba=0):\n",
+    "    def noisy(*args, **kwargs):\n",
+    "        real_result = oracle(*args, **kwargs)\n",
+    "        change = bernoulli(flip_proba).rvs()\n",
+    "        return bool(real_result ^ change)\n",
+    "    return noisy\n",
+    "\n",
+    "def biased_oracle(oracle, flip_0=0, flip_1=0):\n",
+    "    def biased(*args, **kwargs):\n",
+    "        real_result = oracle(*args, **kwargs)\n",
+    "        change = bernoulli(flip_1).rvs() if real_result else bernoulli(flip_0).rvs()\n",
+    "        return bool(real_result ^ change)\n",
+    "    return biased"
    ]
   },
   {
@@ -308,7 +323,8 @@
    "metadata": {},
    "outputs": [],
    "source": [
-    "res = rpa_distinguish(params, multipliers, simulated_oracle)"
+    "p256 = get_params(\"secg\", \"secp256r1\", \"projective\")\n",
+    "res = rpa_distinguish(p256, multipliers, simulated_oracle)"
    ]
   },
   {
@@ -322,24 +338,39 @@
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "265eb13a-6028-4fde-9c3f-cc23768ba63e",
+   "id": "4e9ca09b-9fe4-4c91-ac37-530892b1df48",
    "metadata": {},
    "outputs": [],
    "source": [
     "errs = (0, 0.1, 0.2, 0.3, 0.4, 0.5)\n",
-    "majs = (1, 3, 5, 7)\n",
-    "num_tries = 100\n",
-    "num_cores = 4\n",
+    "majs = (1, 3, 5, 7, 9, 11)\n",
+    "correct_tries = np.zeros((len(errs), len(majs)))\n",
+    "precise_tries = np.zeros((len(errs), len(majs)))\n",
+    "query_tries = np.zeros((len(errs), len(majs)))\n",
+    "total_tries = 0\n",
+    "\n",
+    "num_tries = 50"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "265eb13a-6028-4fde-9c3f-cc23768ba63e",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "num_cores = 30\n",
     "\n",
     "def measure_mult(params, multipliers, simulated_oracle, i, mult, err, majority):\n",
     "    correct = 0\n",
     "    precise = 0\n",
     "    calls = 0\n",
-    "    p = partial(simulated_oracle, simulate_mult_id=i, flip_proba=err)\n",
+    "    p = lru_cache(maxsize=2)(partial(simulated_oracle, simulate_mult_id=i))\n",
+    "    noisy = noisy_oracle(p, flip_proba=err)\n",
     "    def oracle(scalar, affine_point):\n",
     "        nonlocal calls\n",
     "        calls += 1\n",
-    "        return p(scalar, affine_point)\n",
+    "        return noisy(scalar, affine_point)\n",
     "    for j in range(num_tries):\n",
     "        res = rpa_distinguish(params, multipliers, oracle, majority=majority)\n",
     "        if mult in res:\n",
@@ -371,9 +402,7 @@
    "id": "4d283a04-decc-422f-b804-addd57a8a635",
    "metadata": {},
    "source": [
-    "Now we accumulate the results across the error rate and majority vote parameters and plot two heatmaps:\n",
-    " - One for the average number of queries to the oracle.\n",
-    " - One for the success rate of the distinguisher."
+    "Now we accumulate the results across the error rate and majority vote parameters."
    ]
   },
   {
@@ -383,19 +412,27 @@
    "metadata": {},
    "outputs": [],
    "source": [
-    "correct_rate = np.zeros((len(errs), len(majs)))\n",
-    "precise_rate = np.zeros((len(errs), len(majs)))\n",
-    "query_rate = np.zeros((len(errs), len(majs)))\n",
     "for a, result in zip(args, results):\n",
     "    i = errs.index(a[5])\n",
     "    j = len(majs) - majs.index(a[6]) - 1\n",
-    "    correct_rate[i, j] += result[0]\n",
-    "    precise_rate[i, j] += result[1]\n",
-    "    query_rate[i, j] += result[2]\n",
+    "    correct_tries[i, j] += result[0]\n",
+    "    precise_tries[i, j] += result[1]\n",
+    "    query_tries[i, j] += result[2]\n",
+    "total_tries += num_tries\n",
     "\n",
-    "correct_rate = (correct_rate * 100) / (num_tries * len(multipliers))\n",
-    "precise_rate = (precise_rate * 100) / (num_tries * len(multipliers))\n",
-    "query_rate = query_rate / (num_tries * len(multipliers))"
+    "correct_rate = (correct_tries * 100) / (total_tries * len(multipliers))\n",
+    "precise_rate = (precise_tries * 100) / (total_tries * len(multipliers))\n",
+    "query_rate = query_tries / (total_tries * len(multipliers))"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "id": "9bda1baa-359a-4f9b-889d-f64e055deff6",
+   "metadata": {},
+   "source": [
+    "We can plot two heatmaps:\n",
+    " - One for the average number of queries to the oracle.\n",
+    " - One for the success rate of the distinguisher."
    ]
   },
   {
@@ -406,8 +443,8 @@
    "outputs": [],
    "source": [
     "fig, ax = plt.subplots()\n",
-    "im = ax.imshow(query_rate.T, vmin=0, cmap=\"plasma\")\n",
-    "cbar_ax = fig.add_axes((0.97, 0.15, 0.04, 0.69))\n",
+    "im = ax.imshow(query_rate.T, cmap=\"plasma\")\n",
+    "cbar_ax = fig.add_axes((0.90, 0.15, 0.04, 0.69))\n",
     "cbar = fig.colorbar(im, cax=cbar_ax)\n",
     "cbar.ax.set_ylabel(\"Average oracle query rate\", rotation=-90, va=\"bottom\")\n",
     "\n",
@@ -432,7 +469,7 @@
    "source": [
     "fig, ax = plt.subplots()\n",
     "im = ax.imshow(correct_rate.T, vmin=0, cmap=\"viridis\")\n",
-    "cbar_ax = fig.add_axes((0.97, 0.15, 0.04, 0.69))\n",
+    "cbar_ax = fig.add_axes((0.90, 0.15, 0.04, 0.69))\n",
     "cbar = fig.colorbar(im, cax=cbar_ax)\n",
     "cbar.ax.set_ylabel(\"Success rate\", rotation=-90, va=\"bottom\")\n",
     "cbar.ax.axhline(100 / len(multipliers), color=\"red\", linestyle=\"--\")\n",