Deniable authentication and key exchange

ABSTRACT

We extend the definitional work of Dwork,Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE)protocol.SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first "natural" application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security).SIGMA, on the other hand,uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, "partial deniability" property: a party may not be able to deny that it was "alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors.We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

REFERENCES

• 1: Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276854]
• 2: Mihir Bellare , Anand Desai , David Pointcheval , Phillip Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.26-45, August 23-27, 1998
• 3: M. Bellare and A. Palacio. The Knowledge of Exponent Assumptions and 3-Round Zero-Knowledge Protocols. CRYPTO '04, LNCS 3152, 273--289, Springer 2004.
• 4: M. Bellare and A. Palacio. Towards Plaintext-Aware Public-Key Encryption without Random Oracles. ASIACRYPT '04,LNCS 3329,48--62, Springer 2004.
• 5: Mihir Bellare , Phillip Rogaway, Entity Authentication and Key Distribution, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.232-249, August 22-26, 1993
• 6: M.Bellare and P.Rogaway.Optimal Asymmetric Encryption. EUROCRYPT '94,LNCS 950, 92--111,Springer 1994.
• 7: Nikita Borisov , Ian Goldberg , Eric Brewer, Off-the-record communication, or, why not to use PGP, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029200]
• 8: C. Boyd, W. Mao and K. Paterson. Key Agreement using Statically Keyed Authenticators. ACNS 2004, LNCS 3089, 248--262, Springer 2004.
• 9: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 10: Ran Canetti , Hugo Krawczyk, Universally Composable Notions of Key Exchange and Secure Channels, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.337-351, May 02, 2002
• 11: Ran Canetti , Hugo Krawczyk, Security Analysis of IKE's Signature-Based Key-Exchange Protocol, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.143-161, August 18-22, 2002
• 12: 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]
• 13: D. Chaum. Blind Signatures for Untraceable Payments. CRYPTO '82, 199--203,Plenum 1982.
• 14: 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]
• 15: David Chaum , Hans Van Antwerpen, Undeniable Signatures, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.212-216, August 20-24, 1989
• 16: S. Chawla, C. Dwork, F. McSherry, A. Smith and H. Wee. Toward Privacy in Public Databases.TCC '05,LNCS 3378, 363--385, Springer 2005.
• 17: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 18: 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
• 19: Ivan Damgård, Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.445-456, August 11-15, 1991
• 20: A. Dent. Cramer-Shoup is Plaintext-Aware in the Standard Model. EUROCRYPT '06,LNCS 4004, 289--307, Springer 2006.
• 21: Mario Di Raimondo , Rosario Gennaro, New approaches for deniable authentication, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102137]
• 22: Mario Di Raimondo , Rosario Gennaro , Hugo Krawczyk, Secure off-the-record messaging, Proceedings of the 2005 ACM workshop on Privacy in the electronic society, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102199.1102216]
• 23: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 24: C. Dwork and K. Nissim. Privacy-Preserving Datamining on Vertically Partitioned Databases. CRYPTO '04, LNCS 3152, 528--544, Springer 2004.
• 25: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004 [doi>10.1145/1039488.1039489]
• 26: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 27: 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]
• 28: Satoshi Hada , Toshiaki Tanaka, On the Existence of 3-Round Zero-Knowledge Protocols, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.408-423, August 23-27, 1998
• 29: D. Harkins , D. Carrel, The Internet Key Exchange (IKE), RFC Editor, 1998
• 30: ISO/IEC IS 9798-3,"Entity authentication mechanisms ¿ Part 3: Entity authentication using asymmetric techniques ", 1993.
• 31: M. Jakobsson, K. Sako and R. Impagliazzo. Designated Verifier Proofs and Their Applications.EUROCRYPT '96, LNCS 1070, 143--154, Springer 1996.
• 32: J. Katz, Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications. EUROCRYPT '03, LNCS 2656, 211--228, Springer 2003.
• 33: C. Kaufman, ed., Internet Key Exchange (IKEv2) Protocol, draft-ietf-ipsec-ikev2-17. txt, September 2004 (pending RFC).
• 34: H. Krawczyk, SKEME: a versatile secure key exchange mechanism for Internet, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.114, February 22-23, 1996
• 35: H. Krawczyk. SIGMA: The 'SiGn-and-MAc 'Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols. CRYPTO '03,LNCS 2729, 400--425, Springer 2003. Available at www.research.ibm.com/security/sigma.p
• 36: Y. Lindell and B. Pinkas. Privacy Preserving Data Mining. J. of Cryptology, 15(3): 177--206, Springer 2002.
• 37: Chae Hoon Lim , Pil Joong Lee, A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroupp, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.249-263, August 17-21, 1997
• 38: W. Mao and K. G. Paterson. On the Plausible Deniability Feature of Internet Protocols. Manuscript.
• 39: R. Pass. On Deniability in the Common Reference String and Random Oracle Model. CRYPTO '03, LNCS 2729, 316--337, Springer 2003.
• 40: 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
• 41: V. Shoup. On Formal Models for Secure Key Exchange. IBM Research Report RZ 3120, April 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

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

General Terms:
Security, Theory

Keywords:
authentication, deniability, key exchange