New approaches for deniable authentication

ABSTRACT

Deniable Authentication protocols allow a Sender to authenticate a message for a Receiver, in a way that the Receiver cannot convince a third party that such authentication (or any authentication) ever took place.We present two new approaches to the problem of deniable authentication. The novelty of our schemes is that they do not require the use of CCA-secure encryption (all previous known solutions did), thus showing a different generic approach to the problem of deniable authentication. This new approach is practically relevant as it leads to more efficient protocols and security reductions.In the process we point out a subtle definitional issue for deniability. In particular we propose the notion of forward deniability, which requires that the authentications remain deniable even if the Sender wants to later prove that she authenticated a message. We show that forward deniability is not implied by the original notion of deniability, by showing some deniable protocols which are not forward deniable. Our new proposals are forward deniable.

REFERENCES

• 1: Yonatan Aumann , Michael O. Rabin, Authentication, Enhanced Security and Error Correcting Codes (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.299-303, August 23-27, 1998
• 2: Y. Aumann and M. Rabin, Efficient deniable authentication of long messages, in International Conference on Theoretical Computer Science in honor of Professor Manuel Blum's 60th birthday, April 20-24, 1998. Available from: http://www.cs.cityu.edu.hk/dept/video.html.
• 3: 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]
• 4: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 5: L. Carter and M.N. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences, vol. 18, n. 2, pp. 143--154, 1979.
• 6: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 7: W. Diffie and M.E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, vol. 22, n. 6, pp. 644--654, 1976.
• 8: M. Di Raimondo, R. Gennaro, and H. Krawczyk, Deniable authentication and plaintext awareness, Manuscript.
• 9: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 10: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 11: J. Garay, P. MacKenzie and K. Yang, Strengthening Zero-Knowledge Protocols Using Signatures, Advances in Cryptology - proc. of EUROCRYPT '03, LNCS 2656, Springer-Verlag, pp. 177--194, 2003.
• 12: R. Gennaro, Multi-trapdoor Commitments and their Applications to Proofs of Knowledge Secure under Concurrent Man-in-the-middle Attacks, Advances in Cryptology - proc. of CRYPTO '04, LNCS 3152, Springer-Verlag, 2004.
• 13: R. Gennaro and V. Shoup, A Note on An Encryption Scheme of Kurosawa and Desmedt, http://eprint.iacr.org/2004/194/.
• 14: S. Goldwasser and S. Micali, Probabilistic Encryption, Journal of Computer and System Sciences, vol. 28, n. 2, pp. 270--299, 1984.
• 15: 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]
• 16: 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]
• 17: O. Goldreich, S. Micali and A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have Zero-Knowledge Proof Systems, in proc. of 27th IEEE Annual Symposium on the Foundations of Computer Science, vol. 38, n. 1, pp. 691--729, July 1991.
• 18: P. Gutman, Secure Deletion of Data from Magnetic and Solid-State Memory, Sixth USENIX Security Symposium Proceedings, San Jose, California, July 22--25, 1996.
• 19: D. Harkins and D. Carrel, ed., "The Internet Key Exchange (IKE)", RFC 2409, Nov. 1998.
• 20: M. Jakobsson, K. Sako and R. Impagliazzo, Designated Verifier Proofs and Their Applications, Advances in Cryptology - proc. of EUROCRYPT '96, LNCS 1070, Springer-Verlag, pp. 143--154, 1996.
• 21: J. Katz, Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications, Advances in Cryptology - proc. of EUROCRYPT '03, LNCS 2656, Springer-Verlag, pp. 211--228, 2003.
• 22: 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
• 23: K. Kurosawa and Y. Desmedt, A New Paradigm of Hybrid Encryption Scheme, Advances in Cryptology - proc. of CRYPTO '04, LNCS 3152, Springer-Verlag, pp. 426--442, 2004.
• 24: P. MacKenzie and K. Yang, On Simulation-Sound Commitments, Advances in Cryptology - proc. of EUROCRYPT '04, LNCS 3027, Springer-Verlag, pp. 382--400, 2004.
• 25: W. Mao and K.G. Paterson. On the plausible deniability feature of Internet protocols. Manuscript.
• 26: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 27: Moni Naor, Deniable Ring Authentication, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.481-498, August 18-22, 2002
• 28: R. Pass, On Deniability in the Common Reference String and Random Oracle Model, Advances in Cryptology - proc. of CRYPTO '03, LNCS 2729, Springer-Verlag, pp. 316--337, 2003.
• 29: 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
• 30: V. Shoup, Using hash functions as a hedge against chosen ciphertext attack, Advances in Cryptology - proc. of EUROCRYPT '00, LNCS 1807, Springer-Verlag, pp. 275--288, 2000.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Security, Theory

Keywords:
authentication, concurrency, deniability, zero-knowledge