Page web de Nicolas Gama

Carte de visite

me Grade: Agrégé Docteur Normalien en informatique
Lieu(x) de travail: Équipe Algorithmique, GREYC, Ensicaen.
Laboratoire de Cryptologie Algorithmique, EPFL, Suisse
E-mail: HIDDEN
Fax: 09 59 14 93 10
CV/Resume: CV en Français

Publications.

2010
9 EE Smallest Reduction Matrix of Binary Quadratic Forms and Cryptographic Applications

ANTS 2010:

We present a variant of the Gauss reduction of quadratic forms designed to minimize the norm of the reduction matrix within a quadratic complexity. The matrix computed by ´ ¯ our algorithm on the input f has norm O (||f||^1/2 / Discriminant^1/4), which is the square root of the best previously known bounds using classical algorithms. This new bound allows us to fully prove the heuristic lattice based attack against NICE Cryptosystems, which consists in factoring a particular subclass of integers of the form pq^2 . In the process, we set up a homogeneous variant of Boneh-Durfee-Howgrave Graham's algorithm which finds small rational roots of a polynomial modulo unknown divisors. Such algorithm can also be used to speed-up factorization of pq^r for large r.

8 EE Lattice Enumeration using Extreme Pruning

Eurocrypt 2010:

Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.

2009
7 EE Compact normal form for regular languages as Xor Automata

CIAA 2009:

The only presently known normal form for a regular language L in Reg is its Minimal Deterministic Automaton MDA(L). We show that a regular language is also characterized by a finite dimension dim(L), which is always smaller than the number |MDA(L)| of states, and often exponentially so. The dimension is also the minimal number of states of all Nondeterministic Xor Automaton (NXA) which accept the language. NXAs combine the advantages of deterministic automata (normal form, negation, minimization, equivalence of states, accessibility) and of nondeterministic ones (compactness, mirror language). We present an algorithmic construction of the Minimal Non Deterministic Xor Automaton MXA(L), in cubic time from any NXA for L in Reg. The MXA provides another normal form: L=L'<=>MXA(L)=MXA(L'). Our algorithm establishes a missing connection between Brzozowski's mirror-based minimization method for deterministic automata, and algorithms based on state-equivalence.

2008
6 EE Finding Short Lattice vectors within Mordell's inequality.

STOC 2008: 207-216

The celebrated Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL) can naturally be viewed as an algorithmic version of Hermite's inequality on Hermite's constant. We present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of Mordell's inequality on Hermite's constant. This achieves a better and more natural approximation factor for the shortest vector problem than Schnorr's algorithm and its transference variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation factor is essentially tight in the worst case.

5 EE Predicting Lattice Reduction.

Eurocrypt 2008: 31-51

Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it is well-known that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. Interestingly, the conjectures seem consistent with past cryptanalytical experiments on the GGH-challenges and NTRU lattices. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.

2007
4 EE New Chosen-Ciphertext Attacks on NTRU.

Public Key Cryptography 2007: 89-106

We present new and efficient key-recovery chosen-ciphertext attacks on NTRUencrypt. Our attacks are somewhat intermediate between chosen-ciphertext attacks on NTRUencrypt previously published at CRYPTO '00 and CRYPTO '03. Namely, the attacks only work in the presence of decryption failures; we only submit valid ciphertexts to the decryption oracle, where the plaintexts are chosen uniformly at random; and the number of oracle queries is small. Interestingly, our attacks can also be interpreted from a provable security point of view: in practice, if one had access to a NTRUencrypt decryption oracle such that the parameter set allows decryption failures, then one could recover the secret key. For instance, for the initial NTRU-1998 parameter sets, the output of the decryption oracle on a single decryption failure is enough to recover the secret key.

2006
3 EE Rankin's Constant and Blockwise Lattice Reduction.

CRYPTO 2006: 112-130

Lattice reduction is a hard problem of interest to both public-key cryptography and cryptanalysis. Despite its importance, extremely few algorithms are known. The best algorithm known in high dimension is due to Schnorr, proposed in 1987 as a block generalization of the famous LLL algorithm. This paper deals with Schnorr's algorithm and potential improvements. We prove that Schnorr's algorithm outputs better bases than what was previously known: namely, we decrease all former bounds on Schnorr's approximation factors to their (ln 2)-th power. On the other hand, we also show that the output quality may have intrinsic limitations, even if an improved reduction strategy was used for each block, thereby strengthening recent results by Ajtai. This is done by making a connection between Schnorr's algorithm and a mathematical constant introduced by Rankin more than 50 years ago as a generalization of Hermite's constant. Rankin's constant leads us to introduce the so-called smallest volume problem, a new lattice problem which generalizes the shortest vector problem, and which has applications to blockwise lattice reduction generalizing LLL and Schnorr's algorithm, possibly improving their output quality. Schnorr's algorithm is actually based on an approximation algorithm for the smallest volume problem in low dimension. We obtain a slight improvement over Schnorr's algorithm by presenting a cheaper approximation algorithm for the smallest volume problem, which we call transference reduction.

2 EE Symplectic Lattice Reduction and NTRU.

EUROCRYPT 2006: 233-253

NTRU is a very efficient public-key cryptosystem based on polynomial arithmetic. Its security is related to the hardness of lattice problems in a very special class of lattices. This article is motivated by an interesting peculiar property of NTRU lattices. Namely, we show that NTRU lattices are proportional to the so-called symplectic lattices. This suggests to try to adapt the classical reduction theory to symplectic lattices, from both a mathematical and an algorithmic point of view. As a first step, we show that orthogonalization techniques (Cholesky, Gram-Schmidt, QR factorization, etc.) which are at the heart of all reduction algorithms known, are all compatible with symplecticity, and that they can be significantly sped up for symplectic matrices. Surprisingly, by doing so, we also discover a new integer Gram-Schmidt algorithm, which is faster than the usual algorithm for all matrices. Finally, we study symplectic variants of the celebrated LLL reduction algorithm, and obtain interesting speed ups.

2004
1 EE A Parallel Object-Oriented Application for 3D Electromagnetism.

IPDPS 2004

Within the trend of object-based distributed computing, we present the design and implementation of a numerical simulation for electromagnetic waves propagation. A sequential Java design and implementation is first presented. Further, a distributed and parallel version is derived from the first, using an active object pattern. In addition, benchmarks are presented on this non embarrassingly parallel application. A first contribution of this paper resides in the sequential object-oriented design that proved to be very modular and extensible; the classes and abstractions are designed to allow both element and volume type methods, furthermore, valid on structured, unstructured, or hybrid meshes. Compared to a Fortran version, the performance of this highly modular version proved to be in the same range. It is also shown how smoothly the sequential version can be distributed, keeping the same structuring and object abstractions, allowing to deal with larger data size. Finally, benchmarks on up to 64 processors compare the performances with respect to sequential and parallel versions, putting that in perspective with a comparable Fortran version.

Thèse de Doctorat

Géométrie des nombres et Cryptanalyse de NTRU

La cryptographie à clef publique, inventée par Diffie et Hellman en 1976, fait aujourd'hui partie de la vie courante : les cartes bleues, les consoles de jeux et le commerce électronique par exemple utilisent des mécanismes de cryptographie à clef publique. La sécurité de certains cryptosystèmes, comme NTRU, repose sur des problèmes issus de la géométrie des nombres, et notamment les problèmes de plus court vecteur ou de plus proche vecteur dans des réseaux euclidiens. (suite...)