search

lducas / leaky-LWE-Estimator

A sage Toolkit for mounting/estimating attacks on LWE with Side Information
37 stars 16 forks source link

Full DBDD instances for NTRU #3

Closed lducas closed 3 years ago

lducas commented 3 years ago

It is now possible to create full DBDD instances (i.e. actually constructing the lattice), and therefore to test prediction on such instances. It turns out that they seems accurate indeed (see discussion at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/2WbXPO-07TY)

modulus q=512
secrets/errors: uniform ternary
prime n

LWE (m=n)

n,         exp. β,    pred.  β

37,      2.000,     2.000
41,      2.000,     2.000
47,      2.000,     2.035
53,      2.350,     2.596
59,      5.310,     5.736
67,      12.220,    15.020    
71,      17.560,    19.665    
79,      25.880,    27.583
83,      29.920,    31.315
89,      36.740,    36.733
97,      42.870,    43.781
101,     46.820,    47.228
107,     52.620,    52.637
113,     58.880,    58.546

NTRU

n,         exp. β,    pred.  β

37,      2.000,     2.000
41,      2.000,     2.000
47,      2.000,     2.000
53,      2.000,     2.000
59,      2.010,     2.000
67,      2.320,     4.205
71,      2.820,     9.000
79,      9.530,     19.233
83,      15.390,    23.193
89,      23.340,    28.832
97,      31.650,    36.104
101,     35.990,    39.510
107,     42.580,    44.663
113,     48.630,    49.643