International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

David Pointcheval

Publications

Year
Venue
Title
2020
PKC
Boosting Verifiable Computation on Encrypted Data 📺
Dario Fiore Anca Nitulescu David Pointcheval
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 📺
Chloé Hébant Duong Hieu Phan David Pointcheval
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 📺
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
Florian Bourse David Pointcheval Olivier Sanders
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
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
EUROCRYPT
2018
ASIACRYPT
Decentralized Multi-Client Functional Encryption for Inner Product
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.
2017
EUROCRYPT
2017
PKC
2017
PKC
2016
CRYPTO
2015
PKC
2015
PKC
2015
PKC
2015
EUROCRYPT
2015
CRYPTO
2014
PKC
2013
PKC
2013
PKC
2013
CRYPTO
2013
ASIACRYPT
2012
TCC
2012
PKC
2011
PKC
2009
PKC
2009
EUROCRYPT
2009
CRYPTO
2008
CRYPTO
2007
JOFC
2006
ASIACRYPT
2006
CRYPTO
2006
PKC
2006
PKC
2006
PKC
2005
ASIACRYPT
2005
EUROCRYPT
2005
PKC
2005
PKC
2004
ASIACRYPT
2004
CHES
2004
CRYPTO
2004
PKC
2004
JOFC
2003
ASIACRYPT
2003
ASIACRYPT
2003
CRYPTO
2003
JOFC
2002
ASIACRYPT
2002
CRYPTO
2002
CRYPTO
2002
EUROCRYPT
2002
PKC
2001
ASIACRYPT
2001
ASIACRYPT
2001
ASIACRYPT
2001
CRYPTO
2001
PKC
2000
EUROCRYPT
2000
PKC
2000
PKC
2000
PKC
2000
JOFC
1999
ASIACRYPT
1999
EUROCRYPT
1998
CRYPTO
1998
EUROCRYPT
1996
ASIACRYPT
1996
EUROCRYPT
1995
EUROCRYPT

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