Article

Free access

A fuzzy commitment scheme

Authors:

Martin WattenbergAuthors Info & Claims

CCS '99: Proceedings of the 6th ACM conference on Computer and communications security

Pages 28 - 36

https://doi.org/10.1145/319709.319714

Published: 01 November 1999 Publication History

Abstract

We combine well-known techniques from the areas of error-correcting codes and cryptography to achieve a new type of cryptographic primitive that we refer to as a fuzzy commitment scheme. Like a conventional cryptographic commitment scheme, our fuzzy commitment scheme is both concealing and binding: it is infeasible for an attacker to learn the committed value, and also for the committer to decommit a value in more than one way. In a conventional scheme, a commitment must be opened using a unique witness, which acts, essentially, as a decryption key. By contrast, our scheme is fuzzy in the sense that it accepts a witness that is close to the original encrypting witness in a suitable metric, but not necessarily identical.

This characteristic of our fuzzy commitment scheme makes it useful for applications such as biometric authentication systems, in which data is subject to random noise. Because the scheme is tolerant of error, it is capable of protecting biometric data just as conventional cryptographic techniques, like hash functions, are used to protect alphanumeric passwords. This addresses a major outstanding problem in the theory of biometric authentication. We prove the security characteristics of our fuzzy commitment scheme relative to the properties of an underlying cryptographic hash function.

References

[1]

M. Alabbadi and S.B. Wicker. A digital signature scheme based on linear error-correcting block codes. In Josef Pieprzyk and Reihanah Safavi-Naini, editors, Advances in Cryptology- ASIA CRYPT '9~, pages 238- 248. Springer-Verlag, 1994. LNCS No. 917.

Digital Library

[2]

B. DePalma, Director. Mission: Impossible. Paramount Pictures, 1997. Starring Tom Cruise et al.

[3]

S. Bakhtiari, R. Safavi-Naini, and J. Pieprzyk. On password-based authenticated key exchange using collisionful hash functions, in The Austrahan Conference on In}ormahon Security and Pmvacy (.4 CISP '96), pages 299-310, 1996. LNCS No. 1172.

Digital Library

[4]

S. Bakhtiari, R. Safavi-Naini, and J. Pieprzyk. On selectable eollisionful hash functions. In The Australian Conference on Informatwn Security and Privacy (ACISP "96), pages 287-292, 1996. LNCS No. 1172.

Digital Library

[5]

S. Bakhtiari, R. Safavi-Naini, and J. Pieprzyk. On the weaknesses of Gong's collisionful hash function. Journal o} Universal Computer Sczence (J. UCS), 3(3):185--196, 1997.

[6]

C.H. Bennett, F. Bessette, G. Brassard, 13. Savail, and J. Smolin. Experimental quantum cryptography. Journal of Cryptology, 5(1):3-28, 1992.

Digital Library

[7]

C.H. Bennett, G. Brassard, C. Cr6peau, and M.-H. Skubiszewska. Practical quantum oblivious transfer protocols. In J. Feigenbaum, editor, Advances m Cryptology- CRYPTO '92, pages 351-366. Springer-Verlag, 1991. LNCS No. 576.

Digital Library

[8]

E.R. Berlekamp, R.J. McEliece, and H.C.A. van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24:384-386, 1978.

Digital Library

[9]

T.A. Berson, L. Gong, and T.M.A. Lomas. Secure, keyed, and eoUisionful hash functions. Technical Report SRI-CSL-94-08, Computer Science Laboratory, SRI International, December 1993.

[10]

W. Branigin. INS fighting for a high-tech future. Washington Post, page A19, 30 September 1997.

[11]

R. Chandrasel~ran. Brave New Whorl: ID systems using the human body are here, but privacy issues persist. Washington Post, page HO 1, 30 March 1997.

[12]

D. Chaum, I.B. Damghrd, and J. van de Graaf. Multiparty computation ensuring privacy of each party's input and correctness of the result. In C. Pomerance, editor, Advances in Cryptology - CRYPTO '8Z pages 87-119. Springer-Verlag, 1987. LNCS No. 293.

Digital Library

[13]

C. Cr~peau. Efficient cryptographic protocols based on noisy channels. In W. Fumy, editor, Advances in Cryptology - EUROCRYPT '97, p~ges 306-317. Springer- Verlag, 1997. LNCS No. 1233.

Digital Library

[14]

C. Cr4peau and J. Kilian. Achieving oblivious transfer using weakened security assumptions. In Proceedings of the ~9th IEEE Symposzum on the Foundatwns of Computer Science, l~ges 42-52, 1988.

[15]

J. Daugman. High confidence visuM recognition of persons by a test of statistical independence. IEEE Transactioras on Pattern Analysis and Machine Intelligence, 15(11):648--656, November 1993.

Digital Library

[16]

G.I. Davida, Y. Frankel, and B.J. Matt. On enabling secure applications through off-line biometric identification. In IEEE Symposium on Privacy and Secumty, 1998. To appear.

[17]

G.I. Davida, Y. Frankel, and B.J. Matt. On the relation of error correction and cryptography to an oftline biometrie based identification scheme. In Proceedings of WCC99, Workshop on Coding and Cryptography, 1999. To appear.

[18]

D.C. Feldmeier and P.R. Karn. UNIX password security- ten years later. In G. Brassard, editor, Advances sn Cryptolo#y- CRYPTO '89, pages 44-63. Springer- Verlag, 1989. LNCS No. 435.

Digital Library

[19]

R. Fixmer. Tiny new chip could pit protection of property against right of privacy. New York T, mes, 23 September 1998.

[20]

L. Gong. Co}lisionful keyed hash functions with selectable collisions, lnformatwn Processing Letters, 55(3):167-170, August 1995.

Digital Library

[21]

T. Jakobsen. Cryptanalysis of block ciphers with probabilistic non-linear relations of low degree. In H. Krawezyk, editor, Advances ~n Cryptology- CRYPTO '98, pages 212-222. Springer-Verlag, 1998. LNCS No. 1462.

Digital Library

[22]

L. O'Gorman, Chief Scientist, Veridicom Corp., 23 September 1998. Personal communication.

[23]

F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. Elsevier, 1977.

[24]

R.J. McEliece. A public-key cryptosystem based on algebraic coding theory. Technical Report DSN progress report 42-44, Jet Propulsion Laboratory, Pasadena~ 1978.

[25]

A.J. Menezes, S.A. Vanstone, and P.C. van Oorschot. Handbook of Applied Cryptography. CRC Press, 1996.

Digital Library

[26]

R. Morris and K. Thompson. Password security: a case history. Communications of the A CM, 22:594-597, 1979.

Digital Library

[27]

N. Meyer, Director. Star 7}ek II: The Wrath of Khan. Paramount Pictures, 1982. Starring William Shatner et aL

[28]

W.W. Peterson and E.J. Weldon, Jr. Error-Correcting Codes, Second Edition. MIT Press, 1972.

[29]

M.A. Shokrollahi and H. Wasserman. Decoding algebrai~-geometrie codes beyond the error-correction bound. In The Thirtieth Annual A CM Symposmm on Theory of Computing (STOC "98), 1998. To appear.

Digital Library

[30]

C. Soutax. Biometric encryption for secure key generation, January 1998. Presentation at the 1998 RSA Data Security Conference.

[31]

C. Soutar and G.J. Tomko. Secure private key generation using a fingerprint. In CardTech/SecurTech Conference Proceedings, Vol. 1, pages 245-252, May 1996.

[32]

J. Stern. A new identification scheme based on syndrome decoding. In D.R. Stinson, editor, Advances m Cryptology- CRYPTO '93, pages 13-21. Springer- Verlag, 1993. LNCS No. 773.

[33]

D. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.

Digital Library

[34]

M. Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997. Also published in FOCS '96 under the title "Maximum likelihood decoding of Reed Solomon Codes".

Digital Library

[35]

M. Sudan and V. Guruswami. Improved decoding of Reed-Solomon and algebraic-geometric codes. In Proceedings of the 39th Annual IEEE Symposzum on .Foundations of Computer Science (FOCS '98), 1998. To appear.

Digital Library

[36]

S.A. Vanstone and P.C. van Oorschot. An Introductton to Error Correcting Codes with Applicatwns. Kluwer Academic Publishers, 1989.

Digital Library

[37]

L.A. Zadeh, R.R. Yage (Editor), R.R. Yager, R.M. Tong (Editor), and H.T. Nguyen (Editor). Fuzzy Sets and Apphcations : Selected Papers by L.A. Zadeh. John Wiley & Sons, 1987.

Digital Library

Cited By

Amine Hmani MPetrovska-Delacretaz DDorizzi B(2024)Revocable Crypto-Biometric Key Regeneration Using Face Biometrics, Fuzzy Commitment, and a Cohort Bit Selection ProcessBiometrics and Cryptography10.5772/intechopen.1003710Online publication date: 19-Jun-2024
https://doi.org/10.5772/intechopen.1003710
Baig AEskeland SYang B(2024)Novel and Efficient Privacy-Preserving Continuous AuthenticationCryptography10.3390/cryptography80100038:1(3)Online publication date: 24-Jan-2024
https://doi.org/10.3390/cryptography8010003
Melzi PRathgeb CTolosana RVera RBusch C(2024)An Overview of Privacy-Enhancing Technologies in Biometric RecognitionACM Computing Surveys10.1145/3664596Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3664596
Show More Cited By

Index Terms

A fuzzy commitment scheme

Recommendations

An efficient non-interactive deniable authentication scheme based on trapdoor commitment schemes

Deniable authentication scheme is one of useful tools for secure communications. The scheme allows a sender to prove the authenticity of a message to a specified receiver without permitting the receiver to prove that the message was authenticated by the ...
A multi-trapdoor commitment scheme from the RSA assumption
ACISP'10: Proceedings of the 15th Australasian conference on Information security and privacy

Gennaro introduced the notion of multi-trapdoor commitments which is a stronger form of trapdoor commitment schemes at CRYPTO 2004. Multi-trapdoor commitments have several cryptographic applications. For example, Gennaro proposed a conversion that makes ...
A Straight-Line Extractable Non-malleable Commitment Scheme

Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '99: Proceedings of the 6th ACM conference on Computer and communications security

November 1999

160 pages

ISBN:1581131488

DOI:10.1145/319709

Chairmen:
Juzar Motiwalla
Kent Ridge Digital Labs, Singapore
,
Gene Tsudik
USC Information Sciences Institute, USA

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CCS99

Sponsor:

SIGSAC

CCS99: Sixth ACM Conference on Computer and Communication Security

November 1 - 4, 1999

Kent Ridge Digital Labs, Singapore

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,037
Total Citations
View Citations
4,265
Total Downloads

Downloads (Last 12 months)756
Downloads (Last 6 weeks)79

Reflects downloads up to 18 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amine Hmani MPetrovska-Delacretaz DDorizzi B(2024)Revocable Crypto-Biometric Key Regeneration Using Face Biometrics, Fuzzy Commitment, and a Cohort Bit Selection ProcessBiometrics and Cryptography10.5772/intechopen.1003710Online publication date: 19-Jun-2024
https://doi.org/10.5772/intechopen.1003710
Baig AEskeland SYang B(2024)Novel and Efficient Privacy-Preserving Continuous AuthenticationCryptography10.3390/cryptography80100038:1(3)Online publication date: 24-Jan-2024
https://doi.org/10.3390/cryptography8010003
Melzi PRathgeb CTolosana RVera RBusch C(2024)An Overview of Privacy-Enhancing Technologies in Biometric RecognitionACM Computing Surveys10.1145/3664596Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3664596
Zhang MMarin ERyan MKostakos VMurray TTag BOswald D(2024)OOBKey: Key Exchange with Implantable Medical Devices Using Out-Of-Band ChannelsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3670876(1-13)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3670876
Jiang PLiu QZhu L(2024)Purified Authorization Service With Encrypted Message ModerationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.339339119(5196-5206)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3393391
Osorio-Roig DGonzález-Soler LRathgeb CBusch C(2024)Privacy-Preserving Multi-Biometric Indexing Based on Frequent Binary PatternsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338631019(4835-4850)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3386310
Jiang QZhao GMa XLi MTian YLi X(2024)Cross-Modal Learning Based Flexible Bimodal Biometric Authentication With Template ProtectionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.336409219(3593-3607)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3364092
Abdolinezhad SZimmermann LSikora A(2024)Output Positioning to Derive Maximum Entropy From Physical Unclonable FunctionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.332060819(359-371)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3320608
Kietzmann PSchmidt TWählisch M(2024)PUF for the Commons: Enhancing Embedded Security on the OS LevelIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.330036821:4(2194-2210)Online publication date: Jul-2024
https://doi.org/10.1109/TDSC.2023.3300368
Lin KChen Y(2024)A High-Security-Level Iris Recognition System Based on Multi-Scale Dominating Feature PointsIEEE Signal Processing Letters10.1109/LSP.2024.341151331(1600-1604)Online publication date: 2024
https://doi.org/10.1109/LSP.2024.3411513
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents

-