aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorJ08nY2024-07-24 17:30:43 +0200
committerJ08nY2024-07-24 17:30:43 +0200
commit24d1ba404d7b0e0ebcb9b8e64fb797ca66cb6f48 (patch)
treed9b37c8ea3755a2523d7db69faf92ffe608d7386
parent810c9cfd4cdbded82e3ed20ac9961e287c6af856 (diff)
downloadpyecsca-notebook-24d1ba404d7b0e0ebcb9b8e64fb797ca66cb6f48.tar.gz
pyecsca-notebook-24d1ba404d7b0e0ebcb9b8e64fb797ca66cb6f48.tar.zst
pyecsca-notebook-24d1ba404d7b0e0ebcb9b8e64fb797ca66cb6f48.zip
Cleanup notebooks for artifact.
Diffstat
-rw-r--r--configuration_space.ipynb86
-rw-r--r--re/formulas.ipynb170
-rw-r--r--re/rpa.ipynb257
-rw-r--r--re/zvp.ipynb486
4 files changed, 538 insertions, 461 deletions
diff --git a/configuration_space.ipynb b/configuration_space.ipynb
index 165201c..cc5e636 100644
--- a/configuration_space.ipynb
+++ b/configuration_space.ipynb
@@ -18,9 +18,7 @@
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"from typing import get_args\n",
"from pyecsca.ec.configuration import Configuration\n",
@@ -33,19 +31,19 @@
"\tif get_args(field.type):\n",
"\t\tdoc = get_args(field.type)[0].__doc__\n",
"\tprint(name, tp)\n",
- "\tprint(\" \", doc)\n",
+ "\tprint(\" \", doc.strip().split(\"\\n\")[0])\n",
"\tif hasattr(tp, \"names\"):\n",
"\t\tfor enum_name in tp.names():\n",
"\t\t\tprint(\" \", enum_name)\n",
"\tprint()"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"metadata": {},
- "source": [
- "It is represented by the `Configuration` class."
- ]
+ "source": "It is represented by the [`Configuration`](api/pyecsca.ec.configuration.rst#pyecsca.ec.configuration.Configuration) class."
},
{
"cell_type": "markdown",
@@ -53,25 +51,29 @@
"source": [
"## Enumerating configurations\n",
"\n",
- "The possible configurations can be generated using the `all_configurations()` function.\n",
+ "The possible configurations can be generated using the [`all_configurations()`](api/pyecsca.ec.configuration.html#pyecsca.ec.configuration.all_configurations) function.\n",
"The whole space of configurations is quite huge.\n",
"\n",
- "> Note that the amount of possible parametrizations of some scalar multipliers is very large (e.g. window size) so **pyecsca** has\n",
- "> to resctrict this to a reasonable selection. Specifically the function below only considers a few options for window size and\n",
- "> similar parameters."
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "Note that the amount of possible parametrizations of some scalar multipliers is very large (e.g. window size) so **pyecsca** has\n",
+ "to restrict this to a reasonable selection. Specifically the function below only considers a few options for window size and\n",
+ "similar parameters. **Even then, the cell below takes roughly 10 minutes to run.**\n",
+ "\n",
+ "</div>"
]
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"from pyecsca.ec.configuration import all_configurations\n",
"\n",
"total = sum(1 for _ in all_configurations())\n",
"print(total)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -91,22 +93,23 @@
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
- "no_indep = (6*2*4*4*3*2)\n",
- "no_ff = (6*2)"
- ]
+ "no_hash_and_rand = (4*4*3*2)\n",
+ "no_ff = (6*2)\n",
+ "no_indep = no_ff * no_hash_and_rand"
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"print(total // no_indep)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -118,9 +121,7 @@
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"from pyecsca.ec.configuration import HashType, RandomMod, Multiplication, Squaring, Reduction, Inversion\n",
"from pyecsca.ec.model import ShortWeierstrassModel\n",
@@ -141,14 +142,16 @@
"configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult,\n",
"\t\t\t\t\t\t\t \t **independent_opts))\n",
"print(len(configs))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that when we fixed all parameters except for the scalar multiplier arguments \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",
+ "(see the [`LTRMultiplier`](api/pyecsca.ec.mult.binary.html#pyecsca.ec.mult.binary.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",
@@ -172,9 +175,7 @@
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"from IPython.display import HTML, display\n",
"import tabulate\n",
@@ -195,7 +196,9 @@
"\ttotals[4] += count_no_opts\n",
"model_counts.append(totals)\n",
"display(HTML(tabulate.tabulate(model_counts, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -213,9 +216,7 @@
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"coords_counts = [[\"Model\", \"Coords\", \"All\", \"Without independent options\", \"Without independent options and scaling\", \"Without independent options and scalarmult options\"]]\n",
"for model in (ShortWeierstrassModel(), MontgomeryModel(), EdwardsModel(), TwistedEdwardsModel()):\n",
@@ -228,20 +229,23 @@
"\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 * no_ff, count, count_no_scl, count_no_opts])\n",
"display(HTML(tabulate.tabulate(coords_counts, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"metadata": {},
- "source": [
- "### Scalar multipliers"
- ]
+ "source": "### Scalar multipliers"
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Let's examine the split between different scalar multipliers."
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
- "outputs": [],
"source": [
"from pyecsca.ec.mult import ScalarMultiplier\n",
"\n",
@@ -262,14 +266,16 @@
"\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 * no_ff, count, count_no_scl, count_no_opts])\n",
"display(HTML(tabulate.tabulate(mult_counts, tablefmt=\"html\", headers=\"firstrow\")))\n"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"metadata": {},
+ "source": [],
"outputs": [],
- "source": []
+ "execution_count": null
}
],
"metadata": {
diff --git a/re/formulas.ipynb b/re/formulas.ipynb
index 20263a0..39e1cfc 100644
--- a/re/formulas.ipynb
+++ b/re/formulas.ipynb
@@ -5,19 +5,21 @@
"id": "0577f61d-635c-436c-96ca-1471265ac1fb",
"metadata": {},
"source": [
- "# Exploration of formulas in open-source ECC libraries"
+ "# Exploration of formulas in open-source ECC libraries\n",
+ "\n",
+ "This notebook explores formulas found in open-source ECC libraries.\n",
+ "\n",
+ " - [Analysis](#Analysis)\n",
+ " - [Formulas](#The-formulas)\n",
+ " - [Expand](#Expand) "
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "397771ed-7408-47a6-8b82-75e047e100fe",
"metadata": {},
- "outputs": [],
"source": [
"import itertools\n",
- "import tabulate\n",
- "import pickle\n",
"import numpy as np\n",
"import inspect\n",
"import tempfile\n",
@@ -31,17 +33,14 @@
"from pathlib import Path\n",
"\n",
"from matplotlib import pyplot as plt\n",
- "from IPython.display import HTML, display\n",
"from tqdm.notebook import tqdm\n",
- "from importlib_resources import files, as_file\n",
+ "from importlib_resources import files\n",
"\n",
- "import pyecsca\n",
+ "import pyecsca.ec\n",
"from pyecsca.ec.model import ShortWeierstrassModel, TwistedEdwardsModel, MontgomeryModel\n",
"from pyecsca.ec.formula import AdditionEFDFormula, DoublingEFDFormula, LadderEFDFormula\n",
"from pyecsca.ec.params import get_params\n",
"from pyecsca.ec.formula.metrics import formula_similarity, formula_similarity_fuzz\n",
- "from pyecsca.ec.formula.unroll import unroll_formula_expr, unroll_formula\n",
- "from pyecsca.ec.formula.expand import expand_formula_set\n",
"\n",
"\n",
"# Allow to use \"spawn\" multiprocessing method for function defined in a Jupyter notebook.\n",
@@ -59,14 +58,14 @@
" module = import_module(str(path.stem))\n",
" yield getattr(module, func.__name__)\n",
" sys.path.remove(directory)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "1727bd9a-f209-4d91-9286-8cca9118c187",
"metadata": {},
- "outputs": [],
"source": [
"sw = ShortWeierstrassModel()\n",
"mont = MontgomeryModel()\n",
@@ -78,7 +77,9 @@
"p256_jac = get_params(\"secg\", \"secp256r1\", \"jacobian\")\n",
"p256_mod = get_params(\"secg\", \"secp256r1\", \"modified\")\n",
"p256_proj3 = get_params(\"secg\", \"secp256r1\", \"projective-3\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -86,15 +87,13 @@
"metadata": {},
"source": [
"## The formulas\n",
- "The following formulas were collected from open-source cryptographic libraries and are stored in the tests directory of the pyecsca toolkit."
+ "The following formulas were collected from open-source cryptographic libraries and are stored in the core package of the **pyecsca** toolkit. For a full overview of implementation choices done by open-source ECC libraries, see [this page](libraries.html)."
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "21572b7d-380c-4570-b5bd-2043306adc3e",
"metadata": {},
- "outputs": [],
"source": [
"lib_formula_defs = [\n",
" [\n",
@@ -315,7 +314,9 @@
" LadderEFDFormula,\n",
" ],\n",
"]"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -327,45 +328,46 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "0cfcbf60-7d6b-4ab0-b957-e998037ff8ab",
"metadata": {},
- "outputs": [],
"source": [
"lib_formulas = {}\n",
- "base_path = files(pyecsca).joinpath(\"../test/data/formulas/\")\n",
+ "base_path = files(pyecsca.ec).joinpath(\"data\", \"formulas\")\n",
"for formula_def in lib_formula_defs:\n",
" meta_path = base_path / formula_def[0]\n",
" op3_path = base_path / (formula_def[0] + \".op3\")\n",
" model = formula_def[1]()\n",
" formula = formula_def[4](meta_path, op3_path, formula_def[0], model.coordinates[formula_def[2]]).to_code()\n",
" lib_formulas[formula_def[0]] = formula"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "74002746-f3f3-4528-9042-b9ab51791bc2",
"metadata": {},
- "outputs": [],
"source": [
"len(lib_formulas)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"id": "5800e043-85bc-4fac-8c40-75c234beec1c",
"metadata": {},
"source": [
- "Now we can setup some code for examining the similarities between the formulas."
+ "Now we can set up some code for examining the similarities between the formulas. This is done in two ways:\n",
+ "\n",
+ " - Measure similarity between sets of intermediate polynomials of the formulas (like in the **pyecsca** paper),\n",
+ " - Measure similarity between sets of intermediate values of the formulas over random points on some curve (the *fuzz* approach)."
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "e0a91c61-1565-49bd-9604-5a371710f91a",
"metadata": {},
- "outputs": [],
"source": [
"def compute_similarities(formulas, curve):\n",
" table = [[\"One\", \"Other\", \"Similarity (output)\", \"Similarity (IV)\"]]\n",
@@ -377,7 +379,7 @@
" for assumption_str in formula.assumptions_str:\n",
" lhs, rhs = assumption_str.strip().split(\" == \")\n",
" if lhs in formula.inputs:\n",
- " print(f\"Warning, formula {formula.name} has assumptions: {assumption_str}\")\n",
+ " print(f\"Warning, formula {formula.name} has assumptions: {assumption_str}\")\n",
" for one, other in itertools.product(formulas, formulas):\n",
" i = formulas.index(one)\n",
" j = formulas.index(other)\n",
@@ -410,49 +412,51 @@
" table, im_iv, im_out = compute_similarities(formulas, curve)\n",
" plot_similarities(formulas, im_iv, \"IV\")\n",
" plot_similarities(formulas, im_out, \"output\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"id": "392d7eea-abcb-4d83-82b4-a9394d3d44aa",
"metadata": {},
"source": [
- "## Analysis"
+ "## Analysis\n",
+ "\n",
+ "Let's now go through the library formulas grouped by their type and coordinate model."
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "932e8ec8-77f6-4079-909c-3ca021fde717",
"metadata": {},
- "outputs": [],
"source": [
"xz_ladders = [formula for formula in mont.coordinates[\"xz\"].formulas.values() if formula.name.startswith(\"ladd\") or formula.name.startswith(\"mladd\")] + [\n",
" lib_formulas[\"ladd-rfc7748\"], lib_formulas[\"ladd-hacl-x25519\"], lib_formulas[\"ladd-openssl-x25519\"], lib_formulas[\"ladd-bc-r1rv76-x25519\"],\n",
" lib_formulas[\"ladd-go-1214\"], lib_formulas[\"ladd-boringssl-x25519\"], lib_formulas[\"ladd-botan-x25519\"]]\n",
"analyze_formulas(xz_ladders)\n",
"analyze_formulas(xz_ladders, curve25519.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "f2e0e3b5-b7e8-4ed7-94a1-a74976b108fa",
"metadata": {},
- "outputs": [],
"source": [
"xz_dbls = [formula for formula in mont.coordinates[\"xz\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-bc-r1rv76-x25519\"], lib_formulas[\"dbl-hacl-x25519\"], lib_formulas[\"dbl-ipp-x25519\"]]\n",
"analyze_formulas(xz_dbls)\n",
"analyze_formulas(xz_dbls, curve25519.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "724791a0-4137-4d3e-abaa-a90e4e2187ec",
"metadata": {},
- "outputs": [],
"source": [
"jac3_adds = [formula for formula in sw.coordinates[\"jacobian-3\"].formulas.values() if formula.name.startswith(\"add\") or formula.name.startswith(\"madd\")] + [\n",
" lib_formulas[\"add-boringssl-p224\"], lib_formulas[\"add-openssl-z256\"], lib_formulas[\"add-openssl-z256a\"],\n",
@@ -465,14 +469,14 @@
" jac3_adds_fixed.append(formula)\n",
"analyze_formulas(jac3_adds_fixed)\n",
"analyze_formulas(jac3_adds_fixed, p256_jac3.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d12b98bc-71b5-4800-8762-ca87eb02d050",
"metadata": {},
- "outputs": [],
"source": [
"jac3_dbls = [formula for formula in sw.coordinates[\"jacobian-3\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-boringssl-p224\"], lib_formulas[\"dbl-gecc-321\"]]\n",
@@ -484,109 +488,111 @@
" jac3_dbls_fixed.append(formula)\n",
"analyze_formulas(jac3_dbls_fixed)\n",
"analyze_formulas(jac3_dbls_fixed, p256_jac3.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "ae0cde46-061c-48f1-9fb6-67a2798c5068",
"metadata": {},
- "outputs": [],
"source": [
"mod_adds = [formula for formula in sw.coordinates[\"modified\"].formulas.values() if formula.name.startswith(\"add\") or formula.name.startswith(\"madd\")] + [\n",
" lib_formulas[\"add-bc-r1rv76-mod\"]]\n",
"analyze_formulas(mod_adds)\n",
"analyze_formulas(mod_adds, p256_mod.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "c7226513-9866-405f-9f4e-ad83134b957a",
"metadata": {},
- "outputs": [],
"source": [
"mod_dbls = [formula for formula in sw.coordinates[\"modified\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-bc-r1rv76-mod\"]]\n",
"analyze_formulas(mod_dbls)\n",
"analyze_formulas(mod_dbls, p256_mod.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "313570ca-082e-46df-8420-ed47dc78855b",
"metadata": {},
- "outputs": [],
"source": [
"jac_adds = [formula for formula in sw.coordinates[\"jacobian\"].formulas.values() if formula.name.startswith(\"add\")] + [\n",
" lib_formulas[\"add-bc-r1rv76-jac\"], lib_formulas[\"add-libressl-v382\"], lib_formulas[\"add-bearssl-v06\"], lib_formulas[\"add-libgcrypt-v1102\"]]\n",
"analyze_formulas(jac_adds)\n",
"analyze_formulas(jac_adds, p256_jac.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "9a0e3899-872d-411b-8778-362e464390df",
"metadata": {},
- "outputs": [],
"source": [
"jac_dbls = [formula for formula in sw.coordinates[\"jacobian\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-secp256k1-v040\"], lib_formulas[\"dbl-libressl-v382\"], lib_formulas[\"dbl-bearssl-v06\"], lib_formulas[\"dbl-libgcrypt-v1102\"]]\n",
"analyze_formulas(jac_dbls)\n",
"analyze_formulas(jac_dbls, p256_jac.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "881c383e-3062-4f1e-98e3-adc336749a20",
"metadata": {},
- "outputs": [],
"source": [
"proj3_adds = [formula for formula in sw.coordinates[\"projective-3\"].formulas.values() if formula.name.startswith(\"add\") or formula.name.startswith(\"madd\")] + [\n",
" lib_formulas[\"add-sunec-v21\"]]\n",
"analyze_formulas(proj3_adds)\n",
"analyze_formulas(proj3_adds, p256_proj3.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d34e20a4-bf1b-4245-bbb2-a53fdd3446a3",
"metadata": {},
- "outputs": [],
"source": [
"proj3_dbls = [formula for formula in sw.coordinates[\"projective-3\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-sunec-v21\"]]\n",
"analyze_formulas(proj3_dbls)\n",
"analyze_formulas(proj3_dbls, p256_proj3.curve)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "78f7ff19-9f97-4459-b31e-0d7efe3b7dfa",
"metadata": {},
- "outputs": [],
"source": [
"ext_adds = [formula for formula in te.coordinates[\"extended-1\"].formulas.values() if formula.name.startswith(\"add\") or formula.name.startswith(\"madd\")] + [\n",
" lib_formulas[\"add-sunec-v21-ed25519\"]]\n",
"analyze_formulas(ext_adds)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "fb60bd5f-47a6-4a8f-9864-66bc750bfe97",
"metadata": {},
- "outputs": [],
"source": [
"ext_dbls = [formula for formula in te.coordinates[\"extended-1\"].formulas.values() if formula.name.startswith(\"dbl\")] + [\n",
" lib_formulas[\"dbl-sunec-v21-ed25519\"]]\n",
"analyze_formulas(ext_dbls)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -596,15 +602,28 @@
"## Expand\n",
"We can also expand the set of formulas by applying various transformations (like swapping the order of commutative operations).\n",
"\n",
- "Note that this computation is parallelized and you should set an appropriate number of workers."
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Set the `num_workers` variable to something reasonable, like the number of cores of your machine minus two.\n",
+ "\n",
+ "</div>"
]
},
{
+ "metadata": {},
+ "cell_type": "code",
+ "source": [
+ "# 22 is really a maximum usable number here, as there are only 22 \"jobs\".\n",
+ "num_workers = 22"
+ ],
+ "id": "6cc916235ef2e061",
+ "outputs": [],
+ "execution_count": null
+ },
+ {
"cell_type": "code",
- "execution_count": null,
"id": "f3c2c134-a42d-4bb2-b729-0ec1ddcbcdef",
"metadata": {},
- "outputs": [],
"source": [
"def expand_out(formulas, name):\n",
" from pyecsca.ec.formula.expand import expand_formula_set\n",
@@ -615,9 +634,8 @@
" pickle.dump(expanded, f)\n",
" return name, len(expanded)\n",
"\n",
- "# 22 is really a maximum usable number here, as there are only 22 \"jobs\".\n",
"context = multiprocessing.get_context(\"spawn\")\n",
- "with ProcessPoolExecutor(max_workers=22, mp_context=context) as pool, enable_spawn(expand_out) as expand_func:\n",
+ "with ProcessPoolExecutor(max_workers=num_workers, mp_context=context) as pool, enable_spawn(expand_out) as expand_func:\n",
" futures = []\n",
" args = []\n",
" for coord_name, coords in tqdm(sw.coordinates.items(), desc=\"Submitting\"):\n",
@@ -638,15 +656,17 @@
" else:\n",
" res = future.result()\n",
" print(*res)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "a5b1ccd8-1b2b-4e1a-85e1-5cab2b45300c",
"metadata": {},
+ "source": [],
"outputs": [],
- "source": []
+ "execution_count": null
}
],
"metadata": {
diff --git a/re/rpa.ipynb b/re/rpa.ipynb
index 6f62c34..5d2d46b 100644
--- a/re/rpa.ipynb
+++ b/re/rpa.ipynb
@@ -18,26 +18,20 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "11a5f41d-1471-49c3-ba7c-ac87470a31d0",
"metadata": {},
- "outputs": [],
"source": [
- "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",
- "from functools import partial, lru_cache\n",
+ "from functools import partial\n",
"from scipy.stats import bernoulli\n",
- "from concurrent.futures import ProcessPoolExecutor, as_completed\n",
"\n",
"from IPython.display import HTML, display\n",
- "from tqdm.auto import tqdm, trange\n",
+ "from tqdm.auto import tqdm\n",
"import tabulate\n",
- "from anytree import LevelOrderGroupIter, RenderTree\n",
"\n",
"from pyecsca.ec.model import ShortWeierstrassModel\n",
"from pyecsca.ec.coordinates import AffineCoordinateModel\n",
@@ -48,15 +42,12 @@
"from pyecsca.ec.mod import mod\n",
"from pyecsca.ec.mult import *\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, absolute\n",
+ "from pyecsca.sca.trace.process import normalize\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",
"from pyecsca.ec.context import DefaultContext, local\n",
"from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish, RPA\n",
"from pyecsca.sca.trace import Trace\n",
- "from pyecsca.sca.trace.plot import plot_trace, plot_traces\n",
"\n",
"from eval import (eval_tree_symmetric, eval_tree_asymmetric,\n",
" success_rate_symmetric, success_rate_asymmetric,\n",
@@ -65,25 +56,25 @@
" amount_rate_symmetric, amount_rate_asymmetric,\n",
" success_rate_vs_majority_symmetric, success_rate_vs_majority_asymmetric,\n",
" success_rate_vs_query_rate_symmetric, load, store)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "3ff1d591-f922-4c94-9e47-ab053fc21cf1",
"metadata": {},
- "outputs": [],
"source": [
"%matplotlib ipympl\n",
"hv.extension(\"bokeh\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "194fff59-1c4b-473a-9ffc-99b256aecc24",
"metadata": {},
- "outputs": [],
"source": [
"model = ShortWeierstrassModel()\n",
"coordsaff = AffineCoordinateModel(model)\n",
@@ -112,7 +103,9 @@
"\n",
"# And P-256 for eval\n",
"p256 = get_params(\"secg\", \"secp256r1\", \"projective\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -125,10 +118,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "febb198f-4370-4abd-8edc-17c5c1da8d0f",
"metadata": {},
- "outputs": [],
"source": [
"multipliers = [\n",
" LTRMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True, True),\n",
@@ -167,7 +158,9 @@
" CombMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True)\n",
"]\n",
"print(len(multipliers))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -179,17 +172,14 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "44e7e2e9-e0ad-4c8d-8605-af68f73d73e2",
"metadata": {},
- "outputs": [],
"source": [
"scalar = 0b1000000000000000000000000000000000000000000000000\n",
"scalar = 0b1111111111111111111111111111111111111111111111111\n",
"scalar = 0b1010101010101010101010101010101010101010101010101\n",
"scalar = 0b1111111111111111111111110000000000000000000000000\n",
"scalar = 123456789123456789\n",
- "scarar = 8750920244948492046\n",
"# multiples is a mapping from a multiple (integer) to a set of scalar multipliers that compute said multiple when doing [scalar]P\n",
"multiples = {}\n",
"\n",
@@ -205,7 +195,9 @@
" table.append([str(mult), str(list(ctx.points.values()))])\n",
"\n",
"display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -219,10 +211,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "a7fb8a3f-7938-493b-88dc-582ba4d8959d",
"metadata": {},
- "outputs": [],
"source": [
"k = 108\n",
"kinv = mod(k, n).inverse()\n",
@@ -231,7 +221,9 @@
"print(\"Original P0\", P0_aff)\n",
"print(\"P0_target \", P0_target.to_affine())\n",
"print(\"Verify P0 \", curve.affine_multiply(P0_target.to_affine(), k))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -245,10 +237,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "8113cb3f-dc06-4cb7-955c-11cedb4fbdd7",
"metadata": {},
- "outputs": [],
"source": [
"table = [[\"Multiplier\", \"zero present\", \"multiple computed\"]]\n",
"\n",
@@ -261,7 +251,9 @@
" table.append([str(mult), f\"<b>{zero}</b>\" if zero else zero, f\"<b>{multiple}</b>\" if multiple else multiple])\n",
"\n",
"display(HTML(tabulate.tabulate(table, tablefmt=\"unsafehtml\", headers=\"firstrow\", colalign=(\"left\", \"center\", \"center\"))))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -273,19 +265,19 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "67d7705c-6a41-47d9-ad1e-23ea549aaf00",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"table = [[\"Multiple\", \"Multipliers\"]]\n",
"for multiple, mults in multiples.items():\n",
" table.append([bin(multiple), [mult.__class__.__name__ for mult in mults]])\n",
"\n",
"display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -311,10 +303,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "9bb61ac5-d837-4287-a5de-a9a63c346acf",
"metadata": {},
- "outputs": [],
"source": [
"def simulated_oracle(scalar, affine_point, simulate_mult_id=0, measure_init=True, measure_multiply=True, randomize=False):\n",
" real_mult = multipliers[simulate_mult_id]\n",
@@ -351,7 +341,9 @@
" change = bernoulli(flip_1).rvs() if real_result else bernoulli(flip_0).rvs()\n",
" return bool(real_result ^ change)\n",
" return biased"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -363,15 +355,15 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "b6c70d89-1c7d-4d7c-bc65-0cf766b86c0a",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"res = rpa_distinguish(params, multipliers, simulated_oracle)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -383,13 +375,13 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "1556e604-d0ab-403c-bd44-d53be8e18283",
"metadata": {},
- "outputs": [],
"source": [
"print(multipliers[0] in res)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -401,16 +393,16 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "838ae83b-771d-4e4c-8977-ba997aa4fbb6",
"metadata": {},
- "outputs": [],
"source": [
"re = RPA(set(multipliers))\n",
"with silent():\n",
" re.build_tree(p256, tries=10)\n",
"print(re.tree.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -422,13 +414,13 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "136000fe-4a4a-4261-bacc-a49102080749",
"metadata": {},
- "outputs": [],
"source": [
"print(re.tree.render_basic())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -436,15 +428,27 @@
"metadata": {},
"source": [
"#### What about (symmetric) noise?\n",
- "Now we can examine how the method performs in the presence of noise and with various majority vote parameters. Note that the code below spawns several processes (`num_cores`) and saturates their CPU fully, so set this to something appropriate."
+ "Now we can examine how the method performs in the presence of noise and with various majority vote parameters. The cells with the `store` and `load` calls can be used to store the results so that different plots can be printed without re-running the evaluation.\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Set the `num_workers` variable to something reasonable, like the number of cores of your machine minus two.\n",
+ "\n",
+ "</div>"
]
},
{
+ "metadata": {},
+ "cell_type": "code",
+ "source": "num_workers = 30",
+ "id": "74b83f35d681ab9b",
+ "outputs": [],
+ "execution_count": null
+ },
+ {
"cell_type": "code",
- "execution_count": null,
"id": "04bd8191-1af8-4183-ac95-31b1e1c48e1b",
"metadata": {},
- "outputs": [],
"source": [
"def build_tree(cfgs):\n",
" with silent():\n",
@@ -452,8 +456,10 @@
" re.build_tree(p256, tries=10)\n",
" return re.tree\n",
"\n",
- "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=30)"
- ]
+ "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=num_workers)"
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -468,16 +474,16 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "7be15799-d042-43ae-b052-ef7b103e1cca",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_symmetric(correct_rate, 100 / len(multipliers)).savefig(\"rpa_re_success_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
"query_rate_symmetric(query_rate).savefig(\"rpa_re_query_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
"precise_rate_symmetric(precise_rate).savefig(\"rpa_re_precise_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
"amount_rate_symmetric(amount_rate).savefig(\"rpa_re_amount_rate_symmetric.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -489,14 +495,14 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d5176863-d6b6-4205-8a3a-4453b8177305",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_vs_query_rate_symmetric(query_rate, correct_rate).savefig(\"rpa_re_scatter_symmetric.pdf\", bbox_inches=\"tight\")\n",
"success_rate_vs_majority_symmetric(correct_rate).savefig(\"rpa_re_plot_symmetric.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -508,23 +514,23 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "857f39ad-f6ba-4006-8da9-92f4318819e2",
"metadata": {},
- "outputs": [],
"source": [
"store(\"rpa_re_symmetric.nc\", correct_rate, precise_rate, amount_rate, query_rate)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "efb26038-87ea-4a5d-8682-f855c2bec13f",
"metadata": {},
- "outputs": [],
"source": [
"correct_rate, precise_rate, amount_rate, query_rate = load(\"rpa_re_symmetric.nc\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -532,15 +538,19 @@
"metadata": {},
"source": [
"#### What about (asymmetric) noise?\n",
- "The oracle may not only be noisy, but biased, this computation evaluates that case. Beware, for the same parameters this is about 6x slower because of the other dimension (two error probabilities instead of one)."
+ "The oracle may not only be noisy, but biased, this computation evaluates that case. Beware, for the same parameters this is about 6x slower because of the other dimension (two error probabilities instead of one).\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Recall the `num_workers` variable.\n",
+ "\n",
+ "</div>"
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "06268c58-63c9-4565-ba52-4414a9939581",
"metadata": {},
- "outputs": [],
"source": [
"def build_tree(cfgs):\n",
" with silent():\n",
@@ -548,22 +558,24 @@
" re.build_tree(p256, tries=10)\n",
" return re.tree\n",
"\n",
- "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=30)"
- ]
+ "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=num_workers)"
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "43a0055a-8d62-4f0a-be9f-e6ccb47b1d11",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_asymmetric(correct_rate_b, 100 / len(multipliers)).savefig(\"rpa_re_success_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"query_rate_asymmetric(query_rate_b).savefig(\"rpa_re_query_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"precise_rate_asymmetric(precise_rate_b).savefig(\"rpa_re_precise_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"amount_rate_asymmetric(amount_rate_b).savefig(\"rpa_re_amount_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"success_rate_vs_majority_asymmetric(correct_rate_b).savefig(\"rpa_re_plot_asymmetric.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -575,23 +587,23 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "85933a5e-f526-4002-9203-0e4ae4f731d0",
"metadata": {},
- "outputs": [],
"source": [
"store(\"rpa_re_asymmetric.nc\", correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "ddde34f8-7cde-449d-a2e3-289e1aefba72",
"metadata": {},
- "outputs": [],
"source": [
"correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = load(\"rpa_re_asymmetric.nc\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -608,12 +620,10 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "96bec03e-5397-440b-9e8c-81ba5253921b",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"def simulate_trace(mult, scalar, point):\n",
" with local(DefaultContext()) as ctx:\n",
@@ -648,14 +658,14 @@
" 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"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d74a944f-e0a6-434d-8a12-138dfb9d516e",
"metadata": {},
- "outputs": [],
"source": [
"table = [[\"True multiplier\", \"Reversed\", \"Correct\", \"Remaining\"]]\n",
"with silent():\n",
@@ -663,24 +673,33 @@
" res = rpa_distinguish(params, multipliers, partial(simulated_rpa_oracle, simulate_mult_id = i))\n",
" table.append([mult, res, mult in res, len(res)])\n",
"display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"id": "e694b3b3-290d-4528-a611-16a183662944",
"metadata": {},
"source": [
- "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."
+ "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. *If you changed any of the `scalar`, `k`, `P0`, `P0_target` or `multipliers` variables above, the cell below may not work correctly.*\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Recall the `num_workers` variable.\n",
+ "\n",
+ "</div>"
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "e47a70d7-7993-4560-9257-dbbc1cf658cf",
"metadata": {},
- "outputs": [],
"source": [
"def eval(threshold, sdev, tries, num_traces):\n",
+ " # This requires that scalar and P0_target variables are consistent, i.e. that:\n",
+ " # - P0 is computed by scalarmult multipliers[0] when computing [scalar]P0_target\n",
+ " # - but P0 is not computed by scalarmult multipliers[7] when computing [scalar]P0_target\n",
" noise = NormalNoice(0, sdev)\n",
" aff = P0_target.to_affine()\n",
" true_pos = 0\n",
@@ -704,7 +723,7 @@
" 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",
+ "with TaskExecutor(max_workers=num_workers) as pool:\n",
" for threshold in threshold_range:\n",
" for sdev in sdev_range:\n",
" for num_traces in traces_range:\n",
@@ -714,14 +733,14 @@
" 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"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"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",
@@ -730,21 +749,21 @@
" 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",
+ " color = \"white\" if val < 0.5 else \"black\"\n",
" if sval == \"0.00\":\n",
- " color=\"grey\"\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 j, sdev in enumerate(sdev_range):\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",
+ " color = \"white\" if val < 0.5 else \"black\"\n",
" if sval == \"0.00\":\n",
- " color=\"grey\"\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",
@@ -753,53 +772,29 @@
" 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.yaxis.set_label_coords(2.8, 0.5)\n",
" cbar.ax.set_ylabel(\"error probability\", rotation=-90, va=\"bottom\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"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\")"
- ]
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "1f809503-d572-4051-9731-a8a7d16ede33",
"metadata": {},
+ "source": [],
"outputs": [],
- "source": []
+ "execution_count": null
}
],
"metadata": {
diff --git a/re/zvp.ipynb b/re/zvp.ipynb
index 1c4a65e..2807da0 100644
--- a/re/zvp.ipynb
+++ b/re/zvp.ipynb
@@ -23,18 +23,11 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "17a9e580-5f1e-45c9-8afd-fc35e833b0b0",
"metadata": {},
- "outputs": [],
"source": [
"import io\n",
- "import numpy as np\n",
- "import pandas as pd\n",
"import holoviews as hv\n",
- "import xarray as xr\n",
- "import random\n",
- "import tabulate\n",
"import pickle\n",
"import multiprocessing\n",
"import inspect\n",
@@ -43,30 +36,27 @@
"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 sympy import FF, ZZ, symbols, Poly\n",
"from contextlib import contextmanager\n",
"from importlib import import_module, invalidate_caches\n",
"from pathlib import Path\n",
- "from functools import partial\n",
"from itertools import product\n",
- "from IPython.display import HTML, display\n",
+ "from IPython.display import display\n",
"from tqdm.notebook import tqdm, trange\n",
- "from anytree import RenderTree, LevelOrderIter\n",
+ "from anytree import LevelOrderIter, PreOrderIter\n",
"\n",
"\n",
"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, load_params_ecgen\n",
- "from pyecsca.ec.formula import FormulaAction, AdditionFormula, DoublingFormula\n",
+ "from pyecsca.ec.formula import AdditionFormula, DoublingFormula\n",
"from pyecsca.ec.point import Point\n",
- "from pyecsca.ec.mod import mod, gcd, SymbolicMod\n",
- "from pyecsca.ec.context import DefaultContext, local\n",
+ "from pyecsca.ec.mod import mod, SymbolicMod\n",
"from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder\n",
- "from pyecsca.ec.error import NonInvertibleError, UnsatisfiedAssumptionError\n",
+ "from pyecsca.ec.error import UnsatisfiedAssumptionError\n",
"from pyecsca.sca.re.tree import Map, Tree\n",
- "from pyecsca.sca.re.rpa import MultipleContext\n",
- "from pyecsca.sca.re.zvp import zvp_points, compute_factor_set, unroll_formula, addition_chain, eliminate_y\n",
+ "from pyecsca.sca.re.zvp import zvp_points, compute_factor_set, addition_chain, eliminate_y\n",
"from pyecsca.misc.cfg import getconfig\n",
"from pyecsca.misc.utils import TaskExecutor\n",
"\n",
@@ -99,18 +89,20 @@
"\n",
"%matplotlib ipympl\n",
"hv.extension(\"bokeh\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "faca31e8-fe51-4017-a41d-ba31b15c548d",
"metadata": {},
- "outputs": [],
"source": [
"model = ShortWeierstrassModel()\n",
"coordsaff = AffineCoordinateModel(model)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -123,21 +115,19 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "8de124f1-9498-4e55-8b7f-1bd291ccf3fe",
"metadata": {},
- "outputs": [],
"source": [
"which = \"jacobian\"\n",
"coords = model.coordinates[which]"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "2193ab53-9dc9-4ba4-89d3-e331e5cc20de",
"metadata": {},
- "outputs": [],
"source": [
"getconfig().ec.mod_implementation = \"symbolic\"\n",
"x, y, z = symbols(\"x y z\")\n",
@@ -175,7 +165,9 @@
"y_poly = Poly(res.Y.x, domain=field)\n",
"z_poly = Poly(res.Z.x, domain=field)\n",
"display(x_poly, y_poly, z_poly)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -187,14 +179,14 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d8ea0c4d-86e1-46af-ac20-569e6ef5439d",
"metadata": {},
- "outputs": [],
"source": [
"cfg = getconfig()\n",
"cfg.ec.mod_implementation = \"gmp\""
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -207,10 +199,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "0252f8fa-012c-453c-ba23-b40f9686fcce",
"metadata": {},
- "outputs": [],
"source": [
"curves = list(map(lambda spec: load_params_ecgen(io.BytesIO(spec.encode()), \"affine\"), [\n",
" # Random\n",
@@ -272,7 +262,9 @@
" else:\n",
" params.name = \"random\"\n",
" params.name += f\"[{i}]\""
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -286,10 +278,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "7ab00a5c-2873-40c0-a81c-873350897e46",
"metadata": {},
- "outputs": [],
"source": [
"scalars = [0b1111110, 0b1011101, 0b110110, 0b100100, 0b1000110, 0b1001101, 0b101001, 0b1100100, 0b1010110, 0b101010] * 4\n",
"\n",
@@ -304,7 +294,9 @@
" chain_map[params] = chain\n",
" ops.update(chain)\n",
"print(sorted(list(ops)))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -318,10 +310,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "da4e2981-cf3d-40ea-9d1e-9b6c57a6e01d",
"metadata": {},
- "outputs": [],
"source": [
"load_expanded = False\n",
"\n",
@@ -343,7 +333,9 @@
" formula_groups[coords] = groups\n",
"\n",
"print(f\"Loaded {sum(sum(len(group) for group in pair) for pair in formula_groups.values())} formulas.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -352,15 +344,27 @@
"source": [
"### Computing the factor sets\n",
"\n",
- "Now, compute the factor sets of the formulas **in parallel**. There are two options available. `xonly_fsets` builds the factor sets \"x\"-only by eliminating y-coords using the curve equation. `filter_nonhomo` specifies whether to filter out non-homogenous polynomials."
+ "Now, compute the factor sets of the formulas **in parallel**. There are two options available. `xonly_fsets` builds the factor sets \"x\"-only by eliminating y-coords using the curve equation. `filter_nonhomo` specifies whether to filter out non-homogenous polynomials.\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Set the `num_workers` variable to something reasonable, like the number of cores of your machine minus two.\n",
+ "\n",
+ "</div>"
]
},
{
+ "metadata": {},
+ "cell_type": "code",
+ "source": "num_workers = 30",
+ "id": "70a18871d5b46df4",
+ "outputs": [],
+ "execution_count": null
+ },
+ {
"cell_type": "code",
- "execution_count": null,
"id": "f71a9b68-6873-4bee-b1c2-3166ef74897b",
"metadata": {},
- "outputs": [],
"source": [
"xonly_fsets = False\n",
"filter_nonhomo = False\n",
@@ -389,7 +393,7 @@
" return fsets\n",
"\n",
"factor_sets = {}\n",
- "with TaskExecutor(max_workers=22, mp_context=spawn_context) as pool, enable_spawn(compute_fsets) as target:\n",
+ "with TaskExecutor(max_workers=num_workers, mp_context=spawn_context) as pool, enable_spawn(compute_fsets) as target:\n",
" for coord_name, coords in model.coordinates.items():\n",
" for formula_group, formula_class in zip(formula_groups[coords], formula_classes):\n",
" pool.submit_task((coords, formula_group, formula_class),\n",
@@ -404,7 +408,9 @@
" print(f\"Got {coords.name} {formula_class.shortname}s {len(fsets)}.\")\n",
" for formula, fset in zip(formula_group, fsets):\n",
" factor_sets[formula] = fset"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -416,27 +422,27 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "aef30807-e9eb-44f2-8837-f027c54eb724",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"factor_sets.pickle\", \"wb\") as f:\n",
" pickle.dump(factor_sets, f)\n",
" print(f\"Stored {len(factor_sets)} factor sets.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "86df44e6-aa3c-48eb-8561-36b08eaa781c",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"factor_sets.pickle\", \"rb\") as f:\n",
" factor_sets = pickle.load(f)\n",
" print(f\"Loaded {len(factor_sets)} factor sets.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -450,10 +456,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "564b2c16-6655-4ddb-8657-611d1d489e6a",
"metadata": {},
- "outputs": [],
"source": [
"polynomials = {}\n",
"for coord_name, coords in tqdm(model.coordinates.items(), desc=\"Accumulating\"):\n",
@@ -479,7 +483,9 @@
" coord_adds += len(add_polynomials)\n",
" coord_dbls += len(dbl_polynomials)\n",
" print(f\"Got {coord_adds} add polys and {coord_dbls} dbl polys for {coord_name}.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -487,15 +493,19 @@
"metadata": {},
"source": [
"### Computing ZVP points\n",
- "Now, lets compute the sets of ZVP points, going over all of the polynomials. Also filter the points such that for each \"polynomial, curve category, k\" we have only one point, as more are unneccessary."
+ "Now, lets compute the sets of ZVP points, going over all the polynomials. Also filter the points such that for each \"polynomial, curve category, k\" we have only one point, as more are unnecessary.\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Recall the `num_workers` variable.\n",
+ "\n",
+ "</div>"
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "8a637899-8c3c-43a1-86fa-f0322d41ce8c",
"metadata": {},
- "outputs": [],
"source": [
"# bound is the maximal dlog in the hard case of the DCP to be solved\n",
"bound = 100\n",
@@ -505,7 +515,7 @@
"all_points = set()\n",
"all_points_filtered = {}\n",
"dk = set()\n",
- "with TaskExecutor(max_workers=20, mp_context=spawn_context) as pool:\n",
+ "with TaskExecutor(max_workers=num_workers, mp_context=spawn_context) as pool:\n",
" for coord_name, coords in tqdm(model.coordinates.items(), desc=\"Submitting\"):\n",
" for chain, affine_params in zip(chains, curves):\n",
" try:\n",
@@ -543,7 +553,9 @@
"\n",
"print(f\"Got {len(all_points)} points.\")\n",
"print(f\"Got {len(all_points_filtered)} filtered points\")#, but just {len(set(all_points_filtered.values()))} unique.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -555,28 +567,28 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "82bc0305-b302-4240-a34c-81e13fe646b5",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"all_points.pickle\", \"wb\") as f:\n",
" pickle.dump((all_points, all_points_filtered), f)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "411832e9-26a8-46a4-82e6-5f6afe879188",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"all_points.pickle\", \"rb\") as f:\n",
" all_points, all_points_filtered = pickle.load(f)\n",
" \n",
"print(f\"Got {len(all_points)} points.\")\n",
"print(f\"Got {len(all_points_filtered)} filtered points\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -587,17 +599,21 @@
"\n",
"Our ZVP points might (due to the bounds above thus the incompleteness of our analysis) lead to more zeros than we attribute to them (in more configurations), i.e. \"false negatives\". They might also be erroneous and not lead to zeros if the argument `filter_nonhomo` is False, as non-homogenous intermediate polynomials are not filtered out of the analysis. They introduce \"false positives\" but also some true positives.\n",
"\n",
- "Thus we perform a remapping step where we execute the scalar multiplication with given points and trace whether they introduce the zeros. This gives us a new distinguishing map `remapped_hit_point_map`, now without \"false negatives\" or \"false positives\".\n",
+ "Thus, we perform a remapping step where we execute the scalar multiplication with given points and trace whether they introduce the zeros. This gives us a new distinguishing map `remapped_hit_point_map`, now without \"false negatives\" or \"false positives\".\n",
+ "\n",
+ "Note that we also construct two additional maps `remapped_count_point_map` and `remapped_position_point_map` which represent the results of remapping using an oracle counting the zeros and an oracle giving the positions of the zeros in the computation, respectively.\n",
"\n",
- "Note that we also construct two additional maps `remapped_count_point_map` and `remapped_position_point_map` which represent the results of remapping using an oracle counting the zeros and an oracle giving the positions of the zeros in the computation, respectively."
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "This is a resource intensive cell that uses parallelism. Recall the `num_workers` variable.\n",
+ "\n",
+ "</div>"
]
},
{
"cell_type": "code",
- "execution_count": null,
"id": "ca932717-2b0a-4dea-ae84-988b7d9af233",
"metadata": {},
- "outputs": [],
"source": [
"def remap(coords, chunk, points, scalar_map):\n",
" import numpy as np\n",
@@ -642,7 +658,7 @@
"#all_points_list = list(all_points)\n",
"all_points_list = list(set((list(res[0])[0], res[1]) for res in all_points_filtered.values()))\n",
"\n",
- "with TaskExecutor(max_workers=30, mp_context=spawn_context) as pool, enable_spawn(remap) as remap_spawn:\n",
+ "with TaskExecutor(max_workers=num_workers, mp_context=spawn_context) as pool, enable_spawn(remap) as remap_spawn:\n",
" for coord_name, coords in tqdm(model.coordinates.items()):\n",
" param_map = {}\n",
" points_mapped = []\n",
@@ -677,7 +693,7 @@
" for chunk, future in tqdm(pool.as_completed(), total=chunks, unit_scale=chunk_size, desc=f\"Remapping {coord_name} ({len(pairs)} formula pairs)\", leave=False, smoothing=0):\n",
" error = future.exception()\n",
" if error:\n",
- " print(j, error)\n",
+ " print(error)\n",
" else:\n",
" counts, positions = future.result()\n",
" for cfg, counts_row, positions_row in zip(chunk, counts, positions):\n",
@@ -693,7 +709,9 @@
" remapped_count_point_map[cfg] = count_map\n",
" remapped_position_point_map[cfg] = position_map\n",
" print(f\"{coord_name}: Remapped.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -705,25 +723,25 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "95c3693b-166c-4515-9153-e3e00d222835",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"remapped.pickle\", \"wb\") as f:\n",
" pickle.dump((remapped_hit_point_map, remapped_count_point_map, remapped_position_point_map), f)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "3914501e-269c-4a88-ba5b-ad3c6dd28cfb",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"remapped.pickle\", \"rb\") as f:\n",
" remapped_hit_point_map, remapped_count_point_map, remapped_position_point_map = pickle.load(f)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -736,10 +754,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "236d40a0-7a9c-48a0-b932-a0dfe1110a8c",
"metadata": {},
- "outputs": [],
"source": [
"cfgs = set()\n",
"for coord_name, coords in model.coordinates.items():\n",
@@ -761,30 +777,32 @@
" cfg_categories[name] = category_cfgs\n",
"category_map = {cfg: {\"category\": name} for name, category_cfgs in cfg_categories.items() for cfg in category_cfgs}\n",
"dmap_categories = Map.from_io_maps(cfgs, category_map)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "db1ffe84-f58e-465c-b417-ad1d563c8377",
"metadata": {},
- "outputs": [],
"source": [
"dmap_remapped = Map.from_io_maps(cfgs, remapped_hit_point_map)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "48baa442-549f-4ffa-b296-4f964c8efc77",
"metadata": {},
- "outputs": [],
"source": [
"from copy import deepcopy\n",
"dmap_dedup = deepcopy(dmap_remapped)\n",
"dmap_dedup.deduplicate()\n",
"print(f\"Rows before: {len(dmap_remapped.mapping)}, rows after deduplication: {len(dmap_dedup.mapping)}.\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -796,16 +814,16 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "5ffc5564-a42b-4837-94bb-4ecb890b38b2",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"tree_categories = Tree.build(cfgs, dmap_categories)\n",
"tree_remapped = tree_categories.expand(dmap_dedup)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -822,23 +840,23 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "b921aadd-ccc6-4bc2-9cb0-e3905ff4f6ab",
"metadata": {},
- "outputs": [],
"source": [
"print(tree_remapped.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "c3571008-1898-41e0-87d5-848707345d62",
"metadata": {},
- "outputs": [],
"source": [
"print(tree_remapped.render_basic())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -850,76 +868,74 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "5a680f71-f2de-4358-8352-67ec99d63704",
"metadata": {},
- "outputs": [],
"source": [
"dmap_count = Map.from_io_maps(cfgs, remapped_count_point_map)\n",
"dmap_count.deduplicate()"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "764b6dec-f1d5-4e8f-8585-b35d9261b1ca",
"metadata": {},
- "outputs": [],
"source": [
"print(dmap_count.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "cee72bcb-2486-4285-8dc7-80c101ca1760",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"tree_count = tree_categories.expand(dmap_count)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "17de9a81-102e-4804-906a-02d2baef42d5",
"metadata": {},
- "outputs": [],
"source": [
"dmap_position = Map.from_io_maps(cfgs, remapped_position_point_map)\n",
"dmap_position.deduplicate()"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "bc3db76f-192f-4e70-b2c4-8aa5a5f4e078",
"metadata": {},
- "outputs": [],
"source": [
"print(dmap_position.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "db92360c-cb96-4382-8255-d7773772b07d",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"tree_position = tree_categories.expand(dmap_position)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "b81d013a-7ff0-4b02-8c89-d6748d42874b",
"metadata": {},
- "outputs": [],
"source": [
"print(\"Zero hit\")\n",
"print(tree_remapped.describe())\n",
@@ -927,52 +943,70 @@
"print(tree_count.describe())\n",
"print(\"\\nZero position\")\n",
"print(tree_position.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
"id": "eff08e04-20bc-4fc7-978d-9cbfc06179b6",
"metadata": {},
"source": [
- "### Evaluation"
+ "### Evaluation\n",
+ "\n",
+ "The following cells evaluate the ZVP-RE method and its behavior under various levels of noise. The cells with the `store` and `load` calls can be used to store the results so that different plots can be printed without re-running the evaluation.\n",
+ "\n",
+ "<div class=\"alert alert-warning\">\n",
+ "\n",
+ "These are resource intensive cells that use parallelism. Recall the `num_workers` variable.\n",
+ "\n",
+ "</div>"
]
},
{
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "First, lets look at the binary oracle in presence of symmetric noise.",
+ "id": "7d61aa75df8e76b9"
+ },
+ {
"cell_type": "code",
- "execution_count": null,
"id": "3ef78642-fe65-46c7-8233-11dc43525991",
"metadata": {},
+ "source": "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=num_workers)",
"outputs": [],
- "source": [
- "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=30)"
- ]
+ "execution_count": null
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Let's save the results for later and then plot them.",
+ "id": "3e9d4f11cc322958"
},
{
"cell_type": "code",
- "execution_count": null,
"id": "34b5adf6-c4d1-4534-b95c-7e85e780e66f",
"metadata": {},
- "outputs": [],
"source": [
"store(\"zvp_re_symmetric.nc\", correct_rate, precise_rate, amount_rate, query_rate)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "0a443d93-cf71-4c6e-bc11-998a31a47656",
"metadata": {},
- "outputs": [],
"source": [
"correct_rate, precise_rate, amount_rate, query_rate = load(\"zvp_re_symmetric.nc\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "3bef547e-7c8e-4ec4-a842-75889cf6acd9",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_symmetric(correct_rate, None).savefig(\"zvp_re_success_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
"precise_rate_symmetric(precise_rate).savefig(\"zvp_re_precise_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
@@ -980,94 +1014,116 @@
"amount_rate_symmetric(amount_rate).savefig(\"zvp_re_amount_rate_symmetric.pdf\", bbox_inches=\"tight\")\n",
"success_rate_vs_query_rate_symmetric(query_rate, correct_rate).savefig(\"zvp_re_scatter_symmetric.pdf\", bbox_inches=\"tight\")\n",
"success_rate_vs_majority_symmetric(correct_rate).savefig(\"zvp_re_plot_symmetric.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Now, lets look at the binary oracle in presence of asymmetric noise.",
+ "id": "4ef7396c82d760df"
},
{
"cell_type": "code",
- "execution_count": null,
"id": "064e76e9-a299-4a5c-ae44-adfe07d86901",
"metadata": {},
+ "source": "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=num_workers)",
"outputs": [],
- "source": [
- "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=30)"
- ]
+ "execution_count": null
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Let's save the results for later and then plot them.",
+ "id": "335e6e29d6e92030"
},
{
"cell_type": "code",
- "execution_count": null,
"id": "ccdebf35-6401-497f-8731-b205eab672f8",
"metadata": {},
- "outputs": [],
"source": [
"store(\"zvp_re_asymmetric.nc\", correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "8924c80d-2d65-40a6-b589-85bbe93d1094",
"metadata": {},
- "outputs": [],
"source": [
"correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = load(\"zvp_re_asymmetric.nc\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "fa23ea1b-2b95-4f22-b237-bd4d75980681",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_asymmetric(correct_rate_b, None).savefig(\"zvp_re_success_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"precise_rate_asymmetric(precise_rate_b).savefig(\"zvp_re_precise_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"query_rate_asymmetric(query_rate_b).savefig(\"zvp_re_query_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"amount_rate_asymmetric(amount_rate_b).savefig(\"zvp_re_amount_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n",
"success_rate_vs_majority_asymmetric(correct_rate_b).savefig(\"zvp_re_plot_asymmetric.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Finally, lets analyze the count oracle in the presence of noise.",
+ "id": "2ba367834f6a62fb"
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d0566c3d-fb55-496b-aeb3-17b674d32ca2",
"metadata": {},
+ "source": "correct_rate_c, precise_rate_c, amount_rate_c, query_rate_c = eval_tree_binomial1(cfgs, [tree_count], num_tries=100, num_cores=num_workers)",
"outputs": [],
- "source": [
- "correct_rate_c, precise_rate_c, amount_rate_c, query_rate_c = eval_tree_binomial1(cfgs, [tree_count], num_tries=100, num_cores=30)"
- ]
+ "execution_count": null
+ },
+ {
+ "metadata": {},
+ "cell_type": "markdown",
+ "source": "Let's save the results for later and then plot them.",
+ "id": "580d9adeb81b6b4b"
},
{
"cell_type": "code",
- "execution_count": null,
"id": "ea781b4d-0073-4c83-9854-0f7b104f7b14",
"metadata": {},
- "outputs": [],
"source": [
"store(\"zvp_re_binomial.nc\", correct_rate_c, precise_rate_c, amount_rate_c, query_rate_c)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "088a9776-0713-402d-b351-994ba2e24d4d",
"metadata": {},
- "outputs": [],
"source": [
"correct_rate_c, precise_rate_c, amount_rate_c, query_rate_c = load(\"zvp_re_binomial.nc\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "1eedce32-a74a-4baf-a5ab-a08cd8b96a6e",
"metadata": {},
- "outputs": [],
"source": [
"success_rate_binomial(correct_rate_c, None).savefig(\"zvp_re_success_rate_binomial.pdf\", bbox_inches=\"tight\")\n",
"precise_rate_binomial(precise_rate_c).savefig(\"zvp_re_precise_rate_binomial.pdf\", bbox_inches=\"tight\")\n",
"query_rate_binomial(query_rate_c).savefig(\"zvp_re_query_rate_binomial.pdf\", bbox_inches=\"tight\")\n",
"amount_rate_binomial(amount_rate_c).savefig(\"zvp_re_amount_rate_binomial.pdf\", bbox_inches=\"tight\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -1087,10 +1143,8 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d258bc29-b24f-4d57-a183-cb5d58e3f20f",
"metadata": {},
- "outputs": [],
"source": [
"fset_map = {}\n",
"fset_nonhomo_map = {}\n",
@@ -1110,33 +1164,35 @@
" fset_nonhomo.update(factor_sets_nonhomo[formula])\n",
" fset_map[formulas] = fset\n",
" fset_nonhomo_map[formulas] = fset_nonhomo"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "fde74d6a-9895-4fed-83a1-29a5c06ad5a6",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"factor_sets_extended.pickle\", \"wb\") as f:\n",
" pickle.dump((factor_sets, fset_map), f)\n",
"with open(\"factor_sets_nonhomo_extended.pickle\", \"wb\") as f:\n",
" pickle.dump((factor_sets_nonhomo, fset_nonhomo_map), f)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "e513a996-3f61-4ae7-9089-e5e46de6b863",
"metadata": {},
- "outputs": [],
"source": [
"with open(\"factor_sets_extended.pickle\", \"rb\") as f:\n",
" factor_sets, fset_map = pickle.load(f)\n",
"with open(\"factor_sets_nonhomo_extended.pickle\", \"rb\") as f:\n",
" factor_sets_nonhomo, fset_nonhomo_map = pickle.load(f)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -1148,76 +1204,76 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "8076b999-0c93-4748-aa3d-3986f05c62e3",
"metadata": {},
- "outputs": [],
"source": [
"dmap_fset = Map.from_sets(set(fset_map.keys()), fset_map, deduplicate=True)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "47bc3406-6f60-4706-a59d-19feb8f50dea",
"metadata": {},
- "outputs": [],
"source": [
"print(dmap_fset.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "6d4f33f3-557a-4e79-aadb-10fd73aba1d0",
"metadata": {},
- "outputs": [],
"source": [
"tree_fset = Tree.build(dmap_fset.cfgs, dmap_fset)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "7e539028-c7af-446e-b523-97f08fa3e39d",
"metadata": {},
- "outputs": [],
"source": [
"dmap_fset_nonhomo = Map.from_sets(set(fset_nonhomo_map.keys()), fset_nonhomo_map, deduplicate=True)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "afdc58ef-28c2-469a-9a2d-6db44824915e",
"metadata": {},
- "outputs": [],
"source": [
"print(dmap_fset_nonhomo.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "660bf7d1-e25d-40c4-bcd7-d520c566c432",
"metadata": {},
- "outputs": [],
"source": [
"tree_fset_nonhomo = Tree.build(dmap_fset_nonhomo.cfgs, dmap_fset_nonhomo)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "93a67306-e507-422c-92e2-f1439437060f",
"metadata": {},
- "outputs": [],
"source": [
"print(\"Factor sets\")\n",
"print(tree_fset.describe())\n",
"print(\"\\nFactor sets (unfiltered)\")\n",
"print(tree_fset_nonhomo.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -1231,24 +1287,24 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "366ba814-c8ae-4567-8e26-27130f9dbfc9",
"metadata": {},
- "outputs": [],
"source": [
"expanded = tree_remapped.expand(dmap_fset)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "bf8ad92e-a3e9-43c6-8c8a-c5e6d42eee6b",
"metadata": {},
- "outputs": [],
"source": [
"print(\"Zero hit + factor sets\")\n",
"print(expanded.describe())"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "markdown",
@@ -1268,12 +1324,10 @@
},
{
"cell_type": "code",
- "execution_count": null,
"id": "b78f99d6-46b9-44bb-b9b4-5df7fc4fa990",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"p = set()\n",
"for node in PreOrderIter(expanded.root):\n",
@@ -1287,16 +1341,16 @@
" for formula, fset in factor_sets_nonhomo.items():\n",
" if pp in fset:\n",
" print(formula)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "1bd71766-4633-4136-b00a-e42fa304ff92",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"rev_point_map = {}\n",
"for (poly, params_cat, k), (points, affine_params) in all_points_filtered.items():\n",
@@ -1323,16 +1377,16 @@
" print(\"------\")\n",
" else:\n",
" print(\".\", end=\"\") #poly_set, point)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d38370e9-c222-4f7e-9a08-d4e299083f87",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"for node in PreOrderIter(tree_remapped.root):\n",
" if node.dmap_input:\n",
@@ -1363,16 +1417,16 @@
" print(pad, cfg)\n",
" print(\"\")\n",
" print(\"------\")"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "d327e346-9c82-4e50-9357-ba66b3c511ed",
"metadata": {
"scrolled": true
},
- "outputs": [],
"source": [
"for coord_name, coords in model.coordinates.items():\n",
" total = 1\n",
@@ -1384,14 +1438,14 @@
" print(\"\\t\", formula)\n",
" total *= lf\n",
" print(\"\\t\", total)"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "f98fca35-5c01-434d-95b5-0ba81ab37721",
"metadata": {},
- "outputs": [],
"source": [
"for tree in (tree_remapped, tree_count, tree_position):\n",
" same = 0\n",
@@ -1402,16 +1456,16 @@
" cds.add(c[1].coordinate_model)\n",
" same += len(cds) == 1\n",
" print(same / len(tree.leaves))"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"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",
@@ -1421,14 +1475,14 @@
" 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);"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"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",
@@ -1438,15 +1492,17 @@
"del dmap_counter[0]\n",
"fig, ax = plt.subplots(figsize=(10, 3))\n",
"ax.bar(dmap_counter.keys(), dmap_counter.values(), width=1);"
- ]
+ ],
+ "outputs": [],
+ "execution_count": null
},
{
"cell_type": "code",
- "execution_count": null,
"id": "892e02c7-8c39-4467-91ff-b6ae265684aa",
"metadata": {},
+ "source": [],
"outputs": [],
- "source": []
+ "execution_count": null
}
],
"metadata": {
generated by cgit v1.3.1 (git 2.54.0) at 2026-07-18 03:45:42 +0000