uov_estimator

class cryptographic_estimators.UOVEstimator.uov_estimator.UOVEstimator(n: int, m: int, q: int, memory_bound=inf, **kwargs)

Bases: BaseEstimator

Construct an instance of UOVEstimator.

Parameters:

• n (int) – Number of variables.

• m (int) – Number of polynomials.

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

• memory_bound (float, optional) – Memory bound. Defaults to inf.

• **kwargs –

  Additional keyword arguments.

  w (int, optional) - Linear algebra constant. Defaults to 2.

  theta (float or None, optional) - Exponent of the conversion factor. Defaults to 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.

  h (int, optional) - External hybridization parameter. Defaults to 0.

  excluded_algorithms (list or tuple, optional) - Algorithms to be excluded. Defaults to [].

  memory_access (int or callable, optional) - Specifies the memory access cost model. Defaults to 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, optional) - Complexity type to consider. Defaults to 0. 0: estimate, 1: tilde O complexity.

  bit_complexities (int, optional) - Determines if complexity is given in bit operations or basic operations. Defaults to 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, *args, **kwargs)

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.UOVEstimator import UOVEstimator
>>> A = UOVEstimator(n=24, m=10, q=2)
>>> A.table(show_tilde_o_time=1)
+--------------------+--------------+---------------+------------------+
|                    |              |    estimate   | tilde_o_estimate |
+--------------------+--------------+------+--------+-------+----------+
| algorithm          | attack_type  | time | memory |  time |   memory |
+--------------------+--------------+------+--------+-------+----------+
| DirectAttack       |   forgery    | 11.2 |    9.5 |   8.0 |      9.5 |
| KipnisShamir       | key-recovery | 16.8 |   12.5 |    -- |       -- |
| CollisionAttack    |   forgery    | 17.4 |    8.0 |    -- |       -- |
| IntersectionAttack | key-recovery | 23.3 |   13.1 |    -- |       -- |
| WedgeAttack        | key-recovery | 42.1 |   40.6 |    -- |       -- |
+--------------------+--------------+------+--------+-------+----------+

>>> from cryptographic_estimators.UOVEstimator import UOVEstimator
>>> E = UOVEstimator(q=13, n=25, m=23)
>>> E.table(show_all_parameters=True)
+--------------------+--------------+--------------------------------------------+
|                    |              |                  estimate                  |
+--------------------+--------------+------+--------+----------------------------+
| algorithm          | attack_type  | time | memory |         parameters         |
+--------------------+--------------+------+--------+----------------------------+
| DirectAttack       |   forgery    | 61.8 |   49.5 | {'k': 6, 'variant': 'PXL'} |
| CollisionAttack    |   forgery    | 54.8 |   45.5 | {'X': 47.968, 'Y': 35.507} |
| IntersectionAttack | key-recovery |   -- |     -- |             {}             |
| WedgeAttack        | key-recovery | 15.8 |   10.5 |       {'o_prime': 4}       |
+--------------------+--------------+------+--------+----------------------------+

Tests:

>>> if skip_long_doctests:
...     pytest.skip()
>>> from cryptographic_estimators.UOVEstimator import UOVEstimator
>>> A = UOVEstimator(n=112, m=44, q=256, theta=None)
>>> A.table(show_all_parameters=1) # long time
+--------------------+--------------+-----------------------------------------------+
|                    |              |                    estimate                   |
+--------------------+--------------+-------+--------+------------------------------+
| algorithm          | attack_type  |  time | memory |          parameters          |
+--------------------+--------------+-------+--------+------------------------------+
| DirectAttack       |   forgery    | 135.6 |  105.8 |  {'k': 5, 'variant': 'PXL'}  |
| KipnisShamir       | key-recovery | 218.1 |   22.1 |              {}              |
| CollisionAttack    |   forgery    | 189.3 |  181.0 | {'X': 180.389, 'Y': 169.976} |
| IntersectionAttack | key-recovery | 165.7 |   76.5 |           {'k': 2}           |
| WedgeAttack        | key-recovery | 140.7 |  132.0 |       {'o_prime': 18}        |
+--------------------+--------------+-------+--------+------------------------------+

>>> A = UOVEstimator(n=184, m=72, q=256, theta=None)
>>> A.table(show_all_parameters=1) # long time
+--------------------+--------------+-----------------------------------------------+
|                    |              |                    estimate                   |
+--------------------+--------------+-------+--------+------------------------------+
| algorithm          | attack_type  |  time | memory |          parameters          |
+--------------------+--------------+-------+--------+------------------------------+
| DirectAttack       |   forgery    | 215.2 |  170.3 |  {'k': 7, 'variant': 'PXL'}  |
| KipnisShamir       | key-recovery | 348.2 |   24.2 |              {}              |
| CollisionAttack    |   forgery    | 301.6 |  293.3 | {'X': 292.034, 'Y': 282.331} |
| IntersectionAttack | key-recovery | 249.9 |  117.9 |           {'k': 2}           |
| WedgeAttack        | key-recovery | 206.9 |  198.3 |       {'o_prime': 26}        |
+--------------------+--------------+-------+--------+------------------------------+