103 views

Skip to first unread message

Dec 11, 2020, 8:56:07 PM12/11/20

to pqc-forum

Dear Dan, all,

I'd like to extract the discussion about asymptotic security

comparisons from the longer Classic McEliece thread as

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%.

>>> 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.

>> 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.

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.

> 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

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.

> 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

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.

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu