Concurrently-secure credential ownership proofs

ABSTRACT

We address the case in credential systems where a credential owner wants to show her credential to a verifier without taking the risk that the ability to prove ownership of the same (and any other) credential is transferred to the verifier. We define credential ownership proof protocols for credentials signed by standard signature schemes. We also propose proper security definitions for the protocol, aiming to protect the security of both the credential issuer and the credential owner against concurrent attacks. We give two generic constructions of credential ownership proofs based on identity-based encryption and identity-based identification schemes. Furthermore, we show that signatures with credential ownership proofs are equivalent to identity-based identification schemes, in the sense that any secure construction of each implies a secure construction of the other. Finally, we show that the GQ identification protocol yields an efficient credential ownership proof for credentials signed by the RSA-FDH signature scheme of Bellare and Rogaway and prove the protocol concurrently-secure.

REFERENCES

• 1: J. Baek, R. Safavi-Naini, and W. Susilo. Universal designated verifier signature proof (or how to efficiently prove knowledge of a signature). In B. K. Roy, editor, ASIACRYPT, volume 3788 of Lecture Notes in Computer Science, pages 644--661. Springer, 2005.
• 2: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 3: M. Bellare, C. Namprempre, and G. Neven. Security proofs for identity-based identification and signature schemes. In C. Cachin and J. Camenisch, editors, EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 268--286. Springer, 2004.
• 4: Mihir Bellare , Chanathip Namprempre , David Pointcheval , Michael Semanko, The Power of RSA Inversion Oracles and the Security of Chaum's RSA-Based Blind Signature Scheme, Proceedings of the 5th International Conference on Financial Cryptography, p.319-338, February 19-22, 2002
• 5: Mihir Bellare , Adriana Palacio, GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.162-177, August 18-22, 2002
• 6: M. Bellare and P. Rogaway. The exact security of digital signatures - how to sign with rsa and rabin. In EUROCRYPT, pages 399--416, 1996.
• 7: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 8: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 9: S. Brands. Rethinking Public Key Infrastructure and Digital Certificates --- Building in Privacy. PhD thesis, Eindhoven Institute of technology, The Netherlands, 1999.
• 10: 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]
• 11: 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
• 12: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 13: Ronald Cramer , Ivan Damgård , Philip D. MacKenzie, Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.354-372, January 18-20, 2000
• 14: Y. Desmedt, Subliminal-free authentication and signature, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.23-33, April 1988, Davos, Switzerland
• 15: Y. Desmedt and K. Kurosawa. Practical and proven zero-knowledge constant round variants of gq and schnorr. TIEICE: IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Science, E82-A(1):69--76, 1999.
• 16: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 17: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 18: 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
• 19: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 20: 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]
• 21: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 22: K. Kurosawa and S.-H. Heng. From digital signature to id-based identification/signature. In F. Bao, R. H. Deng, and J. Zhou, editors, Public Key Cryptography, volume 2947 of Lecture Notes in Computer Science, pages 248--261. Springer, 2004.
• 23: Anna A. Lysyanskaya , Ronald L. Rivest, Signature schemes and applications to cryptographic protocol design, 2002
• 24: Anna Lysyanskaya , Ronald L. Rivest , Amit Sahai , Stefan Wolf, Pseudonym Systems, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.184-199, August 09-10, 1999
• 25: Proceedings on Advances in cryptology---CRYPTO '86, January 1987
• 26: Tatsuaki Okamoto , Kazuo Ohta, How to Utilize the Randomness of Zero-Knowledge Proofs, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.456-475, August 11-15, 1990
• 27: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 28: R. Steinfeld, L. Bull, H. Wang, and J. Pieprzyk. Universal designated-verifier signatures. In C.-S. Laih, editor, ASIACRYPT, volume 2894 of Lecture Notes in Computer Science, pages 523--542. Springer, 2003.
• 29: B. Waters. Efficient identity-based encryption without random oracles. In R. Cramer, editor, EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 114--127. Springer, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Security

Keywords:
credential systems, designated-verifier signatures, identification schemes, identity-based cryptography, signature schemes