Project : cascade
Section: New Results
Cryptanalysis (Mathematical)
Participants : Vivien Dubois, Pierre-Alain Fouque, Phong Nguyen, Jacques Stern.
Cryptanalysis of SFLASH with Slightly Modified Parameters, EUROCRYPT '07
Practical Cryptanalysis of SFLASH, CRYPTO '07
Key Recovery on Hidden Monomial Multivariate Schemes, EUROCRYPT '08
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 two-folded: 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 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.
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, Journal of Cryptology 2008
Lattice-based signature schemes following the Goldreich-Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer's secret key, but this does not necessarily imply that such schemes are insecure. We present a practical and provable method to attack signature schemes à la GGH, by studying the following learning problem: given many random points uniformly distributed over an unknown n-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can provably be solved by a gradient descent. Our approach is very effective in practice: we present the first successful key-recovery experiments on NTRUsign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 400 signatures are sufficient to recover the NTRUsign-251 secret key, thanks to symmetries in NTRU lattices. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges.
