|
|
Carte de visite
|
Grade:
|
Agrégé Docteur Normalien en informatique |
| Lieu(x) de travail:
|
Université de Versailles, France |
| E-mail:
|
HIDDEN |
| CV/Resume: |
CV en Français |
Publications.
Nicolas GamaMalika IzabachènePhong Q. NguyenXiang XieStructural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions.28320142014IACR Cryptology ePrint Archivehttp://eprint.iacr.org/2014/283db/journals/iacr/iacr2014.html#GamaINX14
Anja Becker
Nicolas Gama
Antoine Joux
Solving shortest and closest vector problems: The decomposition approach.
685
2013
2013
IACR Cryptology ePrint Archive
http://eprint.iacr.org/2013/685
db/journals/iacr/iacr2013.html#BeckerGJ13
Nadia El Mrabet
Nicolas Gama
Efficient Multiplication over Extension Fields.
136-151
2012
WAIFI
http://dx.doi.org/10.1007/978-3-642-31662-3_10
conf/waifi/2012
db/conf/waifi/waifi2012.html#MrabetG12
Vivien DuboisNicolas GamaThe Degree of Regularity of HFE Systems.557-5762010ASIACRYPThttp://dx.doi.org/10.1007/978-3-642-17373-8_32conf/asiacrypt/2010db/conf/asiacrypt/asiacrypt2010.html#DuboisG10
Aurore BernardNicolas GamaSmallest Reduction Matrix of Binary Quadratic Forms.32-492010ANTShttp://dx.doi.org/10.1007/978-3-642-14518-6_7conf/ants/2010db/conf/ants/ants2010.html#BernardG10
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.
Nicolas GamaPhong Q. NguyenOded RegevLattice Enumeration Using Extreme Pruning.257-2782010EUROCRYPThttp://dx.doi.org/10.1007/978-3-642-13190-5_13conf/eurocrypt/2010db/conf/eurocrypt/eurocrypt2010.html#GamaNR10Lattice 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.
Jean VuilleminNicolas GamaCompact Normal Form for Regular Languages as Xor Automata.24-332009CIAAhttp://dx.doi.org/10.1007/978-3-642-02979-0_6conf/wia/2009db/conf/wia/ciaa2009.html#VuilleminG09The 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.
Nicolas GamaPhong Q. NguyenPredicting Lattice Reduction.31-512008EUROCRYPThttp://dx.doi.org/10.1007/978-3-540-78967-3_3conf/eurocrypt/2008db/conf/eurocrypt/eurocrypt2008.html#GamaN08Despite 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.
Nicolas GamaPhong Q. NguyenFinding short lattice vectors within mordell's inequality.207-2162008STOChttp://doi.acm.org/10.1145/1374376.1374408conf/stoc/2008db/conf/stoc/stoc2008.html#GamaN08The 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.
Nicolas GamaPhong Q. NguyenNew Chosen-Ciphertext Attacks on NTRU.89-1062007conf/pkc/2007Public Key Cryptographyhttp://dx.doi.org/10.1007/978-3-540-71677-8_7db/conf/pkc/pkc2007.html#GamaN07We 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.
Nicolas GamaNick Howgrave-GrahamHenrik KoyPhong Q. NguyenRankin's Constant and Blockwise Lattice Reduction.112-1302006conf/crypto/2006CRYPTOhttp://dx.doi.org/10.1007/11818175_7db/conf/crypto/crypto2006.html#GamaHKN06
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.
Nicolas GamaNick Howgrave-GrahamPhong Q. NguyenSymplectic Lattice Reduction and NTRU.233-2532006conf/eurocrypt/2006EUROCRYPThttp://dx.doi.org/10.1007/11761679_15db/conf/eurocrypt/eurocrypt2006.html#GamaHN06NTRU 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.
Laurent BaduelFrançoise BaudeDenis CaromelChristian DelbéNicolas GamaSaid El KasmiStéphane LanteriA Parallel Object-Oriented Application for 3D Electromagnetism.2004conf/ipps/2004IPDPShttp://dx.doi.org/10.1109/IPDPS.2004.1302908http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1302908db/conf/ipps/ipdps2004-c.html#BaduelBCDGKL04
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...)
|
