
Carte de visite

Grade:

Agrégé Docteur Normalien en informatique 
Lieu(x) de travail:

Équipe Algorithmique, GREYC, Ensicaen.
Laboratoire de Cryptologie Algorithmique, EPFL, Suisse

Email:

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
Aurore Bernard, Nicolas Gama
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 BonehDurfeeHowgrave Graham's algorithm which finds small rational roots of a polynomial modulo unknown
divisors. Such algorithm can also be used to speedup factorization of pq^r for large r.

8 
EE 
Lattice Enumeration using Extreme Pruning
Nicolas Gama, Phong Nguyen, Oded Regev
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
publickey 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
Jean Vuillemin, Nicolas Gama:
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 mirrorbased
minimization method for deterministic automata, and algorithms based
on stateequivalence.

2008 
6 
EE 
Finding Short Lattice vectors within Mordell's inequality.
Nicolas Gama,
Phong Q. Nguyen:
STOC 2008: 207216
The celebrated LenstraLenstraLová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 polynomialtime 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, HowgraveGraham, Koy and Nguyen.
Furthermore, we show that this approximation factor is essentially tight in the worst case.

5 
EE 
Predicting Lattice Reduction.
Nicolas Gama,
Phong Q. Nguyen:
Eurocrypt 2008: 3151
Despite their popularity,
lattice reduction algorithms remain mysterious cryptanalytical tools.
Though it is wellknown that they behave better than their proved worstcase theoretical bounds,
no precise assessment has ever been given.
Such an assessment would be very helpful to predict the behaviour of latticebased attacks,
as well as to select keysizes for latticebased 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 GGHchallenges
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 ChosenCiphertext Attacks on NTRU.
Nicolas Gama,
Phong Q. Nguyen:
Public Key Cryptography 2007: 89106
We present new and efficient keyrecovery chosenciphertext attacks on NTRUencrypt. Our attacks are somewhat intermediate between chosenciphertext 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 NTRU1998 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.
Nicolas Gama,
Nick HowgraveGraham,
Henrik Koy,
Phong Q. Nguyen
CRYPTO 2006: 112130
Lattice reduction is a hard problem of interest to both publickey 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 socalled 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.
Nicolas Gama,
Nick
HowgraveGraham,
Phong
Q. Nguyen
EUROCRYPT
2006: 233253
NTRU is a very efficient publickey 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 socalled 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, GramSchmidt, 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 GramSchmidt 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 ObjectOriented Application for 3D Electromagnetism.
Laurent
Baduel,
Françoise
Baude,
Denis
Caromel,
Christian
Delbé,
Nicolas Gama,
Said
El Kasmi,
Stéphane
Lanteri
IPDPS
2004
Within the trend of objectbased 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
objectoriented 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...)
