may_ozerov¶

class cryptographic_estimators.SDEstimator.SDAlgorithms.may_ozerov.MayOzerov(problem: SDProblem, **kwargs)¶

Bases: SDAlgorithm

Complexity estimate of May-Ozerov algorithm in depth 2 and 3.

Introduced in [MO15].

Expected weight distribution:

<—–+ n - k - l +—–>
w - 2p

<–+ (k + l)/2 +–>
p

<–+ (k + l)/2 +–>
p

Parameters:: problem (SDProblem) – SDProblem object including all necessary parameters.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> MayOzerov(SDProblem(n=100,k=50,w=10))
May-Ozerov estimator for syndrome decoding problem with (n,k,w) = (100,50,10) over Finite Field of size 2

property attack_type¶: Returns the attack type of the algorithm.

property complexity_type¶: Returns the optimization type, either ‘bit security’ or ‘asymptotic’.

depth()¶

Return the optimal parameter $depth$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import BJMM
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = BJMM(SDProblem(n=100,k=50,w=10))
>>> A.depth()
2

get_optimal_parameters_dict()¶: Returns the optimal parameters dictionary.

has_optimal_parameter()¶

Return True if the algorithm has optimal parameter.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).has_optimal_parameter()
False

initialize_parameter_ranges()¶

property memory_access¶: Returns the attribute _memory_access.

memory_access_cost(mem: float)¶

Returns the memory access cost (in logarithmic scale) of the algorithm per basic operation.

Parameters:: mem (float) – Memory consumption of an algorithm.
Returns:: Memory access cost in logarithmic scale.
Return type:: float

Note

memory_access: Specifies the memory access cost model (default: 0, choices: 0 - constant, 1 - logarithmic, 2 - square-root, 3 - cube-root or deploy custom function which takes as input the logarithm of the total memory usage)

memory_complexity(**kwargs)¶

Return the memory complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.

optimal_parameters()¶

Return a dictionary of optimal parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).optimal_parameters()
{}

parameter_names()¶

Return the list with the names of the algorithm’s parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).parameter_names()
[]

property parameter_ranges¶

Returns the set ranges for optimal parameter search.

Returns the set ranges in which optimal parameters are searched by the optimization algorithm (used only for complexity type estimate).

r()¶: Returns the optimal parameter r used in the optimization of the M4RI Gaussian elimination.

reset()¶: Resets all internal variables to restart the optimization process.

set_parameter_ranges(parameter: str, min_value: float, max_value: float)¶

Set range of specific parameter.

If optimal parameter is already set, it must fall in that range.

Parameters:

parameter (str) – Name of parameter to set
min_value (float) – Lowerbound for parameter (inclusive)
max_value (float) – Upperbound for parameter (inclusive)

set_parameters(parameters: dict)¶

Set optimal parameters to predefined values, then do not allow optimization to modify the ranges again.

Parameters:: parameters (dict) – A dictionary including parameters to set (for a subset of optimal_parameters functions).

time_complexity(**kwargs)¶

Return the time complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.

class cryptographic_estimators.SDEstimator.SDAlgorithms.may_ozerov.MayOzerovD2(problem: SDProblem, **kwargs)¶

Bases: SDAlgorithm

Complexity estimate of May-Ozerov algorithm in depth 2.

[MO15] May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 203-228 . Springer (2015)

Expected weight distribution:

<—–+ n - k - l +—–>
w - 2p

<–+ (k + l)/2 +–>
p

<–+ (k + l)/2 +–>
p

Parameters:: problem (SDProblem) – SDProblem object including all necessary parameters.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_2
May-Ozerov estimator in depth 2 for syndrome decoding problem with (n,k,w) = (100,50,10) over Finite Field of size 2

property attack_type¶: Returns the attack type of the algorithm.

property complexity_type¶: Returns the attribute _complexity_type.

get_optimal_parameters_dict()¶: Returns the optimal parameters dictionary.

has_optimal_parameter()¶

Return True if the algorithm has optimal parameter.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).has_optimal_parameter()
False

initialize_parameter_ranges()¶: Initialize the parameters p, l, p1.

l()¶

Return the optimal parameter $l$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_2.l()
2

property memory_access¶: Returns the attribute _memory_access.

memory_access_cost(mem: float)¶

Returns the memory access cost (in logarithmic scale) of the algorithm per basic operation.

Parameters:: mem (float) – Memory consumption of an algorithm.
Returns:: Memory access cost in logarithmic scale.
Return type:: float

Note

memory_complexity(**kwargs)¶

Return the memory complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.

optimal_parameters()¶

Return a dictionary of optimal parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).optimal_parameters()
{}

p()¶

Return the optimal parameter $p$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_2.p()
2

p1()¶

Return the optimal parameter $p1$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_2.p1()
1

parameter_names()¶

Return the list with the names of the algorithm’s parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).parameter_names()
[]

property parameter_ranges¶

Returns the set ranges for optimal parameter search.

Returns the set ranges in which optimal parameters are searched by the optimization algorithm (used only for complexity type estimate).

r()¶: Returns the optimal parameter r used in the optimization of the M4RI Gaussian elimination.

reset()¶: Resets internal state of the algorithm.

set_parameter_ranges(parameter: str, min_value: float, max_value: float)¶

Set range of specific parameter.

If optimal parameter is already set, it must fall in that range.

Parameters:

parameter (str) – Name of parameter to set
min_value (float) – Lowerbound for parameter (inclusive)
max_value (float) – Upperbound for parameter (inclusive)

set_parameters(parameters: dict)¶

Set optimal parameters to predefined values, then do not allow optimization to modify the ranges again.

Parameters:: parameters (dict) – A dictionary including parameters to set (for a subset of optimal_parameters functions).

time_complexity(**kwargs)¶

Return the time complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.

class cryptographic_estimators.SDEstimator.SDAlgorithms.may_ozerov.MayOzerovD3(problem: SDProblem, **kwargs)¶

Bases: SDAlgorithm

Complexity estimate of May-Ozerov algorithm in depth 3.

Expected weight distribution:

<—–+ n - k - l +—–>
w - 2p

<–+ (k + l)/2 +–>
p

<–+ (k + l)/2 +–>
p

Parameters:: problem (SDProblem) – SDProblem object including all necessary parameters.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_3
May-Ozerov estimator in depth 3 for syndrome decoding problem with (n,k,w) = (100,50,10) over Finite Field of size 2

property attack_type¶: Returns the attack type of the algorithm.

property complexity_type¶: Returns the attribute _complexity_type.

get_optimal_parameters_dict()¶: Returns the optimal parameters dictionary.

has_optimal_parameter()¶

Return True if the algorithm has optimal parameter.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).has_optimal_parameter()
False

initialize_parameter_ranges()¶: Initialize the parameter ranges for p, p1, p2, l to start the optimization process.

l()¶

Return the optimal parameter $l$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_3.l()
11

property memory_access¶: Returns the attribute _memory_access.

memory_access_cost(mem: float)¶

Returns the memory access cost (in logarithmic scale) of the algorithm per basic operation.

Parameters:: mem (float) – Memory consumption of an algorithm.
Returns:: Memory access cost in logarithmic scale.
Return type:: float

Note

memory_complexity(**kwargs)¶

Return the memory complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.

optimal_parameters()¶

Return a dictionary of optimal parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).optimal_parameters()
{}

p()¶

Return the optimal parameter $p$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_3.p()
2

p1()¶

Return the optimal parameter $p1$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_3.p1()
1

p2()¶

Return the optimal parameter $p2$ used in the algorithm optimization.

Examples

>>> from cryptographic_estimators.SDEstimator.SDAlgorithms import MayOzerov
>>> from cryptographic_estimators.SDEstimator import SDProblem
>>> A = MayOzerov(SDProblem(n=100,k=50,w=10))
>>> A.MayOzerov_depth_3.p2()
2

parameter_names()¶

Return the list with the names of the algorithm’s parameters.

Tests:

>>> from cryptographic_estimators import BaseAlgorithm, BaseProblem
>>> BaseAlgorithm(BaseProblem()).parameter_names()
[]

property parameter_ranges¶

Returns the set ranges for optimal parameter search.

Returns the set ranges in which optimal parameters are searched by the optimization algorithm (used only for complexity type estimate).

r()¶: Returns the optimal parameter r used in the optimization of the M4RI Gaussian elimination.

reset()¶: Resets internal state of the algorithm.

set_parameter_ranges(parameter: str, min_value: float, max_value: float)¶

Set range of specific parameter.

If optimal parameter is already set, it must fall in that range.

Parameters:

parameter (str) – Name of parameter to set
min_value (float) – Lowerbound for parameter (inclusive)
max_value (float) – Upperbound for parameter (inclusive)

set_parameters(parameters: dict)¶

Set optimal parameters to predefined values, then do not allow optimization to modify the ranges again.

Parameters:: parameters (dict) – A dictionary including parameters to set (for a subset of optimal_parameters functions).

time_complexity(**kwargs)¶

Return the time complexity of the algorithm.

Parameters:

**kwargs –

Arbitrary keyword arguments.

optimal_parameters - If for each optimal parameter of the algorithm a value is provided, the computation is done based on those parameters.