## CryptoDB

### Pierre-Alain Fouque

#### Publications

**Year**

**Venue**

**Title**

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

SSE and SSD: Page-Efficient Searchable Symmetric Encryption
📺
Abstract

Searchable Symmetric Encryption (SSE) enables a client to outsource a database to an untrusted server, while retaining the ability to securely search the data. The performance bottleneck of classic SSE schemes typically does not come from their fast, symmetric cryptographic operations, but rather from the cost of memory accesses. To address this issue, many works in the literature have considered the notion of locality, a simple design criterion that helps capture the cost of memory accesses in traditional storage media, such as Hard Disk Drives. A common thread among many SSE schemes aiming to improve locality is that they are built on top of new memory allocation schemes, which form the technical core of the constructions.
The starting observation of this work is that for newer storage media such as Solid State Drives (SSDs), which have become increasingly common, locality is not a good predictor of practical performance. Instead, SSD performance mainly depends on page efficiency, that is, reading as few pages as possible. We define this notion, and identify a simple allocation problem, Data-Independent Packing, that captures the main technical challenge required to build page-efficient SSE. As our main result, we build a page-efficient and storage-efficient data-independent packing scheme, and deduce an SSE scheme with the same properties. The technical core of the result is a new generalization of cuckoo hashing to items of variable size. Practical experiments show that this approach achieves excellent performance.

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

TCHES

The Long and Winding Path to Secure Implementation of GlobalPlatform SCP10
📺
Abstract

GlobalPlatform (GP) card specifications are defined for smart cards regarding rigorous security requirements. The increasingly more powerful cards within an open ecosystem of multiple players stipulate that asymmetric-key protocols become necessary. In this paper, we analyze SCP10, which is the Secure Channel Protocol (SCP) that relies on RSA for key exchange and authentication. Our findings are twofold. First, we demonstrate several flaws in the design of SCP10. We discuss the scope of the identified flaws by presenting several attack scenarios in which a malicious attacker can recover all the messages protected by SCP10. We provide a full implementation of these attacks. For instance, an attacker can get the freshly generated session keys in less than three hours. Second, we propose a secure implementation of SCP10 and discuss how it can mitigate the discovered flaws. Finally, we measure the overhead incurred by the implemented countermeasures.

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.

2020

TOSC

Fake Near Collisions Attacks
Abstract

Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials.In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory.

2020

TOSC

Increasing Precision of Division Property
Abstract

In this paper we propose new techniques related to division property. We describe for the first time a practical algorithm for computing the propagation tables of 16-bit Super-Sboxes, increasing the precision of the division property by removing a lot of false division trails. We also improve the complexity of the procedure introduced by Lambin et al. (Design, Codes and Cryptography, 2020) to extend a cipher with linear mappings and show how to decrease the number of transitions to look for. While search procedures for integral distinguishers most often rely on MILP or SAT solvers for their ease of programming the propagation constraints, such generic solvers can only handle small 4/8-bit Sboxes. Thus we developed an ad-hoc tool handling larger Sboxes and all the improvements described in the paper. As a result, we found new integral distinguishers on SKINNY-64, HIGHT and Midori-64.

2019

TOSC

Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks
📺
Abstract

The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were then proposed in the literature, leading to the Generalized Feistel Network, where the round function first applies a classical Feistel operation in parallel on an even number of blocks, and then a permutation is applied to this set of blocks. In 2010 at FSE, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. They thus gave some optimal permutations, with respect to this diffusion criteria, for a Generalized Feistel Network consisting of 2 to 16 blocks, as well as giving a good candidate for 32 blocks. Later at FSE’19, Cauchois et al. went further and were able to propose optimal even-odd permutations for up to 26 blocks.In this paper, we complete the literature by building optimal even-odd permutations for 28, 30, 32, 36 blocks which to the best of our knowledge were unknown until now. The main idea behind our constructions and impossibility proof is a new characterization of the total diffusion of a permutation after a given number of rounds. In fact, we propose an efficient algorithm based on this new characterization which constructs all optimal even-odd permutations for the 28, 30, 32, 36 blocks cases and proves a better lower bound for the 34, 38, 40 and 42 blocks cases. In particular, we improve the 32 blocks case by exhibiting optimal even-odd permutations with diffusion round of 9. The existence of such a permutation was an open problem for almost 10 years and the best known permutation in the literature had a diffusion round of 10. Moreover, our characterization can be implemented very efficiently and allows us to easily re-find all optimal even-odd permutations for up to 26 blocks with a basic exhaustive search

2018

TOSC

Revisiting and Improving Algorithms for the 3XOR Problem
Abstract

The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F,G and H and she has to find three inputs x, y and z such that F(x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem. Wagner’s celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly

2018

TCHES

On Recovering Affine Encodings in White-Box Implementations
Abstract

Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., other constructions were later built around the same framework. In this framework, the round function of the cipher is “encoded” by composing it with non-linear and affine layers known as encodings. However, all such attempts were broken by a series of increasingly efficient attacks that are able to peel off these encodings, eventually uncovering the underlying round function, and with it the secret key.These attacks, however, were generally ad-hoc and did not enjoy a wide applicability. As our main contribution, we propose a generic and efficient algorithm to recover affine encodings, for any Substitution-Permutation-Network (SPN) cipher, such as AES, and any form of affine encoding. For AES parameters, namely 128-bit blocks split into 16 parallel 8-bit S-boxes, affine encodings are recovered with a time complexity estimated at 232 basic operations, independently of how the encodings are built. This algorithm is directly applicable to a large class of schemes. We illustrate this on a recent proposal due to Baek, Cheon and Hong, which was not previously analyzed. While Baek et al. evaluate the security of their scheme to 110 bits, a direct application of our generic algorithm is able to break the scheme with an estimated time complexity of only 235 basic operations.As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 231. We also provide an implementation of the attack, which is able to recover the secret key in about 12 seconds on a standard desktop computer.

2018

ASIACRYPT

Pattern Matching on Encrypted Streams
Abstract

Pattern matching is essential in applications such as deep-packet inspection (DPI), searching on genomic data, or analyzing medical data. A simple task to do on plaintext data, pattern matching is much harder to do when the privacy of the data must be preserved. Existent solutions involve searchable encryption mechanisms with at least one of these three drawbacks: requiring an exhaustive (and static) list of keywords to be prepared before the data is encrypted (like in symmetric searchable encryption); requiring tokenization, i.e., breaking up the data to search into substrings and encrypting them separately (e.g., like BlindBox); relying on symmetric-key cryptography, thus implying a token-regeneration step for each encrypted-data source (e.g., user). Such approaches are ill-suited for pattern-matching with evolving patterns (e.g., updating virus signatures), variable searchword lengths, or when a single entity must filter ciphertexts from multiple parties.In this work, we introduce Searchable Encryption with Shiftable Trapdoors (SEST): a new primitive that allows for pattern matching with universal tokens (usable by all entities), in which keywords of arbitrary lengths can be matched to arbitrary ciphertexts. Our solution uses public-key encryption and bilinear pairings.In addition, very minor modifications to our solution enable it to take into account regular expressions, such as fully- or partly-unknown characters in a keyword (wildcards and interval/subset searches). Our trapdoor size is at most linear in the keyword length (and independent of the plaintext size), and we prove that the leakage to the searcher is only the trivial one: since the searcher learns whether the pattern occurs and where, it can distinguish based on different search results of a single trapdoor on two different plaintexts.To better show the usability of our scheme, we implemented it to run DPI on all the SNORT rules. We show that even for very large plaintexts, our encryption algorithm scales well. The pattern-matching algorithm is slower, but extremely parallelizable, and it can thus be run even on very large data. Although our proofs use a (marginally) interactive assumption, we argue that this is a relatively small price to pay for the flexibility and privacy that we are able to attain.

2018

ASIACRYPT

LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
Abstract

This paper is devoted to analyzing the variant of Regev’s learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector $$\mathbf {s}\in \mathbb {Z}^n$$ given polynomially many samples of the form $$(\mathbf {a},\langle \mathbf {a},\mathbf {s}\rangle + e)\in \mathbb {Z}^{n+1}$$ where $$\mathbf { a}$$ and e follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be solved efficiently as long as the variance of e is not superpolynomially larger than that of $$\mathbf { a}$$. We also provide almost tight bounds on the number of samples needed to recover $$\mathbf {s}$$.Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to $${\approx }7\%$$ in the CCS paper), and is also considerably faster.

2014

ASIACRYPT

#### Program Committees

- FSE 2020
- CHES 2019 (Program chair)
- PKC 2019
- CHES 2018
- PKC 2018
- FSE 2018
- CHES 2017
- PKC 2017
- Crypto 2016
- PKC 2016
- CHES 2015
- Eurocrypt 2014
- Crypto 2014
- CHES 2014
- PKC 2013
- CHES 2013
- Eurocrypt 2012
- Crypto 2012
- CHES 2011
- FSE 2011
- CHES 2010
- CHES 2009
- Eurocrypt 2009
- PKC 2009
- CHES 2007
- CHES 2006
- PKC 2006

#### Coauthors

- Michel Abdalla (5)
- Martin R. Albrecht (1)
- Elena Andreeva (2)
- Diego F. Aranha (1)
- Shi Bai (1)
- Gilles Barthe (3)
- Sonia Belaïd (5)
- Jean-François Biasse (1)
- Jonathan Bootle (1)
- Jean-Philippe Bossuat (1)
- Raphael Bost (1)
- Charles Bouillaguet (8)
- Jung Hee Cheon (1)
- Céline Chevalier (1)
- Olivier Chevassut (2)
- Jean-Sébastien Coron (1)
- Daniel De Almeida Braga (1)
- Claire Delaplace (2)
- Patrick Derbez (11)
- Nicolas Desmoulins (1)
- M'hamed Drissi (1)
- Vivien Dubois (2)
- Orr Dunkelman (2)
- François Dupressoir (2)
- Thomas Espitau (6)
- Jean-Charles Faugère (1)
- Pierrick Gaudry (1)
- Alexandre Gélin (1)
- Benoît Gérard (3)
- Louis Granboulan (1)
- Benjamin Grégoire (1)
- Benjamin Grégoire (2)
- Nicolas Guillermin (1)
- Jonathan J. Hoch (2)
- Nick Howgrave-Graham (1)
- Jérémy Jean (3)
- Antoine Joux (1)
- Jean-Gabriel Kammerer (2)
- Pierre Karpman (4)
- John Kelsey (2)
- Paul Kirchner (9)
- Sébastien Kunz-Jacques (1)
- Baptiste Lambin (2)
- Changmin Lee (1)
- Moon Sung Lee (1)
- Tancrède Lepoint (1)
- Delphine Leresteux (2)
- Gaëtan Leurent (3)
- Vadim Lyubashevsky (2)
- Gilles Macario-Rat (3)
- Gwenaëlle Martinet (4)
- Chrysanthi Mavromati (1)
- Brice Minaud (6)
- Victor Mollimard (2)
- Frédéric Muller (2)
- Phong Q. Nguyen (1)
- Cristina Onete (1)
- Ludovic Perret (2)
- Thomas Peyrin (1)
- David Pointcheval (5)
- Thomas Pornin (1)
- Guillaume Poupard (5)
- Emmanuel Prouff (1)
- Denis Réal (2)
- Michael Reichle (1)
- Mélissa Rossi (1)
- Hansol Ryu (1)
- Mohamed Sabt (1)
- Olivier Sanders (1)
- Adi Shamir (3)
- Damien Stehlé (1)
- Jacques Stern (7)
- Pierre-Yves Strub (1)
- Mehdi Tibouchi (9)
- Frédéric Valette (5)
- Thomas Vannet (1)
- Amandine Véber (1)
- Alexandre Wallet (1)
- Weiqiang Wen (1)
- Yang Yu (2)
- Jean-Christophe Zapalowicz (3)
- Sébastien Zimmer (3)