Abstract
Digital Signatures enable authenticating messages in a way that disallows repudiation. While non-repudiation is essential in some applications, it might be undesirable in others. Two related notions of authentication are: Deniable Authentication (see Dwork, Naor and Sahai [25]) and Ring Signatures (see Rivest, Shamir and Tauman [38]). In this paper we show how to combine these notions and achieve Deniable Ring Authentication: it is possible to convince a verifier that a member of an ad hoc subset of participants (a ring) is authenticating a message m without revealing which one (source hiding), and the verifier V cannot convince a third party that message m was indeed authenticated - there is no ‘paper trail’ of the conversation, other than what could be produced by V alone, as in zero-knowledge.
We provide an efficient protocol for deniable ring authentication based on any strong encryption scheme. That is once an entity has published a public-key of such an encryption system, it can be drafted to any such ring. There is no need for any other cryptographic primitive. The scheme can be extended to yield threshold authentication (e.g. at least k members of the ring are approving the message) as well.
Research supported in part by the RAND/APX grant from the EU Program IST
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among notions of security for public-key encryption schemes, Advances in Cryptology-saCRYPTO’98, LNCS 1462, Springer, pp. 26–45.
M. Bellare and P. Rogaway, Optimal Asymmetric Encryption, Advances in Cryptology-Eurocrypt’ 94, LNCS 950, Springer, 1995, pp. 92–111.
Dan Boneh, Simplified OAEP for the RSA and Rabin Functions, Advances in Cryptology-CRYPTO 2001, LNCS2139, Springer 2001, pp. 275–291.
D. Boneh and M. Franklin, Anonymous Authentication with Subset Queries, ACM Conference on Computer and Communications Security 1999, pp. 113-119.
D. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, Advances in Cryptology-CRYPTO 2001, LNCS 2139, Springer, 2001, pp. 213–229.
J. Boyar, D. Chaum, I. Damg°ard and T. P. Pedersen: Convertible Undeniable Signatures, Advances in Cryptology-CRYPTO’90, Springer, 1991, pp. 189–205.
E. Bresson, J. Stern and M. Szydlo, Threshold Ring Signatures for Ad-hoc Groups, Advances in Cryptology-CRYPTO/r'2002, (these proceedings).
J. Camenisch, Efficient and Generalized Group Signatures, Advances in Cryptology-EUROCRYPT’97, LNCS 1233, Springer, 1997, pp. 465–479.
J. Camenisch and I. Damg°ard, Verifiable Encryption, Group Encryption, and Their Applications to Group Signatures and Signature Sharing Schemes, Advances in Cryptology-Asiacrypt 2000, LNCS 1976, Springer, 2000, pp. 331–345.
J. Camenisch and A. Lysyanskaya, An Identity Escrow Scheme with Appointed Verifiers, Advances in Cryptology-Crypto 2001, LNCS 2139, Springer, 2001, pp. 388–407.
J. Camenisch, M. Michels, Separability and Efficiency for Generic Group Signature Schemes, Advances in Cryptology-CRYPTO’99, LNCS 1666, Springer, 1999, pp. 106–121.
J. Camenisch and M. Stadler, Efficient Group Signature Schemes for Large Groups, Advances in Cryptology-CRYPTO’97, LNCS 1294, Springer, 1997, pp. 410–424.
R. Canetti, C. Dwork, M. Naor and R. Ostrovsky, Deniable Encryption, Advances in Cryptology-CRYPTO’97, LNCS 1294, Springer, 1997, pp. 90–104.
D. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Comm. of ACM, vol. 24(2), 1981, pp. 84–88.
D. Chaum and H. van Antwerpen, Undeniable Signatures, Advances in Cryptology-CRYPTO’89, LNCS 435, Springer, 1990, pp. 212–216.
D. Chaum and E. van Heyst, Group Signatures, Advances in Cryptology-EUROCRYPT’91, LNCS 541, Springer, 1991, pp. 257–265.
D. Chaum and E. van Heyst and B. Pfitzmann, Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer, Advances in Cryptology-CRYPTO’91, LNCS 576, Springer, 1992, pp. 470–484.
C. Cocks. An identity based encryption scheme based on quadratic residues, Cryptography and Coding, LNCS 2260, Springer, 2001, pp. 360–363.
R. Cramer, I. Damg°ard, B. Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Advances in Cryptology-CRYPTO’94, LNCS, Springer, 1994, pp. 174–187.
R. Cramer and V. Shoup, A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack, Advances in Cryptology-CRYPTO’98, LNCS 1462, Springer, 1998, pp. 13–25.
A. De Santis, G. Di Crescenzo, G. Persiano, M. Yung, On Monotone Formula Closure of SZK, Proc. 35th IEEE FOCS, 1994, pp. 454–465.
W. Diffie, and M.E. Hellman. New Directions in Cryptography. IEEE Trans. on Info. Theory, IT-22 (Nov. 1976), pages 644–654.
D. Dolev, C. Dwork and M. Naor, Non-malleable Cryptography, Siam J. on Computing, vol 30, 2000, pp. 391–437.
C. Dwork and M. Naor, Zaps and Their Applications, Proc. 41st IEEE Symposium on Foundations of Computer Science, pp. 283–293. Full version: ECCC, Report TR02-001,http://www.eccc.uni-trier.de/eccc/.
C. Dwork, M. Naor and A. Sahai, Concurrent Zero-Knowledge, Proc. 30th ACM Symposium on the Theory of Computing, Dallas, 1998, pp. 409–418.
A. Fiat and A. Shamir, How to Prove Yourself: Practical Solutions to Identification and Signature Problems, Advances in Cryptology-CRYPTO’86, LNCS 263, Springer, 1987, pp. 186–194.
E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, RSA-OAEP Is Secure under the RSA Assumption, Advances in Cryptology-CRYPTO 2001, pp. 260–274.
R. Gennaro, H. Krawczyk and T. Rabin, RSA-Based Undeniable Signatures, Advances in Cryptology-CRYPTO’97, LNCS 1294, Springer, 1997, pp. 132–149.
O. Goldreich and Y. Oren, Definitions and properties of Zero-Knowledge proof systems, J. of Cryptology, Vol 7, 1994, pp.1–32.
S. Goldwasser, S. Micali and R. Rivest, A secure digital signature scheme, SIAM J. on Computing 17, 1988, pp. 281–308.
M. Jakobsson, K. Sako and R. Impagliazzo, Designated Verifier Proofs and Their Applications, Advances in Cryptology-EUROCRYPT’ 96, pp. 143–154.
J. Katz, Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications Cryptology, ePrint Archive, Report 2002//027, http://www.eprint.iacr.org/
J. Kilian, A Note on Efficient Zero-Knowledge Proofs and Arguments, Proc. 24th ACM Symposium on the Theory of Computing, 1992, pp. 723–732.
J. Kilian and E. Petrank, Identity Escrow, Advances in Cryptology-CRYPTO’ 98 LNCS 1462, 1998, pp. 169–185.
H. Krawczyk and T. Rabin, Chameleon Hashing Signatures, Proceedings of Network and Distributed Systems Security Symposium (NDSS) 2000, Internet Society, pp. 143–154.
M. Naor. Bit Commitment Using Pseudo-Randomness, Journal of Cryptology, vol. 4, 1991, pp. 151–158.
D. Naor, M. Naor and J. B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Advances in Cryptology-CRYPTO 2001, pp. 41–62. LNCS 2139, Springer, 2001, pp. 205-219. Full version: Cryptology ePrint Archive, Report 2001/059, http://www.eprint.iacr.org/
R. L. Rivest, A. Shamir, and Y. Tauman, How to Leak A Secret, Advances in Cryptology-ASIACRYPT 2001, Lecture Notes in Computer Science, Vol. 2248, Springer, pp. 552–565.
A. Sahai, Non-Malleable Non-Interactive Zero Knowledge and Achieving Chosen-Ciphertext Security, Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999, pp. 543–553.
A. Shamir, How to Share a Secret, Communications of the ACM 22, 1979, pp. 612–613.
A. Shamir, Identity-Based Cryptosystems and Signature Schemes, Advances in Cryptology-CRYPTO’84, LNCS 196, Springer, 1985, pp. 47–53.
V. Shoup, OAEP Reconsidered, Advances in Cryptology-CRYPTO 2001, LNCS, Springer, 2001, pp. 239–259.
Bibliography on Secret Sharing Schemes, maintained by D. Stinson and R. Wei. http://www.cacr.math.uwaterloo.ca/~dstinson/ssbib.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Naor, M. (2002). Deniable Ring Authentication. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_31
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive