estimator_folding's Introduction

Estimator complexity for F4-OLE

How to run the estimator

Open a sage shell
Load the module:

sage: load("Folding.sage")

It will automatically load the ISD.sage module. 3. To estimate the cost of a specific instance, run expect_cost. Example:

sage: expect_cost(c=5, t=14, s=16, q=4, verbose=True)

[...]

Prange --> 169.34343621773516
Lee-Brickell --> 157.80428093327953
Stern --> 149.60824546567432
Optimized_Stern --> 152.51597482747042
MMT --> 140.96761009080828
Folded code has length 3645
Average running time of best ISD at each weight is 140.96761009080828
Weight which minimizes ISD/Proba is 62 which happens with proba 8.722688081689128e-05.
   --> Repeat 11465 (~=2^14) times ISD with aborts (each of them costing 2^124.60204541920282) ---> 138.08691309298325
There are 75628919722004322604209288760~=2^95.93292466855976  possible subgroups of size 3^10.
138.08691309298325

To get a suitable number of errors to achieve a specific security level, run find_t. Example:

sage: t=find_t(c=5, s=15, q=4, security_parameter=128, verbose=True)
Starting from t=12.

[...]

t=12 --> 111.85718141458838 bits. Too small. Testing t=13.

[...]

t=13 --> 121.41917938528088 bits. Too small. Testing t=14.

[...]

Prange --> 169.34350329465923
Lee-Brickell --> 157.8043467206174
Stern --> 149.60831033537673
Optimized_Stern --> 152.51604028505164
MMT --> 140.96767327320416
Folded code has length 3645
Average running time of best ISD at each weight is 140.96767327320416
Weight which minimizes ISD/Proba is 62 which happens with proba 8.721446046640164e-05.
	--> Repeat 11466 (~=2^14) times ISD with aborts (each of them costing 2^124.60204541920282) ---> 138.08711853485795
There are 103741619611085612124067759~=2^86.42312526537337  possible subgroups of size 3^9.
For s=15, c=5, we need t=14 for a security estimated to 138.08711853485795 bits

How to add a new ISD algorithm

It suffices to implement the complexity in the ISD.sage module, following the same template as the other algorithms already there. Once it is implemented, you can add it to the dictionnary ISDs at the end. This is the one that will be exposed in Folding.sage. There is no need to change the main file.

estimator_folding's People

Contributors

Stargazers

Watchers

estimator_folding's Issues

Issue running script on SageMath 10.3

When running the script of MacOS with SageMath 10.3 I'm getting the following output:

│ SageMath version 10.3, Release Date: 2024-03-19                    │
│ Using Python 3.11.8. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage: load("Folding.sage")
sage: expect_cost(c=5, t=14, s=16, q=4, verbose=True)
-------------------------------------------------------------------------
NotImplementedError                     Traceback (most recent call last)
Cell In[2], line 1
----> 1 expect_cost(c=Integer(5), t=Integer(14), s=Integer(16), q=Integer(4), verbose=True)

File <string>:266, in expect_cost(c, t, s, q, ISD_l, verbose, offset)

File <string>:27, in GV(R, q)

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/scipy/optimize/_zeros_py.py:349, in newton(func, x0, fprime, args, tol, maxiter, fprime2, x1, rtol, full_output, disp)
    347     p1 = x0 * (1 + eps)
    348     p1 += (eps if p1 >= 0 else -eps)
--> 349 q0 = func(p0, *args)
    350 funcalls += 1
    351 q1 = func(p1, *args)

File <string>:27, in <lambda>(x)

File <string>:13, in h(q, x)

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/sage/misc/functional.py:1162, in log(*args, **kwds)
   1160     pass
   1161 from sage.functions.log import logb
-> 1162 return logb(args[0], args[1])

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/sage/symbolic/function.pyx:1023, in sage.symbolic.function.BuiltinFunction.__call__ (build/cythonized/sage/symbolic/function.c:14773)()
   1021
   1022             if custom is not None:
-> 1023                 return custom(*args)
   1024
   1025         if not hold and not dont_call_method_on_arg:

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/sage/symbolic/function.pyx:767, in sage.symbolic.function.Function._eval_numpy_ (build/cythonized/sage/symbolic/function.c:11987)()
    765         not support numpy arrays as arguments
    766     """
--> 767     raise NotImplementedError("The Function %s does not support numpy arrays as arguments" % self.name())
    768
    769 def _eval_mpmath_(self, *args):

NotImplementedError: The Function log does not support numpy arrays as arguments```

Recommend Projects