## CryptoDB

### Pierre-Alain Fouque

#### Affiliation: Université Rennes, CNRS and IRISA, France

#### Publications

**Year**

**Venue**

**Title**

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.

2015

EPRINT

2014

ASIACRYPT

2010

EPRINT

Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves
Abstract

Let E be a non-supersingular elliptic curve over a finite field F_q.
At CRYPTO 2009, Icart introduced a deterministic function
F_q->E(F_q) which can be computed efficiently, and allowed him and
Coron to define well-behaved hash functions with
values in E(F_q). Some properties of this function rely on a conjecture
which was left as an open problem in Icart's paper. We prove this
conjecture as well as analogues for other hash functions.
See also Farahashi, Shparlinski and Voloch, _On Hashing into Elliptic Curves_, for independent results of a similar form.

2010

EPRINT

Security Analysis of SIMD
Abstract

In this paper we study the security of the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once.
In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage.
Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of $2^{n/2}$ using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.

2010

EPRINT

Deterministic Encoding and Hashing to Odd Hyperelliptic Curves
Abstract

In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves.
Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well as injective maps to J(F_q) which can be used to encode scalars for such applications as ElGamal encryption.
The new encoding is already interesting in the genus 1 case, where it provides a well-behaved encoding to Joux's supersingular elliptic curves.

2009

EPRINT

On the Security of Iterated Hashing based on Forgery-resistant Compression Functions
Abstract

In this paper we re-examine the security notions suggested for hash
functions, with an emphasis on the delicate notion of second
preimage resistance. We start by showing that, in the random oracle
model, both Merkle-Damgaard and HAIFA achieve second preimage resistance beyond
the birthday bound, and actually up to the level of known generic
attacks, hence demonstrating the optimality of HAIFA in this respect.
We then try to distill a more elementary requirement out of the
compression function to get some insight on the properties it should
have to guarantee the second preimage resistance of its
iteration. We show that if the (keyed) compression function is a
secure FIL-MAC then the Merkle-Damgaard mode of iteration (or HAIFA) still
maintains the same level of second preimage resistance. We conclude
by showing that this ``new'' assumption (or security notion)
implies the recently introduced
Preimage-Awareness while ensuring all other classical security
notions for hash functions.

2007

EPRINT

Practical Cryptanalysis of SFLASH
Abstract

In this paper, we present a practical attack on the signature scheme
SFLASH proposed by Patarin, Goubin and Courtois in 2001 following a
design they had introduced in 1998.
The attack only needs the public key and requires about one second
to forge a signature for any message, after a one-time computation of
several minutes. It can be applied to both SFLASHv2 which was
accepted by NESSIE, as well as to SFLASHv3 which is a higher
security version.

2007

EPRINT

Automatic Search of Differential Path in MD4
Abstract

In 2004, Wang et al. obtained breakthrough collision attacks on the main
hash functions from the MD4 family. The attacks are differential
attacks in which one closely follows the inner steps of the underlying
compression function, based on a so-called differential path. It is
generally assumed that such differential paths were found ``by hand''.
In this paper, we present an algorithm which automatically finds
suitable differential paths, in the case of MD4. As a first
application, we obtain new differential paths for MD4, which improve
upon previously known MD4 differential paths. This algorithm could be
used to find new differential paths, and to build new attacks against
MD4.

2007

EPRINT

Second Preimage Attacks on Dithered Hash Functions
Abstract

The goal of this paper is to analyze the security of dithered variants of the Merkle-Damgard mode of operation that use a third input to indicate the position of a block in the message to be hashed. These modes of operation for hash functions have been proposed to avoid some structural weaknesses of the Merkle-Damgard paradigm, e.g. that second preimages can be constructed in much less than $2^n$ work, as pointed out by Kelsey and Schneier. Among the modes of operation that use such a third input are Rivest's dithered hashing and Biham and Dunkelman's HAIFA proposal.
We propose several new second preimage attacks on the Merkle-Damgard mode of operation, which can also attack Rivest's dithered hash with almost the same complexity. When applied to Shoup's UOWHF, these attacks can be shown to be optimal since their complexity matches Shoup's security bound.

2005

EPRINT

Key Derivation and Randomness Extraction
Abstract

Key derivation refers to the process by which an agreed upon large
random number, often named master secret, is used to derive keys to
encrypt and authenticate data. Practitioners and standardization
bodies have usually used the random oracle model to get key material
from a Diffie-Hellman key exchange. However, proofs in the standard model
require randomness extractors to formally extract the entropy of the
random master secret into a seed prior to derive other keys.
This paper first deals with the protocol $\Sigma_0$, in which the key
derivation phase is (deliberately) omitted, and security inaccuracies
in the analysis and design of the Internet Key Exchange
(IKE version 1) protocol, corrected in IKEv2.
They do not endanger the practical use of IKEv1, since the security
could be proved, at least, in the random oracle model.
However, in the standard model, there is not yet any formal global security
proof, but just separated analyses which do not fit together well.
The first simplification is common in the theoretical security analysis
of several key exchange protocols, whereas the key derivation phase is a
crucial step for theoretical reasons, but also practical purpose, and
requires careful analysis. The second problem is a gap between the
recent theoretical analysis of HMAC as a good randomness extractor
(functions keyed with public but random elements) and its practical
use in IKEv1 (the key may not be totally random, because of the lack
of clear authentication of the nonces).
Since the latter problem comes from the probabilistic property of this
extractor, we thereafter review some \textit{deterministic}
randomness extractors and suggest the \emph{'Twist-AUgmented'}
technique, a new extraction method quite well-suited for
Diffie-Hellman-like scenarios.

2004

EPRINT

Password-Based Authenticated Key Exchange in the Three-Party Setting
Abstract

Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with
non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only. In this paper, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. To the best of our knowledge, the new protocol is the first provably-secure password-based protocol in the three-party setting.

2001

EPRINT

Fully Distributed Threshold RSA under Standard Assumptions
Abstract

The aim of the present article is to propose a fully distributed environment for the RSA scheme.
What we have in mind is highly sensitive applications and even if we are ready to pay a price in
terms of efficiency, we do not want any compromise of the security assumptions that we make.
Recently Shoup proposed a practical RSA threshold signature scheme that allows to share the
ability to sign between a set of players. This scheme can be used for decryption as well.
However, Shoup's protocol assumes a trusted dealer to generate and distribute the keys.
This comes from the fact that the scheme needs a special assumption on the RSA modulus and
this kind of RSA moduli cannot be easily generated in an efficient way with many players.
Of course, it is still possible to call theoretical results on multiparty computation, but we
cannot hope to design efficient protocols. The only practical result to generate RSA moduli
in a distributive manner is Boneh and Franklin protocol but this protocol cannot be easily
modified to generate the kind of RSA moduli that Shoup's protocol requires.
The present work takes a different path by proposing a method to enhance the key generation
with some additional properties and revisits the proof of Shoup to work with the resulting
RSA moduli. Both of these enhancements decrease the performance of the basic protocols.
However, we think that in the applications that we target, these enhancements provide
practical solutions. Indeed, the key generation protocol is usually run only once and the
number of players have time to perform their task so that the communication or time complexity
are not overly important.

#### 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 (7)
- Elena Andreeva (2)
- Diego F. Aranha (2)
- Daniel Augot (1)
- Gilles Barthe (7)
- Sonia Belaïd (9)
- Jean-François Biasse (1)
- Jonathan Bootle (1)
- Charles Bouillaguet (11)
- Jung Hee Cheon (1)
- Céline Chevalier (1)
- Olivier Chevassut (3)
- Jean-Sébastien Coron (2)
- Claire Delaplace (2)
- Patrick Derbez (11)
- Nicolas Desmoulins (1)
- M'hamed Drissi (1)
- Vivien Dubois (3)
- Orr Dunkelman (3)
- François Dupressoir (6)
- Thomas Espitau (5)
- Jean-Charles Faugère (1)
- Pierrick Gaudry (2)
- Alexandre Gélin (1)
- Benoît Gérard (4)
- Louis Granboulan (1)
- Benjamin Grégoire (3)
- Benjamin Grégoire (4)
- Nicolas Guillermin (1)
- Sylvain Guilley (1)
- Jonathan J. Hoch (2)
- Nick Howgrave-Graham (1)
- Jérémy Jean (3)
- Antoine Joux (2)
- Jean-Gabriel Kammerer (3)
- Pierre Karpman (7)
- John Kelsey (2)
- Paul Kirchner (5)
- 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 (5)
- Vadim Lyubashevsky (2)
- Gilles Macario-Rat (3)
- Gwenaëlle Martinet (4)
- Chrysanthi Mavromati (1)
- Brice Minaud (7)
- Victor Mollimard (1)
- Frédéric Muller (2)
- Cédric Murdica (1)
- David Naccache (1)
- Phong Q. Nguyen (2)
- Cristina Onete (1)
- Ludovic Perret (2)
- Thomas Peyrin (1)
- David Pointcheval (7)
- Guillaume Poupard (5)
- Emmanuel Prouff (2)
- Chen Qian (1)
- Denis Réal (2)
- Mélissa Rossi (1)
- Hansol Ryu (1)
- Olivier Sanders (1)
- Adi Shamir (5)
- Jacques Stern (9)
- Pierre-Yves Strub (2)
- Mehdi Tibouchi (12)
- Frédéric Valette (5)
- Thomas Vannet (2)
- Amandine Véber (1)
- Jean-Christophe Zapalowicz (6)
- Sébastien Zimmer (4)