Asymptotic security comparisons

[Kirk Fleming]

Dear Dan, all,

 

I'd like to extract the discussion about asymptotic security
comparisons from the longer Classic McEliece thread as

it is a separate issue.

 

Dan Bernstein (on behalf of the Classic McEliece team) wrote:
>>> The graph in https://video.cr.yp.to/2020/0813/video.html
>>> shows that asymptotic lattice security levels against
>>> attacks known 10 years ago were 42% higher than lattice
>>> security levels against attacks known today (for otherwise
>>> unbroken lattice systems), while for McEliece's system the
>>> change is 0%.

 

Kirk Fleming wrote:
>> You are ignoring asymptotic improvements to half-distance
>> decoding because McEliece uses errors with sublinear weight
>> yet compare it with asymptotic improvements to the exact short
>> vector problem even though lattice schemes depend on different
>> variants of the problem.

 

My point is that Dan is making a false comparison between a
specific cryptosystem (McEliece) and the hard problem for a wide
family of cryptosystems (lattices) without first clearly defining the
asymptotic parameters.

 

Dan Bernstein (speaking for himself) wrote:
> Consider https://eprint.iacr.org/2017/1139.pdf reporting
> exponent 0.0465 for half-distance decoding, where Prange's
> algorithm from 51 years earier was exponent 0.0576; see the
> paper for a survey of intermediate results. This asymptotic
> 24% change corresponds to an asymptotic 0% change in the
> asymptotic security level of McEliece's system.

 

Dan is implicitly equating "McEliece's system" with information
set decoding for parameters n, k = Theta(n) and either

t = O(n/log n) for binary Goppa codes or t = O(sqrt(n)) for MDPC

codes. The result is then from Canto Torres and Sendrier.

 

> Basically, the lattice attacks are bottlenecked by BKZ, and
> BKZ is bottlenecked by a relatively short series of expensive
> shortest-vector searches in a lower dimension (beta, the "block
> size"), so if the SVP solution loses P% of its asymptotic bits
> of security then the whole attack loses P% of its asymptotic
> bits of security.

 

Whoa! There is a huge gap in the logic here. Dan is not being
precise about the asymptotic parameters for this "(otherwise
unbroken) lattice system" yet claims that the block size will
always be beta = Theta(n). If Dan is using the results from
Herold, Kirshanova and May's "On the asymptotic complexity of
solving LWE" then he needs to give them credit for their work

and be clear about which lattice systems are covered by it.

 

Herold, Kirshanova and May assume an LWE scheme with asymptotic
parameters n, q = O(n^c) and s = O(n^d), for constants d < c, that
reveals m = Theta(n) samples. It says nothing about parameters
q = O(2^(n/2)), s = O(sqrt(n)) satisfying the classical reduction
for LWE by Peikert. More work is needed to check that it applies
to parameters q = O(n^c), s = omega(sqrt(log n)) closer to those
in the LWE submissions to NIST. It does not mention NTRU at all.

 

Kirk