International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Thomas Prest

Affiliation: Thales Communications & Security

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.
2019
CRYPTO
Unifying Leakage Models on a Rényi Day
In the last decade, several works have focused on finding the best way to model the leakage in order to obtain provably secure implementations. One of the most realistic models is the noisy leakage model, introduced in [PR13, DDF14] together with secure constructions. These works suffer from various limitations, in particular the use of ideal leak-free gates in [PR13] and an important loss (in the size of the field) in the reduction in [DDF14].In this work, we provide new strategies to prove the security of masked implementations and start by unifying the different noisiness metrics used in prior works by relating all of them to a standard notion in information theory: the pointwise mutual information. Based on this new interpretation, we define two new natural metrics and analyze the security of known compilers with respect to these metrics. In particular, we prove (1) a tighter bound for reducing the noisy leakage models to the probing model using our first new metric, (2) better bounds for amplification-based security proofs using the second metric.To support that the improvements we obtain are not only a consequence of the use of alternative metrics, we show that for concrete representation of leakage (e.g., “Hamming weight + Gaussian noise”), our approach significantly improves the parameters compared to prior works. Finally, using the Rényi divergence, we quantify concretely the advantage of an adversary in attacking a block cipher depending on the number of leakage acquisitions available to it.
2017
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2014
ASIACRYPT