estimator.lwe_bkw.CodedBKW
estimator.lwe_bkw.CodedBKW#
- class estimator.lwe_bkw.CodedBKW[source]#
- __call__(params: estimator.lwe_parameters.LWEParameters, ntest=None, log_level=1)[source]#
Coded-BKW as described in [C:GuoJohSta15].
- Parameters
params – LWE parameters
ntest – Number of coordinates to hypothesis test.
- Returns
A cost dictionary
The returned cost dictionary has the following entries:
rop
: Total number of word operations (≈ CPU cycles).b
: BKW tables have size q^b.t1
: Number of plain BKW tables.t2
: Number of Coded-BKW tables.ℓ
: Hypothesis testing has tables of size q^{ℓ+1}#cod
: Number of coding steps.#top
: Number of guessing steps (typically zero)#test
: Number of coordinates to do hypothesis testing on.
EXAMPLE:
>>> from sage.all import oo >>> from estimator import * >>> LWE.coded_bkw(schemes.LightSaber.updated(m=oo)) rop: ≈2^171.7, m: ≈2^159.4, mem: ≈2^160.4, b: 12, t1: 3, t2: 18, ℓ: 11, #cod: 423, #top: 1...
We may need to amplify the number of samples, which modifies the noise distribution:
>>> from sage.all import oo >>> from estimator import * >>> schemes.Kyber512 LWEParameters(n=512, q=3329, Xs=D(σ=1.22), Xe=D(σ=1.22), m=512, tag='Kyber 512') >>> cost = LWE.coded_bkw(schemes.Kyber512); cost rop: ≈2^178.8, m: ≈2^166.8, mem: ≈2^167.8, b: 14, t1: 0, t2: 16, ℓ: 13, #cod: 448, #top: 0, #test: 64, ... >>> cost["problem"] LWEParameters(n=512, q=3329, Xs=D(σ=1.22), Xe=D(σ=6.24), m=..., tag='Kyber 512')
TESTS:
>>> LWE.coded_bkw(schemes.TFHE630) rop: ≈2^144.7, m: ≈2^131.8, mem: ≈2^132.8, b: 4, t1: 0, t2: 27, ℓ: 3, #cod: 559, #top: 0, #test: 71, ...
Note
See also [C:KirFou15].
Methods
N
(i, sigma_set, b, q)Return N_i for the i-th [N_i, b] linear code.
__init__
()b
(params[, ntest, log_level])cost
(t2, b, ntest, params[, ...])Coded-BKW cost.
t1
(ell, t2, b[, ntest])We compute t1 from N_i by observing that any N_i ≤ b gives no advantage over vanilla BKW, but the estimates for coded BKW always assume quantisation noise, which is too pessimistic for N_i ≤ b.
Attributes