k-anonymous secret handshakes with reusable credentials

ABSTRACT

The problem of privacy-preserving authentication has been extensively investigated in a set of diverse system settings. However, a full-fledged such mechanism called secret handshake, whereby two users (e.g., CIA agents) authenticate each other in a way that no one reveals its own membership (or credential) unless the peer's legitimacy was already ensured of, remains to be elusive because simultaneity of authentication must be guaranteed even in the presence of an active adversary that may act as a handshake initiator or responder. The state-of-the-art secret handshake scheme is very efficient, but imposes on the users the following restriction: either they have to use one-time credentials, or they have to suffer from the privacy degradation that all the sessions involving a same user (or credential are trivially linkable. In this paper, we present the first secret handshake schemes that achieve unlinkability while allowing the users to reuse their credentials (i.e., unlinkability is not achieved by means of one-time credentials). Specifically, we introduce the concept of $k$-anonymous secret handshakes where $k$ is an adjustable parameter indicating the desired anonymity assurance. We present a detailed construction based on public key cryptosystems, and sketch another based on symmetric key cryptosystems. Both schemes are efficient, and can even be seamlessly integrated into a standard public key infrastructure (PKI). Moreover, and their security analysis does not resort to any random oracle.

REFERENCES

• 1: M. Abadi. Private authentication. In Proceedings of the 2002 Workshop on Privacy Enhancing Technologies, pages 27--40, 2003.
• 2: William Aiello , Steven M. Bellovin , Matt Blaze , John Ioannidis , Omer Reingold , Ran Canetti , Angelos D. Keromytis, Efficient, DoS-resistant, secure key exchange for internet protocols, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586118]
• 3: Dirk Balfanz , Glenn Durfee , Narendar Shankar , Diana Smetters , Jessica Staddon , Hao-Chi Wong, Secret Handshakes from Pairing-Based Key Agreements, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.180, May 11-14, 2003
• 4: Mihir Bellare , Alexandra Boldyreva , Anand Desai , David Pointcheval, Key-Privacy in Public-Key Encryption, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.566-582, December 09-13, 2001
• 5: M. Bellare and P. Rogaway. Optimal asymmetric encryption. In A. D. Santis, editor, EUROCRYPT94, pages 92--111. Springer, 1995. Lecture Notes in Computer Science No. 950.
• 6: R Blom, An optimal class of symmetric key generation systems, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.335-338, December 1985, Paris, France
• 7: Carlo Blundo , Alfredo De Santis , Amir Herzberg , Shay Kutten , Ugo Vaccaro , Moti Yung, Perfectly-Secure Key Distribution for Dynamic Conferences, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.471-486, August 16-20, 1992
• 8: C. Boyd, W. Mao, and K. Paterson. Deniable authenticated key establishment for internet protocols. In the Proceedings of Security Protocols, 2003.
• 9: C. Castelluccia, S. Jarecki, and G. Tsudik. Secret handshakes from ca-oblivious encryption. In P. Lee, editor, Advances in Cryptology - ASIACRYPT 2004, volume ??? of Lecture Notes in Computer Science, pages ???--??? Springer, 2004.
• 10: D. Chaum. Blind signatures for untraceable payments. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 199--203, New York, 1983. Plenum Press.
• 11: D. Chaum and E. V. Heyst. Group signatures. In D. W. Davies, editor, Advances in Cryptology --- Eurocrypt '91, pages 257--265, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 547.
• 12: 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
• 13: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 14: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, IT-22:644--654, Nov. 1976.
• 15: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 16: Eiichiro Fujisaki , Tatsuaki Okamoto , David Pointcheval , Jacques Stern, RSA-OAEP Is Secure under the RSA Assumption, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.260-274, August 19-23, 2001
• 17: 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]
• 18: 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]
• 19: D. Harkins and D. Carrel. RFC 2409: The Internet Key Exchange (IKE). Internet Activities Board, 1998.
• 20: Jason E. Holt , Robert W. Bradshaw , Kent E. Seamons , Hilarie Orman, Hidden Credentials, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005142]
• 21: M. Jakobsson, K. Sako, and R. Impagliazzo. Designated verifier proofs and their applications. In Proc. EUROCRYPT 96, pages 143--154.
• 22: H. Krawczyk. Sigma: The 'sign-and-mac' approach to authenticated diffie-hellman and its use in the ike-protocols. In D. Boneh, editor, Proc. CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 400--425. Springer-Verlag, 2002.
• 23: Ninghui Li , Wenliang Du , Dan Boneh, Oblivious signature-based envelope, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.182-189, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872061]
• 24: Moni Naor, Deniable Ring Authentication, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.481-498, August 18-22, 2002
• 25: Pino Persiano , Ivan Visconti, User privacy issues regarding certificates and the TLS protocol: the design and implementation of the SPSL protocol, Proceedings of the 7th ACM conference on Computer and communications security, p.53-62, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352609]
• 26: Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
• 27: Ronald L. Rivest , Adi Shamir , Yael Tauman, How to Leak a Secret, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.552-565, December 09-13, 2001
• 28: R. Sakai, K. Ohgishi, and M. Kasahara. Cryptosystems based on pairing. In Proceedings of the Symposium on Cryptography and Information Security (SCIS), 2002.
• 29: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 30: Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948128]
• 31: S. Xu and M. Yung. k-anonymous secret handshakes with reusable credentials. Full version of the present paper.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

General Terms:
Security

Keywords:
anonymity, credential systems, privacy-preserving authentication, reusable credentials, secret handshake, unlinkability