## CryptoDB

### David Pointcheval

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

#### Publications

**Year**

**Venue**

**Title**

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.

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 (19)
- Mihir Bellare (6)
- Fabrice Benhamouda (14)
- 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 (1)
- Jean-Sébastien Coron (2)
- Geoffroy Couteau (5)
- Cécile Delerablée (1)
- Anand Desai (3)
- Pierre-Alain Dupont (1)
- Pierre-Alain Fouque (7)
- Georg Fuchsbauer (3)
- Eiichiro Fujisaki (3)
- Pierrick Gaudry (2)
- Romain Gay (1)
- Helena Handschuh (2)
- Julia Hesse (1)
- Nick Howgrave-Graham (1)
- Marc Joye (2)
- John Malone-Lee (1)
- David Naccache (2)
- Chanathip Namprempre (1)
- Phong Q. Nguyen (2)
- Tatsuaki Okamoto (4)
- Pascal Paillier (6)
- Thomas Peters (3)
- Duong Hieu Phan (4)
- 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)