## CryptoDB

### David Pointcheval

#### Affiliation: CNRS and DI/ENS, PSL Research University, France

#### Publications

**Year**

**Venue**

**Title**

2020

PKC

Boosting Verifiable Computation on Encrypted Data
📺
Abstract

We consider the setting in which an untrusted server stores a collection of data and is asked to compute a function over it. In this scenario, we aim for solutions where the untrusted server does not learn information about the data and is prevented from cheating. This problem is addressed by verifiable and private delegation of computation, proposed by Gennaro, Gentry and Parno (CRYPTO’10), a notion that is close to both the active areas of homomorphic encryption and verifiable computation (VC). However, in spite of the efficiency advances in the respective areas, VC protocols that guarantee privacy of the inputs are still expensive. The only exception is a protocol by Fiore, Gennaro and Pastro (CCS’14) that supports arithmetic circuits of degree at most 2. In this paper we propose new efficient protocols for VC on encrypted data that improve over the state of the art solution of Fiore et al. in multiple aspects. First, we can support computations of degree higher than 2. Second, we achieve public delegatability and public verifiability whereas Fiore et al. need the same secret key to encode inputs and verify outputs. Third, we achieve a new property that guarantees that verifiers can be convinced about the correctness of the outputs without learning information on the inputs. The key tool to obtain our new protocols is a new SNARK that can efficiently handle computations over a quotient polynomial ring, such as the one used by Ring-LWE somewhat homomorphic encryption schemes. This SNARK in turn relies on a new commit-and-prove SNARK for proving evaluations on the same point of several committed polynomials. We propose a construction of this scheme under an extractability assumption over bilinear groups in the random oracle model.

2020

PKC

Linearly-Homomorphic Signatures and Scalable Mix-Nets
📺
Abstract

Anonymity is a primary ingredient for our digital life. Several tools have been designed to address it such as, for authentication, blind signatures, group signatures or anonymous credentials and, for confidentiality, randomizable encryption or mix-nets. When it comes to complex electronic voting schemes, random shuffling of authenticated ciphertexts with mix-nets is the only known tool. However, it requires huge and complex zero-knowledge proofs to guarantee the actual permutation of the initial ciphertexts in a privacy-preserving way. In this paper, we propose a new approach for proving correct shuffling of signed ElGamal ciphertexts: the mix-servers can simply randomize individual ballots, which means the ciphertexts, the signatures, and the verification keys, with an additional global proof of constant size, and the output will be publicly verifiable. The security proof is in the generic bilinear group model. The computational complexity for the each mix-server is linear in the number of ballots. Verification is also linear in the number of ballots, but independent of the number of rounds of mixing. This leads to a new highly scalable technique. Our construction makes use of linearly-homomorphic signatures, with new features, that are of independent interest.

2020

CRYPTO

Dynamic Decentralized Functional Encryption
📺
Abstract

We introduce Dynamic Decentralized Functional Encryption (DDFE), a generalization of Functional Encryption which allows multiple users to join the system dynamically, without relying on a trusted third party or on expensive and interactive Multi-Party Computation protocols.
This notion subsumes existing multi-user extensions of Functional Encryption, such as Multi-Input, Multi-Client, and Ad Hoc Multi-Input Functional Encryption.
We define and construct schemes for various functionalities which serve as building-blocks for latter primitives and may be useful in their own right, such as a scheme for dynamically computing sums in any Abelian group. These constructions build upon simple primitives in a modular way, and have instantiations from well-studied assumptions, such as DDH or LWE.
Our constructions culminate in an Inner-Product scheme for computing weighted sums on aggregated encrypted data, from standard assumptions in prime-order groups in the Random Oracle Model.

2019

ASIACRYPT

Divisible E-Cash from Constrained Pseudo-Random Functions
Abstract

Electronic cash (e-cash) is the digital analogue of regular cash which aims at preserving users’ privacy. Following Chaum’s seminal work, several new features were proposed for e-cash to address the practical issues of the original primitive. Among them, divisibility has proved very useful to enable efficient storage and spendings. Unfortunately, it is also very difficult to achieve and, to date, quite a few constructions exist, all of them relying on complex mechanisms that can only be instantiated in one specific setting. In addition security models are incomplete and proofs sometimes hand-wavy.In this work, we first provide a complete security model for divisible e-cash, and we study the links with constrained pseudo-random functions (PRFs), a primitive recently formalized by Boneh and Waters. We exhibit two frameworks of divisible e-cash systems from constrained PRFs achieving some specific properties: either key homomorphism or delegability. We then formally prove these frameworks, and address two main issues in previous constructions: two essential security notions were either not considered at all or not fully proven. Indeed, we introduce the notion of clearing, which should guarantee that only the recipient of a transaction should be able to do the deposit, and we show the exculpability, that should prevent an honest user to be falsely accused, was wrong in most proofs of the previous constructions. Some can easily be repaired, but this is not the case for most complex settings such as constructions in the standard model. Consequently, we provide the first construction secure in the standard model, as a direct instantiation of our framework.

2019

JOFC

On the Tightness of Forward-Secure Signature Reductions
Abstract

In this paper, we revisit the security of factoring-based signature schemes built via the Fiat–Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $$\phi $$ ϕ -hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis–Reyzin forward-secure signature scheme. Unlike the original Itkis–Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Moreover, we also show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose security reductions are fully tight.

2018

ASIACRYPT

Decentralized Multi-Client Functional Encryption for Inner Product
Abstract

We consider a situation where multiple parties, owning data that have to be frequently updated, agree to share weighted sums of these data with some aggregator, but where they do not wish to reveal their individual data, and do not trust each other. We combine techniques from Private Stream Aggregation (PSA) and Functional Encryption (FE), to introduce a primitive we call Decentralized Multi-Client Functional Encryption (DMCFE), for which we give a practical instantiation for Inner Product functionalities. This primitive allows various senders to non-interactively generate ciphertexts which support inner-product evaluation, with functional decryption keys that can also be generated non-interactively, in a distributed way, among the senders. Interactions are required during the setup phase only. We prove adaptive security of our constructions, while allowing corruptions of the clients, in the random oracle model.

2015

EPRINT

2008

EPRINT

Encrypting Proofs on Pairings and Its Application to Anonymity for Signatures
Abstract

We give a generic methodology to unlinkably anonymize cryptographic schemes in bilinear groups using the Boneh-Goh-Nissim cryptosystem and NIZK proofs in the line of Groth, Ostrovsky and Sahai.
We illustrate our techniques by presenting the first instantiation of anonymous proxy signatures, a recent primitive unifying the functionalities and strong security notions of group and proxy signatures. To construct our scheme, we introduce various efficient NIZK and witness-indistinguishable proofs, and a relaxed version of simulation soundness.

2008

EPRINT

Anonymous Consecutive Delegation of Signing Rights: Unifying Group and Proxy Signatures
Abstract

We define a general model for consecutive delegations of signing rights with the following properties: The delegatee actually signing and all intermediate delegators remain anonymous. As for group signatures, in case of misuse, a special authority can open signatures to reveal the chain of delegations and the signer's identity. The scheme satisfies a strong notion of non-frameability generalizing the one for dynamic group signatures. We give formal definitions of security and show them to be satisfiable by constructing an instantiation proven secure under general assumptions in the standard model. Our primitive is a proper generalization of both group signatures and proxy signatures and can be regarded as non-frameable dynamic hierarchical group signatures.

2007

JOFC

2006

EPRINT

Automated Security Proofs with Sequences of Games
Abstract

This paper presents the first automatic technique for proving not only
protocols but also primitives in the exact security computational
model. Automatic proofs of cryptographic protocols were up to now
reserved to the Dolev-Yao model, which however makes quite strong
assumptions on the primitives. On the other hand, with the proofs by
reductions, in the complexity theoretic framework, more subtle
security assumptions can be considered, but security analyses are
manual. A process calculus is thus defined in order to take into
account the probabilistic semantics of the computational model. It is
already rich enough to describe all the usual security notions of both
symmetric and asymmetric cryptography, as well as the basic
computational assumptions. As an example, we illustrate the use of the
new tool with the proof of a quite famous asymmetric primitive:
unforgeability under chosen-message attacks (UF-CMA) of the
Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of
some permutations.

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

How to Disembed a Program?
Abstract

This paper presents the theoretical blueprint of a new secure
token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all.
While exporting all the device's executable code to potentially
untrustworthy terminals poses formidable security problems, the
advantages of ROM-less secure tokens are numerous: chip masking
time disappears, bug patching becomes a mere terminal update
and hence does not imply any roll-out of cards in the field. Most
importantly, code size ceases to be a limiting factor. This is
particularly significant given the steady increase in on-board
software complexity.
After describing the machine's instruction-set we will introduce
two XmP variants. The first design is a public-key oriented
architecture which relies on a new RSA screening scheme and
features a relatively low communication overhead at the cost of
computational complexity, whereas the second variant is secret-key
oriented and relies on simple MACs and hash functions but requires
more communication.
For each of these two designs, we propose two protocols that
execute and dynamically authenticate arbitrary programs. We also
provide a strong security model for these protocols and prove
their security under appropriate complexity assumptions.

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.

2003

ASIACRYPT

2002

EPRINT

Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages
Abstract

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

2002

EPRINT

Security Proofs for an Efficient Password-Based Key Exchange
Abstract

Password-based key exchange schemes are designed to provide
entities communicating over a public network, and sharing a
(short) password only, with a session key (e.g, the key is used
for data integrity and/or confidentiality). The focus of the
present paper is on the analysis of very efficient schemes that
have been proposed to the IEEE P1363 Standard working group on
password-based authenticated key-exchange methods, but for which
actual security was an open problem. We analyze the AuthA key
exchange scheme and give a complete proof of its security. Our
analysis shows that the AuthA protocol and its multiple modes
of operation are provably secure under the computational
Diffie-Hellman intractability assumption, in both the
random-oracle and the ideal-cipher models.

2000

EPRINT

Authenticated Key Exchange Secure Against Dictionary Attacks
Abstract

This paper gives definitions and results about password-based
protocols for authenticated key exchange (AKE), mutual authentication
MA), and the combination of these goals (AKE, MA).
Such protocols are designed to work despite interference by an active
adversary and despite the use of passwords drawn from a space so small
that an adversary might well enumerate, off line,
a user's password.
While several such password-based protocols have been suggested,
the underlying theory has been lagging, and
some of the protocols don't actually work.
This is an area strongly in need of foundations,
but definitions and theorems here can get overwhelmingly complex.
To help manage this complexity we begin by defining a model, one rich enough
to deal with password guessing, forward secrecy,
server compromise, and loss of session keys.
The one model can be used to
define various goals.
We take AKE (with implicit authentication---no one besides
your intended partner could possibly get the key, though he may or may
not actually get it) as the basic goal.
Then we prove that any secure
AKE protocol can be
embellished (in a simple and generic way)
to also provide for MA.
This approach turns out to be simpler than trying to
augment an MA protocol to also distribute a session key.
Next we prove correctness for the idea at the center
of the Encrypted Key-Exchange (EKE) protocol
of Bellovin and Merritt:
we prove (in an ideal-cipher model) that
the two-flow protocol at the core of EKE is
a secure AKE.
Combining with the result above we have a
simple 3-flow protocol for AKE,MA which is
proven secure against dictionary attack.

2000

EPRINT

RSA-OAEP is Secure under the RSA Assumption
Abstract

Recently Victor Shoup noted that there is a gap in
the widely-believed security result of OAEP against adaptive
chosen-ciphertext attacks. Moreover, he showed that,
presumably,
OAEP cannot be proven secure from the {\it one-wayness}
of the underlying trapdoor permutation.
This paper establishes another result on the security
of OAEP. It proves that OAEP offers semantic security
against adaptive chosen-ciphertext attacks,
in the random oracle model, under the {\it partial-domain}
one-wayness of the underlying permutation.
Therefore, this uses a formally stronger assumption.
Nevertheless, since partial-domain one-wayness of the RSA function
is equivalent to its (full-domain) one-wayness, it follows that
the security of RSA--OAEP can actually
be proven under the sole RSA assumption, although
the reduction is not tight.

1998

EPRINT

Relations among Notions of Security for Public-Key Encryption Schemes
Abstract

We compare the relative strengths of popular notions of security for
public key encryption schemes. We consider the goals of
indistinguishability and non-malleability, each under chosen plaintext
attack and two kinds of chosen ciphertext attack. For each of the
resulting pairs of definitions we prove either an implication (every
scheme meeting one notion must meet the other) or a separation (there
is a scheme meeting one notion but not the other, assuming the first
notion can be met at all). We similarly treat plaintext awareness, a
notion of security in the random oracle model. An additional
contribution of this paper is a new definition of non-malleability
which we believe is simpler than the previous one.

#### Program Committees

- Eurocrypt 2018
- Crypto 2016
- PKC 2016
- Eurocrypt 2015
- Asiacrypt 2013
- Eurocrypt 2012
- Eurocrypt 2010
- PKC 2010
- Asiacrypt 2009
- PKC 2009
- Asiacrypt 2008
- PKC 2007
- Crypto 2007
- Asiacrypt 2006
- PKC 2005
- Asiacrypt 2005
- Asiacrypt 2004
- Eurocrypt 2003
- PKC 2002
- Eurocrypt 2000

#### Coauthors

- Michel Abdalla (20)
- Mihir Bellare (6)
- Fabrice Benhamouda (15)
- Bruno Blanchet (2)
- Olivier Blazy (6)
- Alexandra Boldyreva (1)
- Florian Bourse (3)
- Xavier Boyen (1)
- Emmanuel Bresson (7)
- Ernest F. Brickell (1)
- Sébastien Canard (1)
- Sébastien Canard (3)
- Angelo De Caro (2)
- Dario Catalano (3)
- Hervé Chabanne (1)
- Céline Chevalier (7)
- Benoît Chevallier-Mames (3)
- Olivier Chevassut (10)
- Jérémy Chotard (2)
- Jean-Sébastien Coron (2)
- Geoffroy Couteau (5)
- Cécile Delerablée (1)
- Anand Desai (3)
- Edouard Dufour-Sans (1)
- Pierre-Alain Dupont (1)
- Dario Fiore (1)
- Pierre-Alain Fouque (7)
- Georg Fuchsbauer (3)
- Eiichiro Fujisaki (3)
- Pierrick Gaudry (2)
- Romain Gay (2)
- Helena Handschuh (2)
- Chloé Hébant (1)
- Julia Hesse (1)
- Nick Howgrave-Graham (1)
- Marc Joye (2)
- John Malone-Lee (1)
- David Naccache (2)
- Chanathip Namprempre (1)
- Phong Q. Nguyen (2)
- Anca Nitulescu (1)
- Tatsuaki Okamoto (4)
- Pascal Paillier (6)
- Thomas Peters (3)
- Duong Hieu Phan (6)
- Thomas Pornin (2)
- John Proos (1)
- Leonid Reyzin (1)
- Phillip Rogaway (4)
- Olivier Sanders (8)
- Edouard Dufour Sans (1)
- Michael Semanko (1)
- Joseph H. Silverman (1)
- Ari Singer (1)
- Nigel P. Smart (1)
- Jacques Stern (7)
- Jacques Traoré (4)
- Christophe Tymen (2)
- Serge Vaudenay (1)
- Damien Vergnaud (5)
- Hoeteck Wee (2)
- William Whyte (1)
- Sophia Yakoubov (1)
- Moti Yung (1)
- Sébastien Zimmer (1)