Abstract
We provide evidence that the unforgeability of several discrete-log based signatures like Schnorr signatures cannot be equivalent to the discrete log problem in the standard model. This contradicts in nature well-known proofs standing in weakened proof methodologies, in particular proofs employing various formulations of the Forking Lemma in the random oracle Model. Our impossibility proofs apply to many discrete-log-based signatures like ElGamal signatures and their extensions, DSA, ECDSA and KCDSA as well as standard generalizations of these, and even RSA-based signatures like GQ. We stress that our work sheds more light on the provable (in)security of popular signature schemes but does not explicitly lead to actual attacks on these.
Chapter PDF
Similar content being viewed by others
References
ANSI X9.62, Public-Key fryptography for the financial services industry: the elliptic curve digital standard algorithm (ECDSA), American National Standards Institute (1999)
Bellare, M., Boldyreva, A., Palacio, A.: An Un-Instantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188. Springer, Heidelberg (2004)
Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The One-More-RSA-Inversion Problems and the security of Chaum’s Blind Signature Scheme. J. Cryptology 16(3), 185–215 (2003)
Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002)
Boneh, D., Venkatesan, R.: Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998)
Brickell, E., Pointcheval, D., Vaudenay, S., Yung, M.: Design Validations for discrete logarithm based signature schemes. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 276–292. Springer, Heidelberg (2000)
Brown, D.R.L.: Generic Groups, Collision Resistance and ECDSA. Des. Codes Cryptography 35, 119–152 (2005)
Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. J. Assoc. Comput. Mach. 51(4), 557–594 (2004)
FIPS 186. Digital Signature Standard, Federal Information Processing Standards Publication 186. US Department of Commerce/NIST, National Technical Information Service, Springfield, Virginia (1994)
Dent, A.: Adapting the weaknesses of the random oracle model to the generic model. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 100–109. Springer, Heidelberg (2002)
Dodis, Y., Reyzin, L.: On the Power of Claw-Free Permutations. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 55–73. Springer, Heidelberg (2003)
El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory IT–31(4), 469–472 (1985)
Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Goldwasser, S., Tauman, Y.: On the (In)security of the Fiat-Shamir Paradigm. In: FOCS 2003, pp. 102–122. IEEE Computer Society, Los Alamitos (2003)
Guillou, L.C., Quisquater, J.-J.: A ”Paradoxical” Identity-Based Signature Scheme Resulting from Zero-Knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 216–231. Springer, Heidelberg (1990)
Horster, P., Petersen, H., Michels, M.: Meta-ElGamal signature schemes. In: CCS 1994: Proceedings of the 2nd ACM Conference on Computer and communications security, pp. 96–107. ACM Press, New York (1994)
KCDSA, Digital Signature Mechanism with Appendix - Part 2: Certificate-Based Digital Signature Algorithm (KCDSA), TTA.KO -12.0001 (1998)
Nielsen, J.B.: Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002)
Pointcheval, D., Stern, J.: Security Arguments for Digital Signatures and Blind Signatures. J. Cryptology 13(3), 361–396 (2000)
Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991)
Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
Shoup, V.: Lower Bounds for Discrete Logarithms and Related Problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paillier, P., Vergnaud, D. (2005). Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log. In: Roy, B. (eds) Advances in Cryptology - ASIACRYPT 2005. ASIACRYPT 2005. Lecture Notes in Computer Science, vol 3788. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593447_1
Download citation
DOI: https://doi.org/10.1007/11593447_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30684-9
Online ISBN: 978-3-540-32267-2
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
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.