ourivski_johansson_2

class cryptographic_estimators.RankSDEstimator.RankSDAlgorithms.ourivski_johansson_2.OJ2(problem: RankSDProblem, **kwargs)

Bases: RankSDAlgorithm

Construct an instance of OJ2 estimator

This algorithm tries to solve a given instance by enumerating the possible F_q basis of Suppx, and solving a linearized quadratic system [OJ02]

Parameters:

  • problem (RankSDProblem) – An instance of the RankSDProblem class.

  • **kwargs –

    Additional keyword arguments.

    w (int) - Linear algebra constant (default: 3).

    theta (int) - Exponent of the conversion factor (default: 2).

Examples

>>> from cryptographic_estimators.RankSDEstimator.RankSDAlgorithms.ourivski_johansson_2 import OJ2
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> OJ = OJ2(RankSDProblem(q=2,m=127,n=118,k=48,r=7))
>>> OJ
OJ2 estimator for the Rank Syndrome Decoding problem with (q, m, n, k, r) = (2, 127, 118, 48, 7)

Base class for RankSD algorithms complexity estimator.

Parameters:

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

  • **kwargs –

    Additional keyword arguments.

    w (int, optional) - linear algebra constant. Defaults to 3.

Examples

>>> from cryptographic_estimators.RankSDEstimator.ranksd_algorithm import RankSDAlgorithm
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> A = RankSDAlgorithm(RankSDProblem(q=2, m=31, n=33, k=15, r=10))
>>> A
BaseRankSDAlgorithm estimator for the Rank Syndrome Decoding problem with (q, m, n, k, r) = (2, 31, 33, 15, 10)
property attack_type

Returns the attack type of the algorithm.

property complexity_type

Returns the attribute _complexity_type.

compute_memory_complexity_helper(a, b, p, op_on_base_field)

Return the time complexity of the reduced instance, i.e., after puncturing the code on p positions and specializing a columns in X.

Parameters:

  • a (int) – Number of columns to guess in X.

  • b (int) – Degree of linear variables.

  • p (int) – Number of positions to puncture in the code.

  • op_on_base_field (boolean) – True if operations are performed on Fq. False if performed on Fq^m.

compute_time_complexity_helper(a, b, p, op_on_base_field)

Return the time complexity of the reduced instance, i.e., after puncturing the code on p positions and specializing a columns in X.

Parameters:

  • a (int) – Number of columns to guess in X.

  • b (int) – Degree of linear variables.

  • p (int) – Number of positions to puncture in the code.

  • op_on_base_field (boolean) – True if operations are performed on Fq. False if performed on Fq^m.

get_optimal_parameters_dict()

Returns the optimal parameters dictionary.

get_reduced_instance_parameters(a, p)

Return the problem parameters of the reduced instance, i.e., after puncturing the code on p positions and specializing a columns in X.

Parameters:

  • a (int) – Number of columns to guess in X.

  • p (int) – Number of positions to puncture in the code.

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

Return the linear algebra constant.

Tests:
>>> from cryptographic_estimators.RankSDEstimator.ranksd_algorithm import RankSDAlgorithm
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> RankSDAlgorithm(RankSDProblem(q=2, m=31, n=33, k=15, r=10), 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.

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.