pk_problem

class cryptographic_estimators.PKEstimator.pk_problem.PKProblem(n: int, m: int, q: int, ell=1, **kwargs)

Bases: BaseProblem

Construct an instance of the Permuted Kernel Problem.

Parameters:

  • n (int) – Columns of the matrix.

  • m (int) – Rows of the matrix.

  • q (int) – Size of the field.

  • ell (int, optional) – Number of rows of the matrix whose permutation should lie in the kernel. Defaults to 1.

  • **kwargs –

    Additional keyword arguments.

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

    nsolutions (int) - Number of solutions of the problem in logarithmic scale. Defaults to expected_number_solutions.

expected_number_solutions()

Returns the logarithm of the expected number of existing solutions to the problem.

get_parameters()

Return the optimizations parameters.

to_bitcomplexity_memory(elements_to_store: float)

Returns the memory bit-complexity associated to a given number of elements to store.

Parameters:

elements_to_store (float) – Number of Fq elements the algorithm needs to store (logarithmic)

to_bitcomplexity_time(basic_operations: float)

Returns the bit-complexity corresponding to basic_operations field additions.

Parameters:

basic_operations (float) – Number of Fq additions (logarithmic)