## CryptoDB

### Paul Kirchner

#### Publications

**Year**

**Venue**

**Title**

2023

ASIACRYPT

We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve
Abstract

The Number Field Sieve (NFS) is the state-of-the art algorithm for integer
factoring, and sieving is a crucial step in the NFS. It is a very
time-consuming operation, whose goal is to collect many relations. The
ultimate goal is to generate random smooth integers mod $N$ with their prime
decomposition, where smooth is defined on the rational and algebraic sides
according to two prime factor bases.
In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split into
different stages depending on the size of the primes, but defining good
parameters for all stages is based on heuristic and practical arguments. At
the beginning, candidates are sieved by small primes on both sides, and if
they pass the test, they continue to the next stages with bigger primes, up to
the final one where we factor the remaining part using the ECM algorithm. On
the one hand, first stages are fast but many false relations pass them, and we
spend a lot of time with useless relations. On the other hand final stages are
more time demanding but outputs less relations. It is not easy to evaluate the
performance of the best strategy on the overall sieving step since it depends
on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up
this step since many improvements have been done on all other steps of the
NFS. Based on the relations collected during the RSA-250 factorization and all
parameters, we try to study different strategies to better understand this
step. Many strategies have been defined since the discovery of NFS, and we
provide here an experimental evaluation.

2022

TCHES

BAT: Small and Fast KEM over NTRU Lattices
Abstract

We present BAT – an IND-CCA secure key encapsulation mechanism (KEM) that is based on NTRU but follows an encryption/decryption paradigm distinct from classical NTRU KEMs. It demonstrates a new approach of decrypting NTRU ciphertext since its introduction 25 years ago. Instead of introducing an artificial masking parameter p to decrypt the ciphertext, we use 2 linear equations in 2 unknowns to recover the message and the error. The encryption process is therefore close to the GGH scheme. However, since the secret key is now a short basis (not a vector), we need to modify the decryption algorithm and we present a new NTRU decoder. Thanks to the improved decoder, our scheme works with a smaller modulus and yields shorter ciphertexts, smaller than RSA-4096 for 128-bit classical security with comparable public-key size and much faster than RSA or even ECC. Meanwhile, the encryption and decryption are still simple and fast in spite of the complicated key generation. Overall, our KEM has more compact parameters than all current lattice-based schemes and a practical efficiency. Moreover, due to the similar key pair structure, BAT can be of special interest in some applications using Falcon signature that is also the most compact signature in the round 3 of the NIST post-quantum cryptography standardization. However, different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.

2021

CRYPTO

Towards faster polynomial-time lattice reduction
📺
Abstract

The LLL algorithm is a polynomial-time algorithm for reducing d-dimensional lattice with exponential approximation factor. Currently, the most efficient variant of LLL, by Neumaier and Stehl\'e, has a theoretical running time in $d^4\cdot B^{1+o(1)}$ where $B$ is the bitlength of the
entries, but has never been implemented. This work introduces new asymptotically fast, parallel, yet heuristic, reduction algorithms with their optimized implementations. Our algorithms are recursive and fully exploit fast block matrix multiplication. We experimentally demonstrate that by carefully controlling the floating-point precision during the recursion steps, we can reduce euclidean lattices of rank d in time $\tilde{O}(d^\omega\cdot C)$, i.e., almost a constant number of matrix multiplications, where $\omega$ is the exponent of matrix multiplication and C is the log of the condition number of the matrix. For cryptographic applications, C is close to B, while it can be up to d times larger in the worst case. It improves the running-time of the state-of-the-art implementation fplll by a multiplicative factor of order $d^2\cdot B$. Further, we show that we can reduce structured lattices, the so-called knapsack lattices, in time $\tilde{O}(d^{\omega-1}\cdot C)$ with a progressive reduction strategy. Besides allowing reducing huge lattices, our implementation can break several instances of Fully Homomorphic Encryption schemes based
on large integers in dimension 2,230 with 4 millions of bits.

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)
- Charles Bouillaguet (1)
- Thomas Espitau (3)
- Ambroise Fleury (1)
- Pierre-Alain Fouque (10)
- Alexandre Gélin (1)
- Pierre Karpman (1)
- Paul Kirchner (10)
- Brice Minaud (1)
- Thomas Pornin (1)
- Damien Stehlé (1)
- Mehdi Tibouchi (1)
- Alexandre Wallet (1)
- Weiqiang Wen (1)
- Yang Yu (2)