Reusable cryptographic fuzzy extractors

ABSTRACT

We show that a number of recent definitions and constructions of fuzzy extractors are not adequate for multiple uses of the same fuzzy secret---a major shortcoming in the case of biometric applications. We propose two particularly stringent security models that specifically address the case of fuzzy secret reuse, respectively from an outsider and an insider perspective, in what we call a chosen perturbation attack. We characterize the conditions that fuzzy extractors need to satisfy to be secure, and present generic constructions from ordinary building blocks. As an illustration, we demonstrate how to use a biometric secret in a remote fuzzy authentication protocol that does not require any storage on the client's side.

REFERENCES

• 1: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 2: C. Bennett, G. Brassard, C. Crépeau, and U. Maurer. Generalized privacy amplification. IEEE Trans. Information Theory, 41(6):1915--1923, 1995.
• 3: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 4: C. Crepeau. Efficient cryptographic protocols based on noisy channels. In Proc. Advances in Cryptology---Eurocrypt '97, pages 306--317, 1997.
• 5: G. Davida, Y. Frankel, and B. Matt. On enabling secure applications through offline biometric identification. In Proc. IEEE Symp. Security and Privacy, pages 148--157, 1998.
• 6: Y. Dodis, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Proc. Advances in Cryptology---Eurocrypt '04, 2004. Full paper available as: Fuzzy extractors and cryptography, or how to use your fingerprints. Cryptology ePrint Archive, Report 2003/235, 2003.
• 7: Carl Ellison , Chris Hall , Randy Milbert , Bruce Schneier, Protecting secret keys with personal entropy, Future Generation Computer Systems, v.16 n.4, p.311-318, Feb. 2000 [doi>10.1016/S0167-739X(99)00055-2]
• 8: Niklas Frykholm , Ari Juels, Error-tolerant password recovery, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.501985]
• 9: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 10: A. Juels and M. Sudan. A fuzzy vault scheme. In IEEE Int. Symp. Information Theory, 2002.
• 11: Ari Juels , Martin Wattenberg, A fuzzy commitment scheme, Proceedings of the 6th ACM conference on Computer and communications security, p.28-36, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319714]
• 12: Fabian Monrose , Michael K. Reiter , Susanne Wetzel, Password hardening based on keystroke dynamics, Proceedings of the 6th ACM conference on Computer and communications security, p.73-82, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319720]
• 13: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 14: J. Radhakrishnan , A. Ta-Shma, Tight bounds for depth-two superconcentrators, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.585, October 19-22, 1997
• 15: R. Shaltiel. Recent developments in explicit constructions of extractors. Bul. EATCS, 77:67--95, 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Security, Theory

Keywords:
biometric keying, chosen perturbation security, fuzzy extractor, zero storage biometric authentication