ranksd_estimator

class cryptographic_estimators.RankSDEstimator.ranksd_estimator.RankSDEstimator(q: int, m: int, n: int, k: int, r: int, memory_bound=inf, **kwargs)

Bases: BaseEstimator

Construct an instance of RankSDEstimator.

Parameters:

  • q (int) – Base field order.

  • m (int) – Extension degree.

  • n (int) – Code length.

  • k (int) – Code dimension.

  • r (int) – Target rank.

  • memory_bound (float, optional) – Maximum allowed memory to use for solving the problem. Defaults to inf.

  • **kwargs –

    Additional keyword arguments.

    excluded_algorithm (list) - A list/tuple of excluded algorithms (default: None)

Examples

>>> from cryptographic_estimators.RankSDEstimator.ranksd_estimator import RankSDEstimator
>>> RSDE = RankSDEstimator(q=2, m=127, n=118, k=48, r=7)

Construct an instance of BaseEstimator.

Parameters:

  • alg – Specialized algorithm class (subclass of BaseAlgorithm).

  • prob – Object of any subclass of BaseProblem.

  • **kwargs –

    Additional keyword arguments.

    excluded_algorithms (list or tuple) - A list/tuple of excluded algorithms. Default: None.

    memory_access (int) - 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.

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

    bit_complexities (int) - State complexity as bit rather than field operations. Default: 1. Only relevant for complexity_type 0.

    include_tildeo (int) - Specifies if tildeO estimation should be included in the outputs. Default: 0. 0: no tildeO estimation.

    include_quantum (int) - Specifies if quantum estimation should be included in the outputs. Default: 0. 0: no quantum estimation.

algorithm_names()

Return a list of the name of considered algorithms.

algorithms()

Return a list of considered algorithms.

property bit_complexities

Returns a list of bit_complexities attributes of included algorithms.

property complexity_type

Returns a list of complexity_type attributes of included algorithms.

estimate(**kwargs)

Returns dictionary describing the complexity of each algorithm and its optimal parameters.

property estimator_type

Returns the type of the estimator.

Either problem or scheme

excluded_algorithms_by_default = []
fastest_algorithm(use_tilde_o_time=False)

Return the algorithm with the smallest time complexity.

Parameters:

use_tilde_o_time (bool) – Use Ō time complexity, i.e., ignore polynomial factors. Default is False.

property memory_access

Returns a list of memory_access attributes of included algorithms.

nalgorithms()

Return the number of considered algorithms.

reset()

Resets the internal states of the estimator and all included algorithms.

table(show_quantum_complexity=0, show_tilde_o_time=0, show_all_parameters=0, precision=1, truncate=0)

Print table describing the complexity of each algorithm and its optimal parameters.

Parameters:

  • show_quantum_complexity (int) – Show quantum time complexity (default: 0).

  • show_tilde_o_time (int) – Show Ō time complexity (default: 0).

  • show_all_parameters (int) – Show all optimization parameters (default: 0).

  • precision (int) – Number of decimal digits output (default: 1).

  • truncate (int) – Truncate rather than round the output (default: 0).

Examples

>>> from cryptographic_estimators.RankSDEstimator.ranksd_estimator import RankSDEstimator
>>> RSDE = RankSDEstimator(q=2, m=31, n=33, k=15, r=10, w=2)
>>> RSDE.table(show_all_parameters=1)
+---------------------+--------------------------------------------+
|                     |                  estimate                  |
+---------------------+-------+--------+---------------------------+
| algorithm           |  time | memory |         parameters        |
+---------------------+-------+--------+---------------------------+
| BasisEnumeration    | 206.0 |   17.6 |             {}            |
| OJ1                 | 160.6 |   16.5 |             {}            |
| OJ2                 | 204.9 |   15.9 |             {}            |
| GRS                 | 162.2 |   18.2 |             {}            |
| ImprovedGRS         | 147.2 |   18.0 |             {}            |
| GuessingEnhancedGRS | 138.3 |   18.1 |          {'t': 1}         |
| HybridLinearization | 174.4 |   12.4 |         {'t': 15}         |
| MaxMinors           | 153.0 |   33.0 |     {'a': 12, 'p': 2}     |
| SupportMinors       | 155.1 |   40.1 | {'b': 1, 'a': 11, 'p': 0} |
+---------------------+-------+--------+---------------------------+

Tests:

>>> from cryptographic_estimators.RankSDEstimator.ranksd_estimator import RankSDEstimator
>>> from cryptographic_estimators.RankSDEstimator.RankSDAlgorithms import BasisEnumeration,GRS,OJ1,OJ2,HybridLinearization
>>> RSDE = RankSDEstimator(q=2, m=31, n=33, k=15, r=10, w=2, excluded_algorithms=[BasisEnumeration,GRS,OJ1,OJ2,HybridLinearization])
>>> RSDE.table(show_all_parameters=1)
+---------------------+--------------------------------------------+
|                     |                  estimate                  |
+---------------------+-------+--------+---------------------------+
| algorithm           |  time | memory |         parameters        |
+---------------------+-------+--------+---------------------------+
| ImprovedGRS         | 147.2 |   18.0 |             {}            |
| GuessingEnhancedGRS | 138.3 |   18.1 |          {'t': 1}         |
| MaxMinors           | 153.0 |   33.0 |     {'a': 12, 'p': 2}     |
| SupportMinors       | 155.1 |   40.1 | {'b': 1, 'a': 11, 'p': 0} |
+---------------------+-------+--------+---------------------------+

>>> RSDE = RankSDEstimator(q=2, m=37, n=41, k=18, r=13, w=2, excluded_algorithms=[BasisEnumeration,GRS,OJ1,OJ2,HybridLinearization])
>>> RSDE.table(show_all_parameters=1)
+---------------------+--------------------------------------------+
|                     |                  estimate                  |
+---------------------+-------+--------+---------------------------+
| algorithm           |  time | memory |         parameters        |
+---------------------+-------+--------+---------------------------+
| ImprovedGRS         | 216.5 |   19.3 |             {}            |
| GuessingEnhancedGRS | 209.5 |   19.4 |          {'t': 6}         |
| MaxMinors           | 237.7 |   42.7 |     {'a': 15, 'p': 2}     |
| SupportMinors       | 240.5 |   53.3 | {'b': 2, 'a': 14, 'p': 0} |
+---------------------+-------+--------+---------------------------+

>>> RSDE = RankSDEstimator(q=2, m=43, n=47, k=18, r=17, w=2, excluded_algorithms=[BasisEnumeration,GRS,OJ1,OJ2,HybridLinearization])
>>> RSDE.table(show_all_parameters=1)
+---------------------+------------------------------------+
|                     |              estimate              |
+---------------------+-------+--------+-------------------+
| algorithm           |  time | memory |     parameters    |
+---------------------+-------+--------+-------------------+
| ImprovedGRS         | 283.6 |   20.4 |         {}        |
| GuessingEnhancedGRS | 283.6 |   20.4 |      {'t': 0}     |
| MaxMinors           | 308.8 |   53.8 | {'a': 15, 'p': 2} |
| SupportMinors       |    -- |     -- |         {}        |
+---------------------+-------+--------+-------------------+