## CryptoDB

### David Pointcheval

#### Publications

**Year**

**Venue**

**Title**

2022

ASIACRYPT

Multi-Client Functional Encryption with Fine-Grained Access Control
Abstract

Multi-Client Functional Encryption (\MCFE) and Multi-Input Functional Encryption (\MIFE) are very interesting extensions of Functional Encryption for practical purpose. They allow to compute joint function over data from multiple parties. Both primitives are aimed at applications in multi-user settings where decryption can be correctly output for users with appropriate functional decryption keys only.
While the definitions for a single user or multiple users were quite general and can be realized
for general classes of functions as expressive as Turing machines or all circuits,
efficient schemes have been proposed so far for concrete classes of functions: either only for access control, \emph{i.e.} the identity function under some conditions, or linear/quadratic functions under no condition.
In this paper, we target classes of functions that explicitly combine some evaluation functions independent of the decrypting user under the condition of some access control. More precisely, we introduce a framework for \MCFE with fine-grained access control and propose constructions for both single-client and multi-client settings, for inner-product evaluation and access control via Linear Secret Sharing Schemes (\textsf{LSSS}), with selective and adaptive security.
The only known work that combines functional encryption in multi-user setting with access control was proposed by Abdalla \emph{et al.} (Asiacrypt '20), which relies on a generic transformation from the single-client schemes to obtain $\MIFE$ schemes that suffer a quadratic factor of $n$ (where $n$ denotes the number of clients) in the ciphertext size. We follow a different path, via $\MCFE$: we present a \emph{duplicate-and-compress} technique to transform the single-client scheme and obtain a \MCFE with fine-grained access control scheme with only a linear factor of $n$ in the ciphertext size. Our final scheme thus outperforms the Abdalla \emph{et al.}'s scheme by a factor $n$, as one can obtain \MIFE from \MCFE by making all the labels in \MCFE a fixed public constant. The concrete constructions are secure under the $\SXDH$ assumption, in the random oracle model for the \MCFE scheme, but in the standard model for the \MIFE improvement.

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.

2007

JOFC

2003

ASIACRYPT

#### Program Committees

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