pk_estimator

class cryptographic_estimators.PKEstimator.pk_estimator.PKEstimator(n: int, m: int, q: int, ell: int = 1, memory_bound=inf, **kwargs)

Bases: BaseEstimator

Construct an instance of Permuted Kernel Estimator.

Parameters:

  • n (int) – Columns of the matrix.

  • m (int) – Rows of the matrix.

  • q (int) – Size of the field.

  • ell (int) – Rows of the matrix whose permutation should lie in the kernel.

  • memory_bound – Memory bound.

  • **kwargs –

    Additional keyword arguments.

    sd_parameters (dict) - Optional parameter arguments for SDEstimator used by SBC algorithm.

    cost_for_list_operation - Cost in Fq additions for one list operation in the SBC and KMP algorithm (default n-m).

    memory_for_list_element - Memory in Fq elements for one list element in the SBC and KMP algorithm (default n-m).

    use_parity_row (bool) - Enables trick of appending extra (all one) row to the matrix, i.e., m -> m+1 (default: False).

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

    nsolutions - No. of solutions.

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.PKEstimator import PKEstimator
>>> A = PKEstimator(n=40,m=10,q=7,ell=2)
>>> A.table()
+-----------+----------------+
|           |    estimate    |
+-----------+-------+--------+
| algorithm |  time | memory |
+-----------+-------+--------+
| KMP       | 146.4 |  105.5 |
| SBC       | 137.6 |   42.8 |
+-----------+-------+--------+
Tests:
>>> if skip_long_doctests:
...     pytest.skip()
>>> from cryptographic_estimators.PKEstimator import PKEstimator
>>> A = PKEstimator(n=100,m=50,q=31,ell=2)
>>> A.table(precision=3, show_all_parameters=1) # long time
+-----------+------------------------------------------------+
|           |                    estimate                    |
+-----------+---------+---------+----------------------------+
| algorithm |    time |  memory |         parameters         |
+-----------+---------+---------+----------------------------+
| KMP       | 243.808 | 243.722 |         {'u': 24}          |
| SBC       | 241.319 | 236.722 | {'d': 1, 'w': 38, 'w1': 2} |
+-----------+---------+---------+----------------------------+