Created
January 30, 2024 00:35
-
-
Save mogproject/65359782dc609a44b47d2d9402002674 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"id": "68e47dd2-4d05-4bfa-bb66-9c314742f4d8", | |
"metadata": {}, | |
"source": [ | |
"## Multilinear Detection" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"id": "190ea649-1ddb-467e-a69a-947a3c4f0292", | |
"metadata": { | |
"jupyter": { | |
"source_hidden": true | |
}, | |
"tags": [] | |
}, | |
"outputs": [], | |
"source": [ | |
"import sys\n", | |
"import math\n", | |
"import warnings\n", | |
"from random import Random\n", | |
"import sympy as sp\n", | |
"from IPython.display import display_latex\n", | |
"\n", | |
"warnings.filterwarnings('ignore')\n", | |
"import galois" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"id": "c14d807f-6c57-4f9c-b5ac-acf1987dfc59", | |
"metadata": { | |
"tags": [] | |
}, | |
"outputs": [], | |
"source": [ | |
"def solve(p, n, k, max_degree, fingerprint_size, rand: Random):\n", | |
" \"\"\"Implementation of Algorithm 1 in Koutis and Williams, 2016.\"\"\"\n", | |
"\n", | |
" v = [rand.randint(0, 2 ** k - 1) for _ in range(n)]\n", | |
" ell = 3 + int(math.ceil(math.log2(max_degree)))\n", | |
" GF = galois.GF(2, ell)\n", | |
" A_tilde = [GF(rand.randint(0, 2 ** ell - 1)) for _ in range(fingerprint_size)]\n", | |
" S = GF(0)\n", | |
" \n", | |
" for j in range(2 ** k):\n", | |
" X_tilde = [(vi & j).bit_count() % 2 for vi in v]\n", | |
" S = S + p(X_tilde, A_tilde)\n", | |
"\n", | |
" return bool(S)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"id": "2d3bf942-e5d3-4f81-b685-2418683d5a12", | |
"metadata": { | |
"jupyter": { | |
"source_hidden": true | |
}, | |
"tags": [] | |
}, | |
"outputs": [], | |
"source": [ | |
"class Degree:\n", | |
" def __init__(self, d): self.d = d\n", | |
" def __add__(self, other): return self if isinstance(other, int) else Degree(max(self.d, other.d))\n", | |
" def __mul__(self, other): return self if isinstance(other, int) else Degree(self.d + other.d)\n", | |
" __radd__ = __add__\n", | |
" __rmul__ = __mul__\n", | |
" def __int__(self): return self.d\n", | |
" def __repr__(self): return f'{self.d}'" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"id": "ba5b7472-1f58-42ef-8bac-6a1179f7198c", | |
"metadata": { | |
"jupyter": { | |
"source_hidden": true | |
}, | |
"tags": [] | |
}, | |
"outputs": [], | |
"source": [ | |
"class Circuit:\n", | |
" def __init__(self, p, n, fingerprint_size):\n", | |
" print('Symbolic evaluation:')\n", | |
" display_latex(p(sp.symbols([f'x_{i}' for i in range(n)]), [1 for _ in range(fingerprint_size)]))\n", | |
" print('Expanded:')\n", | |
" display_latex(sp.expand(p(sp.symbols([f'x_{i}' for i in range(n)]), [1 for _ in range(fingerprint_size)])))\n", | |
" print('With fingerprint:')\n", | |
" display_latex(sp.expand(p(sp.symbols([f'x_{i}' for i in range(n)]), sp.symbols([f'a_{i}' for i in range(fingerprint_size)]))))\n", | |
"\n", | |
" d = int(p([Degree(1) for _ in range(n)], [1 for _ in range(fingerprint_size)]))\n", | |
" print('Max degree:', d)\n", | |
" \n", | |
" self.p = p\n", | |
" self.n = n\n", | |
" self.fingerprint_size = fingerprint_size\n", | |
" self.d = d\n" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"id": "3ff57fba-e3d7-427e-954d-01db26ddea47", | |
"metadata": { | |
"jupyter": { | |
"source_hidden": true | |
}, | |
"tags": [] | |
}, | |
"outputs": [], | |
"source": [ | |
"def run(C, k, rand: Random, num_iterations: int=100):\n", | |
" print(f'Running: k={k}')\n", | |
" count = 0\n", | |
" for _ in range(num_iterations):\n", | |
" if solve(C.p, C.n, k, C.d, C.fingerprint_size, rand):\n", | |
" sys.stdout.write('T')\n", | |
" count += 1\n", | |
" else:\n", | |
" sys.stdout.write('F')\n", | |
" print(f'\\n{count}/{num_iterations}')" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"id": "a461f659-1f84-4b4f-900c-154d0caa78f6", | |
"metadata": {}, | |
"source": [ | |
"### Example" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 7, | |
"id": "b00db21b-a8c7-4dc4-a96d-2f42fea4e34e", | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Symbolic evaluation:\n" | |
] | |
}, | |
{ | |
"data": { | |
"text/latex": [ | |
"$\\displaystyle x_{0}^{4} + x_{2} \\left(x_{0} + x_{1}\\right)$" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
}, | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Expanded:\n" | |
] | |
}, | |
{ | |
"data": { | |
"text/latex": [ | |
"$\\displaystyle x_{0}^{4} + x_{0} x_{2} + x_{1} x_{2}$" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
}, | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"With fingerprint:\n" | |
] | |
}, | |
{ | |
"data": { | |
"text/latex": [ | |
"$\\displaystyle a_{0} a_{2} x_{0} x_{2} + a_{1} a_{2} x_{1} x_{2} + a_{3} x_{0}^{4}$" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
}, | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Max degree: 4\n", | |
"Running: k=4\n", | |
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\n", | |
"0/100\n", | |
"Running: k=3\n", | |
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\n", | |
"0/100\n", | |
"Running: k=2\n", | |
"TFTTFTTFFFTTTFTFFTFFTTFTTFFTTFFTTFFTFFTFFTFTFTFTTFTFTFTTFTFTTFFTTFTFTFFTTTTFFTTTTFFTTTTTFTFFTTTTTTFT\n", | |
"57/100\n", | |
"Running: k=1\n", | |
"TFTTTTFFTFFTFFTFFFTFTTFTTFFTTFTTTFTFFFTFTTFTFFTTTTFTTTTTFTTTFFTFTTFFTFTFTTTFFFTTTTFFFTFTFTTTFTTFFTFF\n", | |
"55/100\n" | |
] | |
} | |
], | |
"source": [ | |
"C = Circuit(lambda X, A: ((X[0] * A[0] + X[1] * A[1]) * X[2]) * A[2] + (X[0] * X[0] * X[0] * X[0]) * A[3], 3, 4)\n", | |
"\n", | |
"run(C, 4, Random(12345))\n", | |
"run(C, 3, Random(12345))\n", | |
"run(C, 2, Random(12345))\n", | |
"run(C, 1, Random(12345))" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": null, | |
"id": "333ae609-7d4e-4c4a-8b8f-7d7802ef19c1", | |
"metadata": {}, | |
"outputs": [], | |
"source": [] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3 (ipykernel)", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.10.4" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 5 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment