Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Tightly CCA-Secure Encryption Without Pairings Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Reusable Fuzzy Extractors for Low-Entropy Distributions

verfasst von : Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, Adam Smith

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Fuzzy extractors (Dodis et al., Eurocrypt 2004) 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, CCS 2004) 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 only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient 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. We show that such structural assumptions are necessary to support 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Provably Robust Sponge-Based PRNGs and KDFs
Nächstes Kapitel Provably Weak Instances of Ring-LWE Revisited
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Specifically, Boyen’s construction requires that the exclusive or \(w_i \oplus w_j\) of any two secrets not leak any information about \(w_i\).
 
2
The term “digital lockers” was introduced by Canetti and Dakdouk [13]; the fact that such digital lockers can be built easily out cryptographic hash functions was shown by [38, Sect. 4].
 
3
Binary entropy \(h_2(\alpha )\) for \(0<\alpha <1\) is defined as \(-\alpha \log _2 \alpha -(1-\alpha ) \log _2 (1-\alpha )\); it is greater than \(\alpha \log _2 \frac{1}{\alpha }\) and, in particular, greater than \(\alpha \) for interesting range \(\alpha <\frac{1}{2}\).
 
4
However, standard heuristics for estimating entropy can also be used to indicate whether a source has high-entropy samples. For a corpus of noisy signals, repeat the following a statistically significant number of times: (1) sample k indices (2) run the heuristic entropy test on the corpus which each sample restricted to the k indices.
 
5
Reusability and unlinkability are two different properties. Unlinkability prevents an adversary from telling if two enrollments correspond to the same physical source [15, 35]. We do not consider this property in this work.
 
6
We present and analyze the construction with uniformly random subsets; however, if necessary, it is possible to substantially decrease the required public randomness and the length of p by using more sophisticated samplers. See [27] for an introduction to samplers.
 
7
For the construction to be reusable \(\rho \) times the digital locker must be composable \(\ell \cdot \rho \) times.
 
8
Any code that corrects \(t\) Hamming errors also corrects \(t\) \(0\rightarrow 1\) errors, but more efficient codes exist for this type of error [53]. Codes with \(2^{\varTheta (n)}\) codewords and \(t= \varTheta (n)\) over the binary alphabet exist for Hamming errors and suffice for our purposes (first constructed by Justensen [32]). These codes also yield a constant error tolerance for \(0\rightarrow 1\) bit flips. The class of errors we support in our source (\(t\) Hamming errors over a large alphabet) and the class of errors for which we need codes (\(t\) \(0\rightarrow 1\) errors) are different.
 
9
We actually need \(({\mathsf {Gen}} ', {\mathsf {Rep}} ')\) to be an average case fuzzy extractor (see [22, Definition 4] and the accompanying discussion). Most known constructions of fuzzy extractors are average-case fuzzy extractors. For simplicity we refer to \({\mathsf {Gen}} ', {\mathsf {Rep}} '\) as simply a fuzzy extractor.
 
10
Here we assume that \(|\mathcal {Z}|\ge n\times \log p\), that is the source has a small number of symbols.
 
11
Note, again, that \(({\mathsf {Gen}} ', {\mathsf {Rep}} ')\) must be an average-case fuzzy extractor. Most known constructions are average-case and we omit this notation.
 
Literatur
1.
Ash, R.: Information Theory. Interscience Publishers, New York (1965)MATH
2.
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficientprotocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
3.
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988)MathSciNetCrossRefMATH
4.
Bitansky, N., Canetti, R.: On strong simulation and composable point obfuscation. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 520–537. Springer, Heidelberg (2010)CrossRef
5.
Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O.: On virtual grey box obfuscation for general circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 108–125. Springer, Heidelberg (2014)CrossRef
6.
Blanton, M., Aliasgari, M.: On the (non-) reusability of fuzzy sketches and extractors and security improvements in the computational setting. IACR Cryptology ePrint Archive, 2012:608 (2012)
7.
Blanton, M., Aliasgari, M.: Analysis of reusability of secure sketches and fuzzy extractors. IEEE Trans. Inf. Forensics Secur. 8(9–10), 1433–1445 (2013)CrossRef
8.
Blanton, M., Hudelson, W.M.P.: Biometric-based non-transferable anonymous credentials. In: Qing, S., Mitchell, C.J., Wang, G. (eds.) ICICS 2009. LNCS, vol. 5927, pp. 165–180. Springer, Heidelberg (2009)CrossRef
9.
Boyen, X.: Reusable cryptographic fuzzy extractors. In: Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, pp. 82–91. ACM, New York (2004)
10.
Boyen, X., Dodis, Y., Katz, J., Ostrovsky, R., Smith, A.: Secure remote authentication using biometric data. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 147–163. Springer, Heidelberg (2005)CrossRef
11.
Brostoff, S., Sasse, M.A.: Are passfaces more usable than passwords?: A Field Trial Investigation. People and Computers, pp. 405–424 (2000)
12.
Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)CrossRef
13.
Canetti, R., Dakdouk, R.R.: Obfuscating point functions with multibit output. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 489–508. Springer, Heidelberg (2008)CrossRef
14.
Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On symmetric encryption and point obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010)CrossRef
15.
Carter, F., Stoianov, A: Implications of biometric encryption on wide spread use of biometrics. In: EBF Biometric Encryption Seminar, June 2008
16.
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230–261 (1988)MathSciNetCrossRefMATH
17.
Cramer, R., Dodis, Y., Fehr, S., Padró, C., Wichs, D.: Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 471–488. Springer, Heidelberg (2008)CrossRef
18.
19.
Daugman, J.: How iris recognition works. IEEE Trans. Circuits Syst. Video Technol. 14(1), 21–30 (2004)CrossRef
20.
Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, Bethesda, MD, USA, May 31 - June 2, 2009, pp. 621–630. ACM (2009)
21.
Dodis, Y., Kanukurthi, B., Katz, J., Reyzin, L., Smith, A.: Robust fuzzy extractors and authenticated key agreement from close secrets. IEEE Trans. Inf. Theory 58(9), 6207–6222 (2012)MathSciNetCrossRefMATH
22.
Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)MathSciNetCrossRefMATH
23.
Dodis, Y., Pietrzak, K., Wichs, D.: Key derivation without entropy waste. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 93–110. Springer, Heidelberg (2014)CrossRef
24.
Ellison, C., Hall, C., Milbert, R., Schneier, B.: Protecting secret keys with personal entropy. Future Gener. Comput. Syst. 16(4), 311–318 (2000)CrossRef
25.
Fuller, B., Meng, X., Reyzin, L.: Computational fuzzy extractors. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 174–193. Springer, Heidelberg (2013)CrossRef
26.
Gassend, B., Clarke, D., Van Dijk, M., Devadas, S.: Silicon physical random functions. In: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 148–160. ACM (2002)
27.
Goldreich, O.: A sample of samplers: a computational perspective on sampling. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 302–332. Springer, Heidelberg (2011)CrossRef
28.
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRefMATH
29.
Hiller, M., Merli, D., Stumpf, F., Sigl, G.: Complementary IBS: application specific error correction for PUFs. In: IEEE International Symposium on Hardware-Oriented Securityand Trust (HOST), pp. 1–6. IEEE (2012)
30.
Holenstein, T., Renner, R.S.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478–493. Springer, Heidelberg (2005)CrossRef
31.
Hsiao, C.-Y., Lu, C.-J., Reyzin, L.: Conditional computational entropy, or toward separating pseudoentropy from compressibility. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 169–186. Springer, Heidelberg (2007)CrossRef
32.
33.
Kamp, J., Zuckerman, D.: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36(5), 1231–1247 (2007)MathSciNetCrossRefMATH
34.
Kanukurthi, B., Reyzin, L.: Key agreement from close secrets over unsecured channels. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 206–223. Springer, Heidelberg (2009)CrossRef
35.
Kelkboom, E.J.C., Breebaart, J., Kevenaar, T.A.M., Buhan, I., Veldhuis, R.N.J.: Preventing the decodability attack based cross-matching in a fuzzy commitment scheme. IEEE Trans. Inf. Forensics Secur. 6(1), 107–121 (2011)CrossRef
36.
Koeberl, P., Li, J., Rajan, A., Wu, W.: Entropy loss in PUF-based key generation schemes: the repetition code pitfall. In: 2014 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 44–49. IEEE (2014)
37.
Krawczyk, H.: Cryptographic extraction and key derivation: the HKDF scheme. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 631–648. Springer, Heidelberg (2010)CrossRef
38.
Lynn, B.Y.S., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004)CrossRef
39.
Maes, R., Tuyls, P., Verbauwhede, I.: Low-overhead implementation of a soft decision helper data algorithm for SRAM PUFs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 332–347. Springer, Heidelberg (2009)CrossRef
40.
Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993)MathSciNetCrossRefMATH
41.
Maurer, U.M.: Information-theoretically secure secret-key agreement by NOT authenticated public discussion. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 209–225. Springer, Heidelberg (1997)CrossRef
42.
Maurer, U.M., Wolf, S.: Towards characterizing when information-theoretic secret key agreement is possible. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 196–209. Springer, Heidelberg (1996)CrossRef
43.
Maurer, U.M., Wolf, S.: Privacy amplification secure against active adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 307–321. Springer, Heidelberg (1997)CrossRef
44.
Mayrhofer, R., Gellersen, H.: Shake well before use: intuitive and secure pairing of mobile devices. IEEE Trans. Mobile Comput. 8(6), 792–806 (2009)CrossRef
45.
Monrose, F., Reiter, M.K., Wetzel, S.: Password hardening based on keystroke dynamics. Int. J. Inf. Secur. 1(2), 69–83 (2002)CrossRefMATH
46.
47.
Pappu, R., Recht, B., Taylor, J., Gershenfeld, N.: Physical one-way functions. Science 297(5589), 2026–2030 (2002)CrossRef
48.
49.
Prabhakar, S., Sharath Pankanti, A.K., Jain, A.K.: Biometric recognition: security and privacy concerns. IEEE Secur. Priv. 1(2), 33–42 (2003)CrossRef
50.
Simoens, K., Tuyls, P., Preneel, B.: Privacy weaknesses in biometric sketches. In: 2009 30th IEEE Symposium on Security and Privacy, pp. 188–203. IEEE (2009)
51.
52.
Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key generation. In: Proceedings of the 44th Annual Design Automation Conference, pp. 9–14. ACM (2007)
53.
Tallini, L.G., Al-Bassam, S., Bose, B.: On the capacity and codes for the Z-channel. In: IEEE International Symposium on Information Theory, p. 422 (2002)
54.
Tuyls, P., Schrijen, G.-J., Škorić, B., van Geloven, J., Verhaegh, N., Wolters, R.: Read-proof hardware from protective coatings. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 369–383. Springer, Heidelberg (2006)CrossRef
55.
Vadhan, S.P.: On constructing locally computable extractors and cryptosystems in the bounded storage model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 61–77. Springer, Heidelberg (2003)CrossRef
56.
Yu, M.-D.M., Devadas, S.: Secure and robust error correction for physical unclonable functions. IEEE Des. Test 27(1), 48–65 (2010)CrossRef
57.
Zviran, M., Haga, W.J.: A comparison of password techniques for multilevel authentication mechanisms. Comput. J. 36(3), 227–237 (1993)CrossRef
Metadaten
Titel
Reusable Fuzzy Extractors for Low-Entropy Distributions
verfasst von
Ran Canetti
Benjamin Fuller
Omer Paneth
Leonid Reyzin
Adam Smith
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – EUROCRYPT 2016

Print ISBN: 978-3-662-49889-7

Electronic ISBN: 978-3-662-49890-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49890-3_5