lokshtanov

class cryptographic_estimators.MQEstimator.MQAlgorithms.lokshtanov.Lokshtanov(problem: MQProblem, **kwargs)

Bases: MQAlgorithm

Construct an instance of Lokshtanov et al.’s estimator.

Lokshtanov et al.’s is a probabilistic algorithm to solve the MQ problem over GF(q) [LPTWY17]. It describes an algorithm to determine the consistency of a given system of polynomial equations.

Parameters:

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

• h (int, optional) – The external hybridization parameter. Defaults to 0.

• memory_access (int, optional) – Specifies the memory access cost model. Defaults to 0 (constant), 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.

• complexity_type (int, optional) – The complexity type to consider. Defaults to 0 (estimate), choices: 0 - estimate, 1 - tilde O complexity.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.lokshtanov import Lokshtanov
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Lokshtanov(MQProblem(n=10, m=12, q=9))
>>> E
Lokshtanov et al. 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.

delta()

Return the optimal delta for Lokshtanov et al.’s algorithm.

Returns:

The optimal delta value.

Return type:

float

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.lokshtanov import Lokshtanov
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Lokshtanov(MQProblem(n=10, m=12, q=9))
>>> E.delta()
0.1

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

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).

quantum_time_complexity()

Return quantum gate complexity

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.