estimator.lwe_guess.guess_composition.gammaf

estimator.lwe_guess.guess_composition.gammaf#

classmethod guess_composition.gammaf(n, h, zeta, base, g=<function guess_composition.<lambda>>)[source]#

Find optimal hamming weight for sparse guessing.

Let s be a vector of dimension n where we expect h non-zero entries. We are ignoring η-γ components and are guessing γ. This succeeds with some probability given by prob_drop(n, h, ζ, γ). Exhaustively searching the guesses takes binomial(n, γ) ⋅ b^γ steps where b is the number of non-zero values in a component of s. We call a γ optimal if it minimizes the overall number of repetitions that need to be performed to succeed with probability 99%.

Parameters:
  • n – vector dimension

  • h – hamming weight of the vector

  • zeta – number of ignored + guesses components

  • base – number of possible non-zero scalars

  • g – We do not consider search space directly by g() applied to it (think time-memory trade-offs).

Returns:

(number of repetitions, γ, size of the search space, probability of success)