hybrid_linearization

class cryptographic_estimators.RankSDEstimator.RankSDAlgorithms.hybrid_linearization.HybridLinearization(problem: RankSDProblem, **kwargs)

Bases: RankSDAlgorithm

Construct an instance of HybridLinearization estimator.

This algorithm tries to solve a given instance by randomly generating new equations from the orginal equations and attempting to solve them by linearization [GRS16]

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.hybrid_linearization import HybridLinearization
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> HL = HybridLinearization(RankSDProblem(q=2,m=127,n=118,k=48,r=7))
>>> HL
Hybrid Linearization 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).

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)

t()

Return the optimal t, i.e. the number of zero entries expected to have a random element of the support.

Examples:
>>> from cryptographic_estimators.RankSDEstimator.RankSDAlgorithms.hybrid_linearization import HybridLinearization
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> HL = HybridLinearization(RankSDProblem(q=2,m=31,n=33,k=15,r=10))
>>> HL.t()
15
Tests:
>>> from cryptographic_estimators.RankSDEstimator.RankSDAlgorithms.hybrid_linearization import HybridLinearization
>>> from cryptographic_estimators.RankSDEstimator.ranksd_problem import RankSDProblem
>>> HL = HybridLinearization(RankSDProblem(q=2,m=37,n=41,k=18,r=13))
>>> HL.t()
18
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.