mayo_estimator

class cryptographic_estimators.MAYOEstimator.mayo_estimator.MAYOEstimator(n: int, m: int, o: int, k: int, q: int, memory_bound=inf, **kwargs)

Bases: BaseEstimator

Construct an instance of MAYOEstimator.

Parameters:

• n (int) – Number of variables.

• m (int) – Number of polynomials.

• o (int) – Dimension of the oil space.

• k (int) – Whipping parameter.

• q (int) – Order of the finite field.

• memory_bound – Memory bound.

• **kwargs –

  Additional keyword arguments.

  theta - Exponent of the conversion factor (default: 2). If 0 <= theta <= 2, every multiplication in GF(q) is counted as log2(q) ^ theta binary operation. If theta = None, every multiplication in GF(q) is counted as 2 * log2(q) ^ 2 + log2(q) binary operation.

  w - Linear algebra constant (default: 2.81).

  w_ks - Linear algebra constant (only for kipnis-shamir algorithm) (default: 2.8).

  h - External hybridization parameter (default: 0).

  excluded_algorithms - A list/tuple of algorithms to be excluded (default: []).

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

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

  bit_complexities - Determines if complexity is given in bit operations or basic operations (default 1: in bit).

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)

Tests:

>>> if skip_long_doctests:
...     pytest.skip()
>>> from cryptographic_estimators.MAYOEstimator import MAYOEstimator
>>> E = MAYOEstimator(n=66, m=64, o=8, k=9, q=16)
>>> E.table(show_all_parameters=1)
+----------------------+--------------+-------------------------------------------------------------+
|                      |              |                           estimate                          |
+----------------------+--------------+-------+--------+--------------------------------------------+
| algorithm            | attack_type  |  time | memory |                 parameters                 |
+----------------------+--------------+-------+--------+--------------------------------------------+
| DirectAttack         |   forgery    | 130.8 |   28.5 | {'k': 16, 'a': 18, 'variant': 'Hashimoto'} |
| KipnisShamir         | key-recovery | 222.1 |   17.1 |                     {}                     |
| ReconciliationAttack | key-recovery | 143.2 |   48.1 |      {'k': 9, 'variant': 'las_vegas'}      |
| IntersectionAttack   | key-recovery | 254.8 |   33.5 |      {'k': 1, 'variant': 'las_vegas'}      |
| ClawFinding          |   forgery    | 142.1 |  132.1 |        {'X': 130.915, 'Y': 125.085}        |
+----------------------+--------------+-------+--------+--------------------------------------------+

>>> E = MAYOEstimator(n=78, m=64, o=18, k=4, q=16)
>>> E.table(show_all_parameters=1)
+----------------------+--------------+------------------------------------------------------------+
|                      |              |                          estimate                          |
+----------------------+--------------+-------+--------+-------------------------------------------+
| algorithm            | attack_type  |  time | memory |                 parameters                |
+----------------------+--------------+-------+--------+-------------------------------------------+
| DirectAttack         |   forgery    | 153.8 |   49.4 | {'k': 11, 'a': 6, 'variant': 'Hashimoto'} |
| KipnisShamir         | key-recovery | 190.8 |   18.7 |                     {}                    |
| ReconciliationAttack | key-recovery | 151.2 |   48.1 |     {'k': 11, 'variant': 'las_vegas'}     |
| IntersectionAttack   | key-recovery | 202.5 |   45.0 |      {'k': 0, 'variant': 'las_vegas'}     |
| ClawFinding          |   forgery    | 142.1 |  132.1 |        {'X': 130.915, 'Y': 125.085}       |
+----------------------+--------------+-------+--------+-------------------------------------------+

>>> E = MAYOEstimator(n=90, m=56, o=8, k=10, q=16)
>>> E.table(show_all_parameters=1)
+----------------------+--------------+------------------------------------------------------------+
|                      |              |                          estimate                          |
+----------------------+--------------+-------+--------+-------------------------------------------+
| algorithm            | attack_type  |  time | memory |                 parameters                |
+----------------------+--------------+-------+--------+-------------------------------------------+
| DirectAttack         |   forgery    |  93.7 |   35.9 | {'k': 3, 'a': 27, 'variant': 'Hashimoto'} |
| KipnisShamir         | key-recovery | 319.3 |   18.0 |                     {}                    |
| ReconciliationAttack | key-recovery | 150.3 |   43.8 |     {'k': 13, 'variant': 'las_vegas'}     |
| IntersectionAttack   | key-recovery | 399.1 |   59.1 |      {'k': 0, 'variant': 'las_vegas'}     |
| ClawFinding          |   forgery    | 126.0 |  116.0 |        {'X': 115.011, 'Y': 108.989}       |
+----------------------+--------------+-------+--------+-------------------------------------------+

>>> E = MAYOEstimator(n=64, m=60, o=10, k=21, q=16)
>>> E.table(show_all_parameters=1)
+----------------------+--------------+------------------------------------------------------------+
|                      |              |                          estimate                          |
+----------------------+--------------+-------+--------+-------------------------------------------+
| algorithm            | attack_type  |  time | memory |                 parameters                |
+----------------------+--------------+-------+--------+-------------------------------------------+
| DirectAttack         |   forgery    |  98.8 |   38.6 | {'k': 3, 'a': 29, 'variant': 'Hashimoto'} |
| KipnisShamir         | key-recovery | 198.0 |   17.3 |                     {}                    |
| ReconciliationAttack | key-recovery | 134.6 |   49.8 |      {'k': 6, 'variant': 'las_vegas'}     |
| IntersectionAttack   | key-recovery | 224.8 |   36.5 |      {'k': 0, 'variant': 'las_vegas'}     |
| ClawFinding          |   forgery    | 134.0 |  124.0 |        {'X': 122.962, 'Y': 117.038}       |
+----------------------+--------------+-------+--------+-------------------------------------------+