CRYPTO : Kévin Carrier (CY Cergy-Paris Université) : Faster Dual Lattice Attacks by Using Coding Theory

1 décembre 2022 / 11:00 - 12:00

We present a faster dual lattice attack on the Learning with

Errors (LWE) problem, based on ideas from coding theory. Basically, it

consists in revisiting the most classical dual attack by replacing

modulus switching by a decoding algorithm. This replacement achieves a

reduction from small LWE to plain LWE with a very significant reduction

of the secret dimension. We also replace the enumeration part of this

attack by betting that the secret is zero on the part where we want to

enumerate it and iterate this bet over other choices of the enumeration

part.We estimate the complexity of this attack by making the optimistic,

but realistic guess that we can use polar codes for this decoding task. We

show that under this assumption the best attacks on Kyber and Saber

can be improved by 1 and 6 bits.

CRYPTO : Kévin Carrier (CY Cergy-Paris Université) : Faster Dual Lattice Attacks by Using Coding Theory