crossbred¶

class cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred.Crossbred(problem: MQProblem, **kwargs)¶

Bases: MQAlgorithm

Construct an instance of crossbred estimator.

The Crossbred is an algorithm to solve the MQ problem [JV18]. This algorithm consists of two steps: the preprocessing step and the linearization step. In the preprocessing step, we find a set S of degree-D polynomials in the ideal generated by the initial set of polynomials. Every specialization of the first n-k variables of the polynomials in S results in a set S’ of degree-d polynomials in k variables. Finally, in the linearization step, a solution to S’ is found by direct linearization.

Note

Our complexity estimates are a generalization over any field of size q of the complexity formulas given in [Dua20], which are given either for q=2 or generic fields.

Parameters:

problem (MQProblem) – MQProblem object including all necessary parameters.
**kwargs –
Additional keyword arguments.

h (int) - External hybridization parameter. Defaults to 0.

w (float) - Linear algebra constant (2 <= w <= 3). Defaults to 2.81.

max_D (int) - Upper bound to the parameter D. Defaults to 20.

memory_access (int) - Specifies the memory access cost model. Defaults to 0. Choices: 0 - constant, 1 - logarithmic, 2 - square-root, 3 - cube-root. Alternatively, deploy a custom function which takes as input the logarithm of the total memory usage.

complexity_type (int) - Complexity type to consider. Defaults to 0. 0: estimate, 1: tilde O complexity.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred import Crossbred
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Crossbred(MQProblem(n=10, m=12, q=5))
>>> E
Crossbred estimator for the MQ problem with 10 variables and 12 polynomials

D()¶

Return the optimal D, i.e. the degree of the initial Macaulay matrix.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred import Crossbred
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Crossbred(MQProblem(n=10, m=12, q=5), max_D = 10)
>>> E.D()
3

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

property complexity_type¶: Returns the attribute _complexity_type.

d()¶

Return the optimal d, i.e. degree resulting Macaulay matrix.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred import Crossbred
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Crossbred(MQProblem(n=10, m=12, q=5), max_D = 10)
>>> E.d()
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

k()¶

Return the optimal k, i.e. the number of variables in the resulting system.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred import Crossbred
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Crossbred(MQProblem(n=10, m=12, q=5))
>>> E.k()
5

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 max_D¶

Return the upper bound of the degree of the initial Macaulay matrix.

Examples

>>> from cryptographic_estimators.MQEstimator.MQAlgorithms.crossbred import Crossbred
>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> E = Crossbred(MQProblem(n=10, m=12, q=5))
>>> E.max_D
10

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.