Laboratoire IMATH

par Andrea Lesavourey

Titre :

Diagonally dominant matrices in cryptography

Résumé :

Euclidean lattices are among the most promising objects for building a post-quantum cryptography,
i.e. constructions that would resist the power of large scale quantum computers. For efficiency
reasons, most constructions use lattices enjoying a strong algebraic structure, and can be
interpreted as constructions over polynomials with rational coefficients. However, it is still
unknown to this date to what extent this additional structure can be used to attack those
cryptosystems. Thus, studying more generic lattices is still an important challenge for future
cryptography.
Plantard et al. (2016) submitted a scheme called DRS to the NIST process aiming at standardising
post-quantum cryptography, based on diagonally dominant matrices. However, it suffered a different
learning attack from Ducas and Yu (2017), lowering the security estimates by at least 30 bits.

In this talk, I will first give some background on Euclidean lattices and their use in
cryptography. Then I will describe GGH-like schemes and statistical attacks known on these
constructions. Finally I will present a recent joint work with T. Plantard and A. Sipasseuth
published in Communication in Cryptography (CiC), where we study diagonally dominant matrices (as
in the DRS scheme) and their use in cryptography.