## CryptoDB

### David Pointcheval

#### Publications

**Year**

**Venue**

**Title**

2023

PKC

Tracing a Linear Subspace: Application to Linearly-Homomorphic Group Signatures
Abstract

When multiple users have power or rights, there is always the risk of corruption or abuse. Whereas there is no solution to avoid those malicious behaviors, from the users themselves or from external adversaries, one can strongly deter them with tracing capabilities that will later help to revoke the rights or negatively impact the reputation. On the other hand, privacy is an important issue in many applications, which seems in contradiction with traceability.
In this paper, we first extend usual tracing techniques based on codes so that not just one contributor can be traced but the full collusion. In a second step, we embed suitable codes into a set~$\mathcal V$ of vectors in such a way that, given a vector~$\mathbf U \in \mathsf{span}(\mathcal V)$, the underlying code can be used to efficiently find a minimal subset~$\mathcal X \subseteq \mathcal V$ such that~$\mathbf U \in \mathsf{span}(\mathcal X)$.
To meet privacy requirements, we then make the vectors of~$\mathsf{span}(\cV)$ anonymous while keeping the efficient tracing mechanism. As an interesting application, we formally define the notion of linearly-homomorphic group signatures and propose a construction from our codes: multiple signatures can be combined to sign any linear subspace in an anonymous way, but a tracing authority is able to trace back all the contributors involved in the signatures of that subspace.

2023

ASIACRYPT

Verifiable Decentralized Multi-Client Functional Encryption for Inner Product
Abstract

Joint computation on encrypted data is becoming increasingly crucial with the rise of cloud computing. In recent years, the development of multi-client functional encryption (MCFE) has made it possible to perform joint computation on private inputs, without any interaction. Well-settled solutions for linear functions have become efficient and secure, but there is still a shortcoming: if one user inputs incorrect data, the output of the function might become meaningless for all other users (while still useful for the malicious user). To address this issue, the concept of verifiable functional encryption was introduced by Badrinarayanan et al. at Asiacrypt ’16 (BGJS). However, their solution was impractical because of strong statistical requirements. More recently, Bell et al. introduced a related concept for secure aggregation, with their ACORN solution, but it requires multiple rounds of interactions between users. In this paper,
– we first propose a computational definition of verifiability for MCFE. Our notion covers the computational version of BGJS and extends it to handle any valid inputs defined by predicates. The BGJS notion corresponds to the particular case of a fixed predicate, in our setting;
– we then introduce a new technique called Combine-then-Descend, which relies on the class group. It allows us to construct One-time Decentralized Sum (ODSUM) on verifiable private inputs. ODSUM is the building block for our final protocol of a verifiable decentralized MCFE for inner-product, where the inputs are within a range. Our approach notably enables the efficient identification of malicious users, thereby addressing an unsolved problem in ACORN.

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

- Crypto 2023
- PKC 2023
- 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 (2)
- Julia Hesse (1)
- Nick Howgrave-Graham (1)
- Marc Joye (1)
- John Malone-Lee (1)
- David Naccache (1)
- Chanathip Namprempre (1)
- Dinh Duy Nguyen (1)
- Phong Q. Nguyen (2)
- Ky Nguyen (1)
- Anca Nitulescu (1)
- Tatsuaki Okamoto (3)
- Pascal Paillier (4)
- Thomas Peters (2)
- Duong Hieu Phan (8)
- Thomas Pornin (2)
- John Proos (1)
- Leonid Reyzin (1)
- Phillip Rogaway (2)
- Olivier Sanders (4)
- Edouard Dufour Sans (1)
- Robert Schädlich (1)
- Michael Semanko (1)
- Joseph H. Silverman (1)
- Ari Singer (1)
- Nigel P. Smart (2)
- 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)