Abstract
Undeniable signatures are like ordinary digital signatures, except that testing validity of a signature requires interaction with the signer. This gives the signer additional control over who will benefit from being convinced by a signature, and is particularly relevant when signing sensitive, non-public data. Convertible undeniable signatures offer additional flexibility in that there is a separate verification key that can be used to verify a signature (without interaction). This allows the signer to delegate the ability to verify signatures to one or more participants, and ultimately to convert all signatures to ordinary ones by making the verification key public. While provably secure theoretical solutions exist for convertible schemes, earlier practical schemes proposed have either been broken or their status as far as security is concerned is very unclear. In this paper, we present two new convertible schemes, in which forging signatures is provably equivalent to forging El Gamal signatures. The difficulty of verifying signatures without interacting with the signer is based on the factoring problem for one of the schemes and on the Diffie-Hellman problem for the other scheme.
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
J. Boyar, D. Chaum, I. Damgård, and T. Pedersen. Convertible Undeniable Signatures. In Advances in Cryptology — proceedings of CRYPTO 90, Lecture Notes in Computer Science, pages 189–205. Springer-Verlag, 1991.
D. Chaum, J.-H. Evertse, and J. van de Graaf. An Improved Protocol for Demonstrating Possession of a Discrete Logarithm and some Generalizations. In Advances in Cryptology — proceedings of EUROCRYPT 87, Lecture Notes in Computer Science, pages 127–141, 1987.
D. Chaum. Zero-Knowledge Undeniable Signatures. In Advances in Cryptology — proceedings of EUROCRYPT 90, Lecture Notes in Computer Science, pages 458–464. Springer Verlag, 1991.
D. Chaum and T.P. Pedersen. Wallet Databases with Observers. In Advances in Cryptology — proceedings of CRYPTO 92, Lecture Notes in Computer Science, pages 89–105. Springer-Verlag, 1993.
D. Chaum and H. van Antwerpen. Undeniable Signatures. In Advances in Cryptology — proceedings of CRYPTO 89, Lecture Notes in Computer Science, pages 212–216. Springer Verlag, 1990.
W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Trans. Inform. Theory, IT-22(6):644–654, November 1976.
Y. Desmedt and M. Yung. Weaknesses of Undeniable Signature Schemes. In Advances in Cryptology — proceedings of EUROCRYPT 91, volume 547 of Lecture Notes in Computer Science, pages 205–220. Springer-Verlag, 1991.
T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Advances in Cryptology — proceedings of CRYPTO 84, Lecture Notes in Computer Science, pages 10–18. Springer-Verlag, 1985.
A. Fujioka, T. Okamoto and K. Ohta. Interactive Bi-Proof Systems and Undeniable Signature Schemes. In Advances in Cryptology — proceedings of EUROCRYPT 91, volume 547 of Lecture Notes in Computer Science, pages 243–256. Springer-Verlag, 1991.
O. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions. In Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science, 1984.
S. Goldwasser, S. Micali, and R. L. Rivest. A Digital Signature Scheme Secure against Adaptive Chosen Message Attack. SIAM Journal on Computing, 17(2):281–308, April 1988.
S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof-Systems. SIAM Journal of Computation, 18(1):186–208, 1989.
M. Jakobsson, K. Sako and R. Impagliazzo: Designated Verifier Proofs and Their Applications, 1996. These proceedings.
S. Micali, August 1990. Personal communication.
M. Michels. Breaking and Repairing a Convertible Undeniable Signature Scheme. Technical Report TR-95-10-D, University of Technology, Chemnitz-Zwickau, June 1995. To appear at ACM Security, March 1996.
M. O. Rabin. Digitalized Signatures and Public-Key Functions as Intractable as factorization. Technical Report MIT/LCS/TR-212, Laboratory for Computer Science, MIT, January 1979.
C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.
S. S. Wagstaff Jr. Greatest of the Least Primes in Arithmetic Progression Having a Given Modulus. Mathematics of Computation, 33(147):1073–1080, July 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Pedersen, T. (1996). New Convertible Undeniable Signature Schemes. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_32
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive