Reusable Fuzzy Extractors for Low-Entropy Distributions
- PDF / 453,918 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 175 Views
Reusable Fuzzy Extractors for Low-Entropy Distributions∗ Ran Canetti Boston University, Boston, USA Tel Aviv University, Tel Aviv, Israel [email protected]
Benjamin Fuller University of Connecticut, Storrs, USA [email protected]
Omer Paneth Massachusetts Institute of Technology, Cambridge, USA [email protected]
Leonid Reyzin · Adam Smith Boston University, Boston, USA [email protected] [email protected] Communicated by Stefano Tessaro. Received 16 August 2018 / Revised 15 September 2020 / Accepted 14 October 2020
Abstract. 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 ∗ © IACR 2020. This article is the final version submitted by the author(s) to the IACR and to SpringerVerlag on September 15, 2020. A preliminary version of this work appeared at the 35th IACR Advances in Cryptology, EUROCRYPT, May 2016. Differences between that work and this manuscript are discussed at the end of the introduction.
© International Association for Cryptologic Research 2020
R. Canetti et al. 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. Keywords. Fuzzy extractors, Reusability, Key derivation, Digital lockers, Point obfuscation.
1. Introduction Long-term secrets enable cryptographic key derivation and authentication. However, many source
Data Loading...
