Efficient attributes for anonymous credentials

ABSTRACT

We extend the Camenisch-Lysyanskaya anonymous credential system such that selective disclosure of attributes becomes highly efficient. The resulting system significantly improves upon existing approaches, which suffer from a linear complexity in the total number of attributes. This limitation makes them unfit for many practical applications, such as electronic identity cards. Our system can incorporate an arbitrary number of binary and finite-set attributes without significant performance impact. Our approach folds all such attributes in a single attribute base and, thus, boosts the efficiency of all proofs of possession. The core idea is to encode discrete binary and finite-set attribute values as prime numbers. We use the divisibility property for efficient proofs of their presence or absence. We additionally contribute efficient methods for conjunctions and disjunctions. The system builds on the Strong-RSA assumption alone. We demonstrate the applicability and performance improvements of our method in realistic application scenarios, such as, electronic identity cards and complex/structured credentials. Our method has crucial advantages in devices with restricted computational capabilities, such as smartcards and cell phones.

REFERENCES

• 1: American Psychiatric Association. Diagnostic and Statistical Manual of Mental Disorders (DSM-IV-TR). American Psychiatric Publishing Inc., 1000 Wilson Boulevard, Suite 1825, Arlington, VA 22209, fourth edition, text revision edition, 2000. ISBN 9780890420249.
• 2: Association for Computing Machinery (ACM). ACM computing classification system (CCS). http://oldwww.acm.org/class/1998/ccs98.html, 2007.
• 3: Giuseppe Ateniese , Jan Camenisch , Marc Joye , Gene Tsudik, A Practical and Provably Secure Coalition-Resistant Group Signature Scheme, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.255-270, August 20-24, 2000
• 4: D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. K. Franklin, editor, Advances in Cryptology -- CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 41--55. Springer Verlag, 2004.
• 5: F. Boudot. Efficient proofs that a committed number lies in an interval. In B. Preneel, editor, Advances in Cryptology -- EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 431--444. Springer Verlag, 2000.
• 6: Stefan A. Brands, An Efficient Off-line Electronic Cash System Based On The Representation Problem., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1993
• 7: Stefan A. Brands, Restrictive blinding of secret-key certificates, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 8: Stefan A. Brands, Secret-key certificates, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 9: S. Brands. Rapid demonstration of linear relations connected by boolean operators. In W. Fumy, editor, Advances in Cryptology -- EUROCRYPT '97, volume 1233 of Lecture Notes in Computer Science, pages 318--333. Springer Verlag, 1997.
• 10: S. Brands. Rethinking Public Key Infrastructure and Digital Certificates-- Building in Privacy. PhD thesis, Eindhoven Institute of Technology, Eindhoven, The Netherlands, 1999.
• 11: Jan Camenisch , Susan Hohenberger , Markulf Kohlweiss , Anna Lysyanskaya , Mira Meyerovich, How to win the clonewars: efficient periodic n-times anonymous authentication, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180431]
• 12: J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact E-cash. In R. Cramer, editor, Advances in Cryptology -- Eurocrypt 2005, volume 3494 of Lecture Notes in Computer Science, pages 302--321. Springer, 2005.
• 13: 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
• 14: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 15: J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In S. Cimato, C. Galdi, and G. Persiano, editors, Security in Communication Networks, Third International Conference, SCN 2002, volume 2576 of Lecture Notes in Computer Science, pages 268--289. Springer Verlag, 2003.
• 16: J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In M. K. Franklin, editor, Advances in Cryptology -- CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 56--72. Springer Verlag, 2004.
• 17: J. Camenisch and M. Michels. Proving in zero--knowledge that a number n is the product of two safe primes. In J. Stern, editor, Advances in Cryptology -- EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 107--122. Springer Verlag, 1999.
• 18: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 19: J. L. Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, 1998. Diss. ETH No. 12520, Hartung Gorre Verlag, Konstanz.
• 20: A. Chan, Y. Frankel, and Y. Tsiounis. Easy come -- easy go divisible cash. In K. Nyberg, editor, Advances in Cryptology -- EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 561--575. Springer Verlag, 1998.
• 21: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 22: D. Chaum. Blind signatures for untraceable payments. In D. Chaum, R. L. Rivest, and A. T. Sherman, editors, Advances in Cryptology -- Proceedings of CRYPTO '82, pages 199--203. Plenum Press, 1983.
• 23: 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]
• 24: 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
• 25: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 26: D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, Advances in Cryptology -- EUROCRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 257--265. Springer-Verlag, 1991.
• 27: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 28: I. Damgård and E. Fujisaki. An integer commitment scheme based on groups with hidden order. http://eprint.iacr.org/2001, 2001.
• 29: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 30: Yair Frankel , Yiannis Tsiounis , Moti Yung, Fair Off-Line e-cash Made Easy, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.257-270, October 18-22, 1998
• 31: Atsushi Fujioka , Tatsuaki Okamoto , Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.244-251, December 13-16, 1992
• 32: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 33: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 34: Aggelos Kiayias , Moti Yung, Secure scalable group signature with dynamic joins and separable authorities, International Journal of Security and Networks, v.1 n.1/2, p.24-45, September 2006 [doi>10.1504/IJSN.2006.010821]
• 35: A. Kiayias, M. Yung, and Y. Tsiounis. Traceable signatures. In C. Cachin and J. Camenisch, editors, Advances in Cryptology -- EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 571--589. Springer, 2004.
• 36: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 37: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 38: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 39: C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239--252, 1991.
• 40: SPF Intérieur. Instructions generales relatives à la carte d'indentité électronique. SPF Intérieur, Service Registres de la Population et Cartes d'identité, Parc Atrium, rue des Colonies, 11, 1000 Bruxelles, November 2005. http://www.registrenational.fgov.be.
• 41: E. W. Weisstein. Prime number theorem. From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PrimeNumberTheorem.html, March 2008.
• 42: Wikipedia. DSM-IV codes. http://en.wikipedia.org/wiki/DSM-IV_Codes, March 2008.
• 43: World Health Organization (WHO). International Statistical Classification of Diseases and Health Related Problems (ICD-10). World Health Organization, Geneva, 2nd edition, 10th revision edition, 2005.
• 44: World Health Organization (WHO). ICD-10 codes. http://www.who.int/classifications/apps/icd/icd10online, 2007.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Performance, Security

Keywords:
anonymous credential systems, cryptographic protocols, efficient attribute encoding, privacy