kernel_search¶

class cryptographic_estimators.MREstimator.MRAlgorithms.kernel_search.KernelSearch(problem: MRProblem, **kwargs)¶

Bases: MRAlgorithm

Construct an instance of KernelSearch estimator.

Parameters:

problem (MRProblem) – An instance of the MRProblem 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.MREstimator.MRAlgorithms.kernel_search import KernelSearch
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> E = KernelSearch(MRProblem(q=7, m=9, n=10, k=15, r=4))
>>> E
KernelSearch estimator for the MinRank problem with (q, m, n, k, r) = (7, 9, 10, 15, 4)

a()¶

Return the optimal a, i.e. number of vectors to guess in the kernel of the low-rank matrix.

Examples

>>> from cryptographic_estimators.MREstimator.MRAlgorithms.kernel_search import KernelSearch
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> KS = KernelSearch(MRProblem(q=7, m=9, n=10, k=15, r=4))
>>> KS.a()
1

Tests:

>>> from cryptographic_estimators.MREstimator.MRAlgorithms.kernel_search import KernelSearch
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> KS = KernelSearch(MRProblem(q=16, m=15, n=15, k=78, r=6))
>>> KS.a()
4

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

property complexity_type¶: Returns the attribute _complexity_type.

cost_reduction(a, lv)¶

Return the cost of computing the reduced instance.

The reduced instance is obtained after one guess of a kernel vectors.

Parameters:: a – Number of vectors to guess in the kernel of the low-rank matrix

get_optimal_parameters_dict()¶: Returns the optimal parameters dictionary.

get_problem_parameters_reduced(a, lv)¶

Return the problem parameters of the reduced instance.

Returns the problem parameters after guessing a kernel vectors and lv entries in the solution vector.

Args: - a – no. of vectors to guess in the kernel of the low-rank matrix - lv – no. of entries to guess in the solution vector

has_optimal_parameter()¶

Return True if the algorithm has optimal parameter.

Tests:

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

hybridization_factor(a, lv)¶

Return the logarithm of the number of reduced instances to be solved.

Parameters:

a – No. of vectors to guess in the kernel of the low-rank matrix.
lv – No. of entries to guess in the solution vector.

linear_algebra_constant()¶

Return the linear algebra constant.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_algorithm import MRAlgorithm
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRAlgorithm(MRProblem(q=7, m=9, n=10, k=15, r=4), w=2).linear_algebra_constant()
2

lv()¶

Return the optimal lv, i.e. number of entries to guess in the solution.

Examples

>>> from cryptographic_estimators.MREstimator.MRAlgorithms.kernel_search import KernelSearch
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> KS = KernelSearch(MRProblem(q=7, m=9, n=10, k=15, r=4))
>>> KS.lv()
0

Tests:

>>> from cryptographic_estimators.MREstimator.MRAlgorithms.kernel_search import KernelSearch
>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> KS = KernelSearch(MRProblem(q=16, m=15, n=15, k=78, r=6))
>>> KS.lv()
3

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.