The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Open accessAbstract
We provide formal definitions and efficient secure techniques for turning noisy information into keys usable for any cryptographic application, and, in particular, reliably and securely authenticating biometric data. Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A secure sketch produces public information about its input w that does not reveal w and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them. We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of “closeness” of input data, such as Hamming distance, edit distance, and set difference.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
(1961) · Journal of the Optical Society of America · doi:10.1364/josa.51.000248 · Cited by 2,288
Theory and practice of error control codes
Blahut, R. E. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 2,066
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Reyzin, L., & Smith, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_31 · Cited by 2,038
Self-citationSecret key agreement by public discussion from common information
Maurer, U. M. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256484 · Cited by 2,005
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
(2000) · Choice Reviews Online · doi:10.5860/choice.37-5723 · Cited by 1,617
Juels, A., & Wattenberg, M. (1999) · Proceedings of the 6th ACM conference on Computer and communications security · doi:10.1145/319709.319714 · Cited by 1,591
Generalized privacy amplification
Bennett, C. H., Brassard, G., Crepeau, C., & Maurer, U. M. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.476316 · Cited by 1,417
New hash functions and their use in authentication and set equality
Wegman, M. N., & Carter, J. L. (1981) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(81)90033-7 · Cited by 1,402
Improved decoding of Reed-Solomon and algebraic-geometry codes
Guruswami, V., & Sudan, M. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.782097 · Cited by 998
Password security: a case history
Morris, R., & Thompson, K. (1979) · Communications of the ACM · doi:10.1145/359168.359172 · Cited by 926
Privacy Amplification by Public Discussion
Bennett, C. H., Brassard, G., & Robert, J.-M. (1988) · SIAM Journal on Computing · doi:10.1137/0217014 · Cited by 867
Multiplication of Multidigit Numbers on Automata
Karatsuba, A. A., & Ofman, Y. (1963) · Soviet physics. Doklady · Cited by 792
Pseudo-random generation from one-way functions
Impagliazzo, R., Levin, L. A., & Luby, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73009 · Cited by 724
Juels, A., & Sudan, M. (2006) · Designs, Codes and Cryptography · doi:10.1007/s10623-005-6343-z · Cited by 648
Nisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634
A Computational Introduction to Number Theory and Algebra
Shoup, V. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814549 · Cited by 549
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 544
A new table of constant weight codes
Brouwer, A. E., Shearer, J. B., Sloane, N. J. A., & Smith, W. D. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.59932 · Cited by 422
A method for solving key equation for decoding goppa codes
Sugiyama, Y., Kasahara, M., Hirasawa, S., & Namekawa, T. (1975) · Information and Control · doi:10.1016/s0019-9958(75)90090-x · Cited by 409
On enabling secure applications through off-line biometric identification
Davida, G. I., Frankel, Y., & Matt, B. J. (2002) · Proceedings. 1998 IEEE Symposium on Security and Privacy (Cat. No.98CB36186) · doi:10.1109/secpri.1998.674831 · Cited by 406
New Shielding Functions to Enhance Privacy and Prevent Misuse of Biometric Templates
Linnartz, J.-P., & Tuyls, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-44887-x_47 · Cited by 387
Cryptographic key generation from voice
Monrose, F., Reiter, M. K., Li, Q., & Wetzel, S. (2002) · Proceedings 2001 IEEE Symposium on Security and Privacy. S&P 2001 · doi:10.1109/secpri.2001.924299 · Cited by 333
RECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
SHALTIEL, R. (2004) · Current Trends in Theoretical Computer Science · doi:10.1142/9789812562494_0013 · Cited by 291
A Proposal for an ISO Standard for Public Key Encryption.
Shoup, V. (2001) · Cited by 271
Secure Remote Authentication Using Biometric Data
Boyen, X., Dodis, Y., Katz, J. I., Ostrovsky, R., & Smith, A. (2005) · Lecture notes in computer science · doi:10.1007/11426639_9 · Cited by 260
Self-citationSimple and Tight Bounds for Information Reconciliation and Privacy Amplification
Renner, R., & Wolf, S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11593447_11 · Cited by 258
Password hardening based on keystroke dynamics
Monrose, F., Reiter, M. K., & Wetzel, S. (2002) · International Journal of Information Security · doi:10.1007/s102070100006 · Cited by 254
Practical Quantum Oblivious Transfer
Bennett, C. H., Brassard, G., Crépeau, C., & Skubiszewska, M.-H. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_29 · Cited by 224
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
Radhakrishnan, J., & Ta-Shma, A. (2000) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480197329508 · Cited by 223
List Decoding of Error-Correcting Codes
Guruswami, V. (2005) · Lecture Notes in Computer Science · doi:10.1007/b104335 · Cited by 209
Smooth renyi entropy and applications
Renner, R., & Wolf, S. (2004) · International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings. · doi:10.1109/isit.2004.1365269 · Cited by 174
Correcting errors without leaking partial information
Dodis, Y., & Smith, A. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060688 · Cited by 171
Self-citationEfficient Cryptographic Protocols Based on Noisy Channels
Crépeau, C. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_21 · Cited by 169
Extracting Randomness: A Survey and New Constructions
Nisan, N., & Ta‐Shma, A. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1546 · Cited by 158
Protecting secret keys with personal entropy
Ellison, C. M., Hall, C., Milbert, R., & Schneier, B. (2000) · Future Generation Computer Systems · doi:10.1016/s0167-739x(99)00055-2 · Cited by 106
Using voice to generate cryptographic keys.
Monrose, F., Reiter, M. K., Li, Q. L., & Wetzel, S. (2001) · Cited by 83
Starobinski, D., Trachtenberg, A., & Agarwal, S. (2003) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2003.1195150 · Cited by 80
Tight bounds for depth-two superconcentrators
Radhakrishnan, J., & Ta‐Shma, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646148 · Cited by 58
Lower Bounds on Signatures From Symmetric Primitives
Barak, B., & Mahmoody, M. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389536 · Cited by 53
The Computational Hardness of Estimating Edit Distance
Andoni, A., & Krauthgamer, R. (2010) · SIAM Journal on Computing · doi:10.1137/080716530 · Cited by 38
Subquadratic-time factoring of polynomials over finite fields
Kaltofen, E., & Shoup, V. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225166 · Cited by 30
Cited by
Jain, A. K., Nandakumar, K., & Nagar, A. (2008) · EURASIP Journal on Advances in Signal Processing · doi:10.1155/2008/579416 · Cited by 1,134
Efficient Lattice (H)IBE in the Standard Model
Agrawal, S., Boneh, D., & Boyen, X. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_28 · Cited by 976
50 years of biometric research: Accomplishments, challenges, and opportunities
Jain, A. K., Nandakumar, K., & Ross, A. (2016) · Pattern Recognition Letters · doi:10.1016/j.patrec.2015.12.013 · Cited by 708
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
PUF Modeling Attacks on Simulated and Silicon Data
Ruhrmair, U., Solter, J., Sehnke, F., Xu, X., Mahmoud, A., Stoyanova, V., Dror, G., Schmidhuber, J., Burleson, W., & Devadas, S. (2013) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2013.2279798 · Cited by 637
Metadata
- Authors
- Dodis, Y., Ostrovsky, R., Reyzin, L., & Smith, A.
- Venue
- SIAM Journal on Computing
- Published
- 2008-01
- Volume
- 38
- Issue
- 1
- Pages
- 97-139
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2146813141
- Cited by
- 1,717
- References
- 44
- FWCI
- 144.70
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.