International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Shafi Goldwasser

Publications

Year
Venue
Title
2021
CRYPTO
Deniable Fully Homomorphic Encryption from Learning With Errors 📺
Shweta Agrawal Shafi Goldwasser Saleet Mossel
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 📺
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.
2018
CRYPTO
2017
TCC
2017
JOFC
2016
TCC
2015
TCC
2015
TCC
2014
CRYPTO
2014
EUROCRYPT
2014
PKC
2014
JOFC
2013
TCC
2013
CRYPTO
2012
TCC
2011
TCC
2011
ASIACRYPT
2010
TCC
2010
CRYPTO
2010
CRYPTO
2010
CRYPTO
2009
TCC
2009
TCC
2009
EUROCRYPT
2008
CRYPTO
2007
EUROCRYPT
2007
TCC
2005
TCC
2005
JOFC
2004
TCC
2001
EUROCRYPT
1999
EUROCRYPT
1997
CRYPTO
1997
CRYPTO
1997
CRYPTO
1996
EUROCRYPT
1994
CRYPTO
1992
CRYPTO
1990
CRYPTO
1989
CRYPTO
1989
CRYPTO
1989
CRYPTO
1989
CRYPTO
1988
CRYPTO
1985
CRYPTO
1984
CRYPTO
1984
CRYPTO
1984
CRYPTO
1982
CRYPTO

Program Committees

Crypto 2009
Eurocrypt 2005
Eurocrypt 1997
Asiacrypt 1991
Crypto 1988 (Program chair)
Crypto 1986