Minimal information disclosure with efficiently verifiable credentials

ABSTRACT

Public-key based certificates provide a standard way to prove one's identity, as attested by some certificate authority (CA). However, plain certificates provide a binary identification: either the whole identity of the subject is known, or nothing is known. We propose using a Merkle hash tree structure, whereby it is possible for a single certificate to contain many separate claims or attributes, each of which may be proved independently, without revealing the others. Additionally, we demonstrate how trees from multiple sources can be combined together by modifying the tree structure. This allows claims by different authorities, such as an employer or professional organization, to be combined under a single certificate, without the CA needing to know (or to verify) all of the claims. In addition to describing the hash tree structure and protocols for constructing and verifying our proposed credential, we formally prove that it provides unforgeability and privacy and we present performance results demonstrating its efficiency. As services move from user names and passwords to attribute-based identity verification, efficiency and scalability of claims verification will become a major issue. We have implemented a prototype client-server system, deployed the prototype in Emulab, and evaluated the server-side throughput for attribute-based identity verification. The results show that our approach can perform about 200 identity verifications per second, while the best competing approach can perform only about 2--5 verifications per second. Our approach is, therefore, better suited to today's high-volume Web-based services that demand the highest possible throughput.

REFERENCES

• 1: D. Bauer. Video demonstration of the credential-holding remote identity agent. http://users.ece.gatech.edu/~gte810u/RIdA_Video/, 2007.
• 2: D. Bayer, S. Haber, and W. Stornetta. Improving the efficiency and reliability of digital time-stamping. In Sequences II: Methods in Communication, Security, and Computer Science, pages 329--334. Springer-Verlag, 1993.
• 3: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 4: S. Brands. Credentica -- u-prove sdk, 2007.
• 5: S. Brands, L. Demuynck, and B. D. Decker. A practical system for globally revoking the unlinkable pseudonyms of unknown users. In (Accepted to) 12th Australasian Conference on Information Security and Privacy, 2007.
• 6: Jan Camenisch , Els Van Herreweghen, Design and implementation of the idemix anonymous credential system, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586114]
• 7: J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact e-cash. In R. Cramer, editor, Advances in Cryptology | EUROCRYPT '05, volume 3494 of Lecture Notes in Computer Science, pages 302--321, 2005.
• 8: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 9: K. Cameron. The laws of identity, 2005.
• 10: J. Cates. Robust and effcient data management for a distributed hash table. Master's thesis, Massachusetts Institute of Technology, May 2003.
• 11: David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
• 12: David Chaum , Jan-Hendrik Evertse, A secure and privacy-protecting protocol for transmitting personal information between organizations, Proceedings on Advances in cryptology---CRYPTO '86, p.118-167, January 1987, Santa Barbara, California, United States
• 13: Consumer fraud and identity theft complaint data, 2006.
• 14: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 15: D. Hardt. Identity 2.0, 2005.
• 16: Robert Johnson , David Molnar , Dawn Xiaodong Song , David Wagner, Homomorphic Signature Schemes, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.244-262, February 18-22, 2002
• 17: Ralph C. Merkle, A Certified Digital Signature, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.218-238, August 20-24, 1989
• 18: Microsoft. Microsoft's vision for an identity metasystem, 2005.
• 19: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060313]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Performance, Security, Verification

Keywords:
PKI, credential, hash-tree, identity assertion, identity management, merkle tree, privacy