International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Adam Smith

Publications

Year
Venue
Title
2020
JOFC
Reusable Fuzzy Extractors for Low-Entropy Distributions
Fuzzy extractors (Dodis et al., in Advances in cryptology—EUROCRYPT 2014, Springer, Berlin, 2014, pp 93–110) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, in Proceedings of the 11th ACM conference on computer and communications security, CCS, ACM, New York, 2004, pp 82–91) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations). We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated. The extractor works for binary strings with Hamming noise; it achieves computational security under the existence of digital lockers (Canetti and Dakdouk, in Advances in cryptology—EUROCRYPT 2008, Springer, Berlin, 2008, pp 489–508). It is simple and tolerates near-linear error rates. Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates—lower than those supported by prior (nonreusable) constructions—assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. Structure beyond entropy is necessary to support distributions with low entropy rates. We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources.
2019
EUROCRYPT
Distributed Differential Privacy via Shuffling
We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the “central” model, in which a trusted server collects users’ data in the clear, which allows greater accuracy; and the “local” model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic multiparty computation (MPC), which limits scalability.In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [5], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.
2017
JOFC
2016
EUROCRYPT
2016
ASIACRYPT
2016
TCC
2015
JOFC
2015
TCC
2013
TCC
2013
EUROCRYPT
2011
CRYPTO
2010
JOFC
2010
CRYPTO
2009
TCC
2008
EUROCRYPT
2008
CRYPTO
2006
CRYPTO
2006
CRYPTO
2006
TCC
2005
EUROCRYPT
2005
EUROCRYPT
2005
TCC
2005
TCC
2004
EUROCRYPT
2004
TCC
2003
EUROCRYPT
2001
ASIACRYPT
2001
EUROCRYPT
2001
EUROCRYPT

Program Committees

Eurocrypt 2020
Eurocrypt 2018
TCC 2016
TCC 2014
Crypto 2013
Crypto 2011
TCC 2010
Crypto 2009
Crypto 2008
Crypto 2007
TCC 2006
Crypto 2005