International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Thomas Pornin

Affiliation: NCC Group

Publications

Year
Venue
Title
2019
PKC
More Efficient Algorithms for the NTRU Key Generation Using the Field Norm
Thomas Pornin Thomas Prest
NTRU lattices [13] are a class of polynomial rings which allow for compact and efficient representations of the lattice basis, thereby offering very good performance characteristics for the asymmetric algorithms that use them. Signature algorithms based on NTRU lattices have fast signature generation and verification, and relatively small signatures, public keys and private keys.A few lattice-based cryptographic schemes entail, generally during the key generation, solving the NTRU equation: $$\begin{aligned} f G - g F = q \mod x^n + 1 \end{aligned}$$Here f and g are fixed, the goal is to compute solutions F and G to the equation, and all the polynomials are in $${\mathbb {Z}}[x]/(x^n + 1)$$. The existing methods for solving this equation are quite cumbersome: their time and space complexities are at least cubic and quadratic in the dimension n, and for typical parameters they therefore require several megabytes of RAM and take more than a second on a typical laptop, precluding onboard key generation in embedded systems such as smart cards.In this work, we present two new algorithms for solving the NTRU equation. Both algorithms make a repeated use of the field norm in tower of fields; it allows them to be faster and more compact than existing algorithms by factors $${\tilde{O}}(n)$$. For lattice-based schemes considered in practice, this reduces both the computation time and RAM usage by factors at least 100, making key pair generation within range of smart card abilities.
2015
EPRINT
2007
FSE
2007
JOFC
2004
CRYPTO
2003
EPRINT
Did Filiol Break AES ?
On January 8th 2003, Eric Filiol published on the eprint a paper (eprint.iacr.org/2003/003/) in which he claims that AES can be broken by a very simple and very fast ciphertext-only attack. If such an attack existed, it would be the biggest discovery in code-breaking since some 10 or more years. Unfortunately the result is very hard to believe. In this paper we present the results of computer simulations done by several independent people, with independently written code. Nobody has confirmed a single anomaly in AES, even for much weaker versions of the bias claimed by the author. We also studied the source code provided by the author to realize that the first version had various issues and bugs, and the latest version still does not confirm the claimed result on AES.
2001
CHES
2000
CHES
1998
ASIACRYPT

Program Committees

CHES 2019