Project : cascade

Section: Overall Objectives

Highlights

Foundation: Finding Short Lattice Vectors Within Mordell's Inequality

The shortest vector problem (SVP) in a lattice is a famous NP-hard problem of interest to both public-key cryptography and public-key cryptanalysis. Despite its importance, extremely few algorithms are known. This article presents the best polynomial-time algorithm known for approximating SVP. The algorithm, called slide reduction, has a natural interpretation: it can be viewed as an algorithmic version of a mathematical inequality proved by Mordell back in 1944.

The first polynomial-time algorithm for approximating SVP is the celebrated LLL algorithm, published by Lenstra, Lenstra and Lovász in 1982, and referenced by thousands of articles since: the historical applications of LLL were integer programming in fixed dimension, factoring polynomial with rational coefficients, and Diophantine approximation. The LLL algorithm is arguably best described as an algorithmic version of a mathematical inequality discovered by Hermite in 1850, which proved the existence of a constant related to lattice packings, now known as Hermite's constant. The principles and the worst-case output quality of the LLL algorithm are tightly related to Hermite's inequality.

In 1944, Mordell found a simple generalization of Hermite's inequality, which gave rise to better upper bounds on Hermite's constant. This article presents the first true algorithmic analogue of Mordell's inequality: the algorithm is to Mordell's inequality what LLL is to Hermite's inequality. As such, the new algorithm can be viewed as the “right” blockwise generalization of the LLL algorithm. Furthermore, it is simpler than previous blockwise generalizations of LLL, and a tight worst-case analysis is known.

Cryptanalysis: Cryptanalysis of SFLASH

Multivariate cryptography is a field of public-key cryptography which provides alternative schemes to RSA or Discrete-Log based schemes. The advantages of these schemes are twofold: they are extremely fast, even on low power devices since no cryptographic coprocessor is needed; and their security is related to a problem for which no quantum polynomial time algorithm is known. In 2003, the NESSIE project thus recommended the SFLASH signature scheme as a good scheme with high security level. This scheme has been proposed by Patarin, Goubin and Courtois in 2001. In multivariate cryptography, the public key is a system of multivariate polynomials over a small finite field. To sign a message with SFLASH, a trapdoor allows the legitimate user to invert the system, while the verification is very easy since it only requires to evaluate the system. The project-team CASCADE proposed in 2007 two attacks against SFLASH. These attacks are very efficient in practice since they require 3 minutes to break the parameters. The attacks allow an adversary to find a signature for any message. They only use linear and bilinear algebra and are based on some properties of the differential functions associated to the system of the public key. Studying the differential functions has also been proposed by the project-team CASCADE in 2005 and allowed to cryptanalyze an encryption scheme whose security is related those of the SFLASH signature scheme. Finally, these attacks were recently extended and allow to recover equivalent secret keys on SFLASH and on other traitor tracing schemes based on other multivariate problems.