## CryptoDB

### Pierre-Alain Fouque

#### Publications

**Year**

**Venue**

**Title**

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.

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)
- Martin R. Albrecht (1)
- Elena Andreeva (2)
- Diego F. Aranha (2)
- Daniel Augot (1)
- Shi Bai (1)
- Gilles Barthe (7)
- Sonia Belaïd (9)
- Jean-François Biasse (1)
- Jonathan Bootle (1)
- Jean-Philippe Bossuat (1)
- Raphael Bost (1)
- Charles Bouillaguet (11)
- Jung Hee Cheon (1)
- Céline Chevalier (1)
- Olivier Chevassut (3)
- Jean-Sébastien Coron (2)
- Daniel De Almeida Braga (1)
- Claire Delaplace (2)
- Patrick Derbez (13)
- Nicolas Desmoulins (1)
- M'hamed Drissi (1)
- Vivien Dubois (3)
- Orr Dunkelman (3)
- François Dupressoir (6)
- Thomas Espitau (7)
- 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 (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 (5)
- Vadim Lyubashevsky (2)
- Gilles Macario-Rat (3)
- Gwenaëlle Martinet (4)
- Chrysanthi Mavromati (1)
- Brice Minaud (8)
- Victor Mollimard (2)
- 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)
- Michael Reichle (1)
- Mélissa Rossi (1)
- Hansol Ryu (1)
- Mohamed Sabt (1)
- Olivier Sanders (1)
- Adi Shamir (5)
- Damien Stehlé (1)
- Jacques Stern (9)
- Pierre-Yves Strub (2)
- Mehdi Tibouchi (13)
- Frédéric Valette (5)
- Thomas Vannet (2)
- Amandine Véber (1)
- Alexandre Wallet (1)
- Weiqiang Wen (1)
- Yang Yu (1)
- Jean-Christophe Zapalowicz (6)
- Sébastien Zimmer (4)