CryptoDB
Shafi Goldwasser
Publications
Year
Venue
Title
2021
CRYPTO
Deniable Fully Homomorphic Encryption from Learning With Errors
📺
Abstract
We define and construct {\it Deniable Fully Homomorphic Encryption} based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption.
Our constructions achieve {\it compactness} independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the faking probability achieved by the scheme. This is in contrast to all previous constructions of deniable encryption schemes (even without requiring homomorphisms) which are based on polynomial hardness assumptions, originating with the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) in which the ciphertext size grows with the inverse of the faking probability. Canetti {\it et al.} argued that this dependence ``seems inherent'', but our constructions illustrate this is not the case. We note that the Sahai-Waters (STOC13) construction of deniable encryption from indistinguishability-obfuscation achieves compactness and can be easily modified to achieve deniable FHE as well, but it requires multiple, stronger sub-exponential hardness assumptions, which are furthermore not post-quantum secure. In contrast, our constructions rely only on the LWE polynomial hardness assumption, as currently required for FHE even without deniability.
The running time of our encryption algorithm depends on the inverse of the faking probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability probability {\it and} polynomial encryption time. Yet, we believe that achieving compactness is a fundamental step on the way to achieving all properties simultaneously as has been the historical journey for other primitives such as functional encryption. Interestingly, we note that our constructions support large message spaces, whereas previous constructions were bit by bit, and can be run in online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. The running time of the online phase, is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking probability.
At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.
2020
EUROCRYPT
Formalizing Data Deletion in the Context of the Right to be Forgotten
📺
Abstract
The right of an individual to request the deletion of their personal data by an entity that might be storing it -- referred to as \emph{the right to be forgotten} -- has been explicitly recognized, legislated, and exercised in several jurisdictions across the world, including the European Union, Argentina, and California. However, much of the discussion surrounding this right offers only an intuitive notion of what it means for it to be fulfilled -- of what it means for such personal data to be deleted.
In this work, we provide a formal definitional framework for the right to be forgotten using tools and paradigms from cryptography. In particular, we provide a precise definition of what could be (or should be) expected from an entity that collects individuals' data when a request is made of it to delete some of this data. Our framework captures most, though not all, relevant aspects of typical systems involved in data processing. While it cannot be viewed as expressing the statements of current laws (especially since these are rather vague in this respect), our work offers technically precise definitions that represent possibilities for what the law could reasonably expect, and alternatives for what future versions of the law could explicitly require.
Finally, with the goal of demonstrating the applicability of our framework and definitions, we consider various natural and simple scenarios where the right to be forgotten comes up. For each of these scenarios, we highlight the pitfalls that arise even in genuine attempts at implementing systems offering deletion guarantees, and also describe technological solutions that provably satisfy our definitions. These solutions bring together techniques built by various communities.
1999
EUROCRYPT
1992
CRYPTO
1984
CRYPTO
Program Committees
- Crypto 2009
- Eurocrypt 2005
- Eurocrypt 1997
- Asiacrypt 1991
- Crypto 1988 (Program chair)
- Crypto 1986
Coauthors
- Shweta Agrawal (1)
- Adi Akavia (1)
- Donald Beaver (1)
- Mihir Bellare (5)
- Michael Ben-Or (2)
- Allison Bishop (1)
- Nir Bitansky (3)
- Manuel Blum (1)
- Elette Boyle (2)
- Zvika Brakerski (3)
- Ran Canetti (5)
- Hao Chen (1)
- Alessandro Chiesa (1)
- Benny Chor (1)
- Aloni Cohen (1)
- Henry Cohn (1)
- Lenore Cowen (1)
- Ronald Cramer (1)
- Yevgeniy Dodis (1)
- Marc Fischlin (1)
- Sanjam Garg (1)
- Oded Goldreich (6)
- S. Dov Gordon (1)
- Vipul Goyal (1)
- Robbert de Haan (1)
- Shai Halevi (3)
- Johan Håstad (1)
- Ioana Ivan (1)
- Abhishek Jain (1)
- Yael Tauman Kalai (7)
- Jonathan Katz (1)
- Dmitriy Kharchenko (1)
- Joe Kilian (2)
- Saleet Klein (1)
- Leonid A. Levin (1)
- Huijia Lin (1)
- Yehuda Lindell (1)
- Feng-Hao Liu (1)
- Silvio Micali (6)
- Daniele Micciancio (1)
- Saleet Mossel (1)
- Rafail Ostrovsky (1)
- Omer Paneth (1)
- Chris Peikert (1)
- Oxana Poburinnaya (1)
- Raluca A. Popa (1)
- Charles Rackoff (1)
- Ronald L. Rivest (1)
- Phillip Rogaway (1)
- Alon Rosen (1)
- Guy N. Rothblum (6)
- Aviad Rubinstein (1)
- Amit Sahai (1)
- Elaine Shi (1)
- Stefano Tessaro (1)
- Eran Tromer (1)
- Vinod Vaikuntanathan (6)
- Prashant Nalini Vasudevan (1)
- Erez Waisbard (1)
- Daniel Wichs (1)
- Avi Wigderson (1)
- David A. Wilson (1)
- Andrew Chi-Chih Yao (1)
- Nickolai Zeldovich (1)
- Hong-Sheng Zhou (1)