dinur1

class cryptographic_estimators.MQEstimator.MQAlgorithms.dinur1.DinurFirst(problem: MQProblem, **kwargs)

Bases: MQAlgorithm

Construct an instance of Dinur’s first estimator.

The Dinur’s first is a probabilistic algorithm to solve the MQ problem over GF(2) [Din21a]. It computes the parity of the number of solutions of many quadratic polynomial systems. These systems come from the specialization, in the original system, of the values in a fixed set of variables.

Parameters:

  • problem (MQProblem) – MQProblem object including all necessary parameters.

  • nsolutions (int) – Number of solutions (default: 1).

  • h (int) – External hybridization parameter (default: 0).

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.dinur1 import DinurFirst
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = DinurFirst(MQProblem(n=10, m=12, q=2))
>>> E
Dinur1 estimator for the MQ problem with 10 variables and 12 polynomials
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.

get_reduced_parameters()
has_optimal_parameter()

Return True if the algorithm has optimal parameter.

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

Return the optimal kappa.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.dinur1 import DinurFirst
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = DinurFirst(MQProblem(n=10, m=12, q=2))
>>> E.kappa()
0.3333333333333333
lambda_()

Return the optimal lambda_.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.dinur1 import DinurFirst
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = DinurFirst(MQProblem(n=10, m=12, q=2))
>>> E.lambda_()
0.2222222222222222
linear_algebra_constant()

Returns the linear algebra constant.

Tests:
>>> from cryptographic_estimators.MQEstimator.mq_algorithm import MQAlgorithm
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQAlgorithm(MQProblem(n=10, m=5, q=4), w=2).linear_algebra_constant()
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_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.

npolynomials_reduced()

Return the number of polynomials after applying the Thomae and Wolf strategy.

Returns:

The number of polynomials after applying the Thomae and Wolf strategy.

Return type:

int

Tests:
>>> from cryptographic_estimators.MQEstimator.mq_algorithm import MQAlgorithm
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQAlgorithm(MQProblem(n=5, m=10, q=2)).npolynomials_reduced()
10
>>> MQAlgorithm(MQProblem(n=60, m=20, q=2)).npolynomials_reduced()
18
nvariables_reduced()

Return the number of variables after fixing some values.

Tests:
>>> from cryptographic_estimators.MQEstimator.mq_algorithm import MQAlgorithm
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQAlgorithm(MQProblem(n=5, m=10, q=2)).nvariables_reduced()
5
>>> MQAlgorithm(MQProblem(n=25, m=20, q=2)).nvariables_reduced()
20
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).

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 predifined values.

Parameters:

parameters (dict) – 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.