CryptoDB
Paul Kirchner
Publications
Year
Venue
Title
2020
EUROCRYPT
Key Recovery from Gram--Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices
📺
Abstract
In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold.
First, we identify a specific source of side-channel leakage in most implementations of those schemes, namely, the one-dimensional Gaussian sampling steps within lattice Gaussian sampling. It turns out that the implementations of these steps often leak the Gram--Schmidt norms of the secret lattice basis.
Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram--Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field.
Third, we concretely demonstrate the side-channel attack against DLP (but not Falcon due to the different structures of the two schemes). The challenge is that timing information only provides an approximation of the Gram--Schmidt norms, so our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximate values. Experimentally, we show that around $2^{35}$ DLP traces are enough to reconstruct the entire key with good probability.
2020
CRYPTO
Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))
📺
Abstract
We give a lattice reduction algorithm that achieves root Hermite factor k^(1/(2k)) in time k^(k/8 + o(k)) and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time k^(k/(2e) + o(k)). A cost of k^(k/8 + o(k)) was previously mentioned as potentially achievable (Hanrot-Stehlé’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below k^(k/8 + o(k)) for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.
2020
CRYPTO
Fast reduction of algebraic lattices over cyclotomic fields
📺
Abstract
We introduce a framework generalizing lattice reduction algorithms to module
lattices in order to \emph{practically} and \emph{efficiently} solve the
$\gamma$-Hermite Module-SVP problem over arbitrary cyclotomic fields. The core
idea is to exploit the structure of the subfields for designing a recursive
strategy of reduction in the tower of fields we are working in. Besides, we
demonstrate how to leverage the inherent symplectic geometry existing such
fields to provide a significant speed-up of the reduction for rank two
modules. As a byproduct, we also generalize to all cyclotomic fields and
provide speedups for many previous number theoretical algorithms, in
particular to the rounding in the so-called Log-unit lattice. Quantitatively,
we show that a module of rank 2 over a cyclotomic field of degree $n$ can be
heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time
$\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large
enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last
result is particularly striking as it goes below the estimate of $n^2B$ swaps
given by the classical analysis of the LLL algorithm using the decrease of
the \emph{potential} of the basis. Finally, all this framework is fully parallelizable, and we
provide a full implementation. We apply it to break multilinear cryptographic
candidates on concrete proposed parameters. We were able to reduce matrices of
dimension 4096 with 6675-bit integers in 4 days, which is more than a million
times faster than previous state-of-the-art implementations. Eventually, we
demonstrate a quasicubic time for the Gentry-Szydlo algorithm which finds a
generator given the relative norm and a basis of an ideal. This algorithm is
important in cryptanalysis and requires efficient ideal multiplications and
lattice reductions; as such we can practically use it in dimension 1024.
Coauthors
- Martin R. Albrecht (1)
- Shi Bai (1)
- Jean-François Biasse (1)
- Thomas Espitau (2)
- Pierre-Alain Fouque (8)
- Alexandre Gélin (1)
- Pierre Karpman (1)
- Brice Minaud (1)
- Damien Stehlé (1)
- Mehdi Tibouchi (1)
- Alexandre Wallet (1)
- Weiqiang Wen (1)
- Yang Yu (1)