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 number of modular exponentiations in the total number of attributes. This limitation makes them unfit for many practical applications, such as electronic identity cards. Our novel approach can incorporate a large number of binary and finite-set attributes without significant performance impact. It compresses all such attributes into 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 values as prime numbers. We then use the divisibility property for efficient proofs of their presence or absence. In addition, we contribute efficient methods for conjunctions and disjunctions. The system builds on the strong RSA assumption. We demonstrate the aptness of our method in realistic application scenarios, notably electronic identity cards, and show its advantages for small devices, such as smartcards and cell phones.
Supplemental Material
Available for Download
The proof is given in an electronic appendix, available online in the ACM Digital Library.
- Ateniese, G., Camenisch, J., Joye, M., and Tsudik, G. 2000. A practical and provably secure coalition-resistant group signature scheme. In Advances in Cryptology (CRYPTO). M. Bellare Ed., Lecture Notes in Computer Science, vol. 1880. Springer Verlag, 255--270. Google ScholarDigital Library
- Barić, N. and Pfitzmann, B. 1997. Collision-free accumulators and fail-stop signature schemes without trees. In Advances in Cryptology (EUROCRYPT). W. Fumy Ed., Lecture Notes in Computer Science, vol. 1233. Springer Verlag, 480--494. Google ScholarDigital Library
- Bichsel, P., Camenisch, J., Groß, T., and Shoup, V. 2009. Anonymous credentials on a standard Java Card. In Proceedings of the 16th ACM Conference on Computer and Communications Security (CCS). ACM Press, 600--610. Google ScholarDigital Library
- Boneh, D., Boyen, X., and Shacham, H. 2004. Short group signatures. In Advances in Cryptology (CRYPTO). M. K. Franklin Ed., Lecture Notes in Computer Science, vol. 3152. Springer Verlag, 41--55.Google Scholar
- Boudot, F. 2000. Efficient proofs that a committed number lies in an interval. In Advances in Cryptology (EUROCRYPT). B. Preneel Ed., Lecture Notes in Computer Science, vol. 1807. Springer Verlag, 431--444. Google ScholarDigital Library
- Brands, S. 1993. An efficient off-line electronic cash system based on the representation problem. Tech. rep. CS-R9323, CWI. Google ScholarDigital Library
- Brands, S. 1995a. Restrictive blinding of secret-key certificates. Tech. rep. CS-R9509, CWI. Google ScholarDigital Library
- Brands, S. 1995b. Secret-key certificates. Tech. rep. CS-R9510, CWI. Google ScholarDigital Library
- Brands, S. 1997. Rapid demonstration of linear relations connected by boolean operators. In Advances in Cryptology (EUROCRYPT). W. Fumy Ed., Lecture Notes in Computer Science, vol. 1233. Springer Verlag, 318--333. Google ScholarDigital Library
- Brands, S. 1999. Rethinking public key infrastructure and digital certificates---building in privacy. Ph.D. thesis, Eindhoven Institute of Technology, The Netherlands.Google Scholar
- Camenisch, J. L. 1998. Group signature schemes and payment systems based on the discrete logarithm problem. Ph.D. thesis, No. 12520, ETH Zürich. Hartung Gorre Verlag, Konstanz.Google Scholar
- Camenisch, J. and Stadler, M. 1997. Efficient group signature schemes for large groups. In Advances in Cryptology (CRYPTO). B. Kaliski Ed., Lecture Notes in Computer Science, vol. 1296. Springer Verlag, 410--424. Google ScholarDigital Library
- Camenisch, J. and Michels, M. 1999. Proving in zero-knowledge that a number n is the product of two safe primes. In Advances in Cryptology (EUROCRYPT). J. Stern Ed., Lecture Notes in Computer Science, vol. 1592. Springer Verlag, 107--122. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2001. Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation. In Advances in Cryptology (EUROCRYPT). B. Pfitzmann Ed., Lecture Notes in Computer Science, vol. 2045. Springer Verlag, 93--118.Google Scholar
- Camenisch, J. and Lysyanskaya, A. 2002. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Advances in Cryptology (CRYPTO). M. Yung Ed., Lecture Notes in Computer Science, vol. 2442. Springer Verlag, 61--76. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2003. A signature scheme with efficient protocols. In Proceedings of the 3rd International Conference on Security in Communication Networks (SCN’02). S. Cimato, C. Galdi, and G. Persiano Eds., Lecture Notes in Computer Science, vol. 2576. Springer Verlag, 268--289. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2004. Signature schemes and anonymous credentials from bilinear maps. In Advances in Cryptology (CRYPTO). M. K. Franklin Ed., Lecture Notes in Computer Science, vol. 3152. Springer Verlag, 56--72.Google Scholar
- Camenisch, J. and Groß, T. 2011. Efficient attributes for anonymous credentials (extended version). Cryptology ePrint Archive Report 2010/496, IACR. http://eprint.iacr.org/.Google Scholar
- Camenisch, J., Hohenberger, S., and Lysyanskaya, A. 2005. Compact E-cash. In Advances in Cryptology (Eurocrypt). R. Cramer Ed., Lecture Notes in Computer Science, vol. 3494. Springer, 302--321. Google ScholarDigital Library
- Camenisch, J., Hohenberger, S., Kohlweiss, M., Lysyanskaya, A., and Meyerovich, M. 2006. How to win the clonewars: efficient periodic n-times anonymous authentication. In Proceedings of the ACM Conference on Computer and Communications Security. A. Juels, R. N. Wright, and S. D. C. di Vimercati Eds., ACM, 201--210. Google ScholarDigital Library
- Camenisch, J., Groß, T., and Scott-Heydt Benjamin, T. 2011. Efficient tight interval proofs with Camenisch-Groß encoding. IBM Res. rep. RZ 3800, IBM Research Division.Google Scholar
- Celebi, S. 2009. Design and implementation of efficient attribute-encoding in anonymous credentials. M.S. thesis, ETH Zurich.Google Scholar
- Chan, A., Frankel, Y., and Tsiounis, Y. 1998. Easy come---easy go divisible cash. In Advances in Cryptology (EUROCRYPT). K. Nyberg Ed., Lecture Notes in Computer Science, vol. 1403. Springer Verlag, 561--575.Google Scholar
- Chaum, D. 1981. Untraceable electronic mail, return addresses, and digital pseudonyms. Comm. ACM 24, 2, 84--88. Google ScholarDigital Library
- Chaum, D. 1983. Blind signatures for untraceable payments. In Advances in Cryptology (CRYPTO). D. Chaum, R. L. Rivest, and A. T. Sherman Eds., Plenum Press, 199--203.Google Scholar
- Chaum, D. 1985. Security without identification: Transaction systems to make big brother obsolete. Comm. ACM 28, 10, 1030--1044. Google ScholarDigital Library
- Chaum, D. and Evertse, J.-H. 1987. A secure and privacy-protecting protocol for transmitting personal information between organizations. In Advances in Cryptology (CRYPTO). M. Odlyzko Ed., Lecture Notes in Computer Science, vol. 263. Springer Verlag, 118--167. Google ScholarDigital Library
- Chaum, D. and van Heyst, E. 1991. Group signatures. In Advances in Cryptology (EUROCRYPT). D. W. Davies Ed., Lecture Notes in Computer Science, vol. 547. Springer Verlag, 257--265. Google ScholarDigital Library
- Chaum, D. and Pedersen, T. P. 1993. Wallet databases with observers. In Advances in Cryptology (CRYPTO). E. F. Brickell Ed., Lecture Notes in Computer Science, vol. 740. Springer Verlag, 89--105. Google ScholarDigital Library
- Cramer, R., Damgård, I., and Schoenmakers, B. 1994. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology (CRYPTO). Y. G. Desmedt Ed., Lecture Notes in Computer Science, vol. 839. Springer Verlag, 174--187. Google ScholarDigital Library
- Damgård, I. and Fujisaki, E. 2001. An integer commitment scheme based on groups with hidden order. http://eprint.iacr.org/2001.Google Scholar
- Fiat, A. and Shamir, A. 1987. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology (CRYPTO). A. M. Odlyzko Ed., Lecture Notes in Computer Science, vol. 263. Springer Verlag, 186--194. Google ScholarDigital Library
- Frankel, Y., Tsiounis, Y., and Yung, M. 1998. Fair off-line e-cash made easy. In Advances in Cryptology (ASIACRYPT). K. Kim and T. Matsumoto Eds., Lecture Notes in Computer Science, vol. 1514. Springer Verlag, 257--270. Google ScholarDigital Library
- Fujioka, A., Okamoto, T., and Ohta, K. 1992. A practical secret voting scheme for large scale elections. In Advances in Cryptology (ASIACRYPT). J. Seberry and Y. Zheng Eds., Lecture Notes in Computer Science, vol. 718. Springer, 244--251. Google ScholarDigital Library
- Fujisaki, E. and Okamoto, T. 1997. Statistical zero knowledge protocols to prove modular polynomial relations. In Advances in Cryptology (CRYPTO). B. Kaliski Ed., Lecture Notes in Computer Science, vol. 1294. Springer Verlag, 16--30. Google ScholarDigital Library
- Goldwasser, S., Micali, S., and Rivest, R. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 2, 281--308. Google ScholarDigital Library
- IBM. 2010. Specification of the Identity Mixer cryptographic library, v. 2.3.2. Specification, IBM Research. http://prime.inf.tu-dresden.de/idemix/.Google Scholar
- Kiayias, A. and Yung, M. 2006. Secure scalable group signature with dynamic joins and separable authorities. Int. J. Secur. Netw. 1, 1/2, 24--45. Google ScholarDigital Library
- Kiayias, A., Yung, M., and Tsiounis, Y. 2004. Traceable signatures. In Advances in Cryptology (EUROCRYPT). C. Cachin and J. Camenisch Eds., Lecture Notes in Computer Science, vol. 3027. Springer, 571--589.Google Scholar
- Miller, G. L. 1976. Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci. 13, 300--317. Google ScholarDigital Library
- Naor, M., Pinkas, B., and Sumner, R. 1999. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM Conference on Electronic Commerce. Google ScholarDigital Library
- Pedersen, T. P. 1992. Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology (CRYPTO). J. Feigenbaum Ed., Lecture Notes in Computer Science, vol. 576, Springer Verlag, 129--140. Google ScholarDigital Library
- Rabin, M. O. 1980. Probabilistic algorithm for testing primality. J. Number Theory 12, 128--138.Google ScholarCross Ref
- Rabin, M. O. and Shallit, J. O. 1986. Randomized algorithms in number theory. Comm. Pure Appl. Math. 39, 239--256.Google ScholarCross Ref
- Schnorr, C. P. 1991. Efficient signature generation for smart cards. J. Cryptology 4, 3, 239--252.Google ScholarDigital Library
- Shoup, V. 2008. A Computational Introduction to Number Theory and Algebra 2nd Ed. Cambridge University Press. http://www.shoup.net/ntb/. Google ScholarDigital Library
- SPF Intérieur. 2005. Instructions generales relatives à la carte d’indentité électronique. SPF Intérieur, Service Registres de la Population et Cartes d’identité, Bruxelles. http://www.registrenational.fgov.be.Google Scholar
- World Health Organization (WHO). 2005. International Statistical Classification of Diseases and Health Related Problems (ICD-10). 2nd Ed., 10th Rev. Ed. World Health Organization, Geneva.Google Scholar
Index Terms
- Efficient Attributes for Anonymous Credentials
Recommendations
Efficient attributes for anonymous credentials
CCS '08: Proceedings of the 15th ACM conference on Computer and communications securityWe 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 ...
Anonymous credentials light
CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications securityWe define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the ...
Privacy-Enhancing Proxy Signatures from Non-interactive Anonymous Credentials
DBSec 2014: Proceedings of the 28th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy XXVIII - Volume 8566Proxy signatures enable an originator to delegate the signing rights for a restricted set of messages to a proxy. The proxy is then able to produce valid signatures only for messages from this delegated set on behalf of the originator. Recently, two ...
Comments