Abstract
This paper, for the first time, presents a provably secure signature scheme with message recovery based on the (elliptic-curve) discrete logarithm. The proposed scheme can be proven to be secure in the strongest sense (i.e., existentially unforgeable against adaptively chosen message attacks) in the random oracle model under the (elliptic-curve) discrete logarithm assumption. We give the concrete analysis of the security reduction. When practical hash functions are used in place of truly random functions, the proposed scheme is almost as efficient as the (elliptic-curve) Schnorr signature scheme and the existing schemes with message recovery such as (elliptic-curve) Nyberg-Rueppel and Miyaji schemes.
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
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: Proc. of the First ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures –How to Sign with RSA and Rabin. In: Proc. of Eurocrypt 1996. LNCS, pp. 399–416. Springer, Heidelberg (1996)
Bleichenbacher, D.: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998)
Canetti, R., Goldreich, O., Halevi, S.: The RandomO racle Methodology, Revisited. In: Proc. of STOC, pp. 209–218. ACM Press, New York (1998)
Naccache, J.S.D., Stern, J.P.: On the Security of RSA Padding. In: Proc. of Crypto 1999. LNCS, Springer, Heidelberg (1999)
ElGamal, 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. In: Proc. of Crypto 1986. LNCS, pp. 186–194. Springer, Heidelberg (1986)
Feige, U., Fiat, A., Shamir, A.: Zero-Knowledge Proofs of Identity. J. of Cryptology 1, 77–94 (1988)
Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. on Computing 17, 281–308 (1988)
Koblitz, N.: Elliptic Curve Cryptosystems. Mathematics of Computation 48, 203–209 (1987)
Miyaji, A.: A Message Recovery Signature Scheme Equivalent to DSA over Elliptic Curves. In: Proc. of Asiacrypt 1996. LNCS, pp. 1–14. Springer, Heidelberg (1996)
Naor, M., Yung, M.: Universal One-Way Hash Functions and Their Cryptographic Applications. In: Proc. of STOC, pp. 33–43 (1989)
Nyberg, K., Rueppel, R.A.: A New Signature Scheme Based on the DSA Giving Message Recovery. In: Proc. of the First ACM Conference on Computer and Communications Security (1993)
Nyberg, K., Rueppel, R.A.: Message Recovery for Signature Schemes Based on the Discrete LogarithmProb lem. In: Proc. of Eurocrypt 1994. LNCS, pp. 182–193. Springer, Heidelberg (1995)
Nyberg, K., Rueppel, R.A.: Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem. Designs, Codes and Cryptography 7, 61–81 (1996)
Ohta, K., Okamoto, T.: On the Concrete Security Treatment of Signatures Derived fromI dentification. In: Proc. of Crypto 1998. LNCS. Springer, Heidelberg (1998)
Pointcheval, D., Stern, J.: Security Proofs for Signature Schemes. In: Proc. of Eurocrypt 1996. LNCS, pp. 387–398. Springer, Heidelberg (1996)
Rompel, J.: One-Way Functions are Necessary and Sufficient for Secure Signature. In: Proc. of STOC, pp. 387–394 (1990)
Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of ACM 21(2), 120–126 (1978)
Schnorr, C.P.: Efficient Identification and Signatures for Smart Card. In: Proc. of Eurocrypt 1989. LNCS, pp. 235–251. Springer, Heidelberg (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abe, M., Okamoto, T. (1999). A Signature Scheme with Message Recovery as Secure as Discrete Logarithm. In: Lam, KY., Okamoto, E., Xing, C. (eds) Advances in Cryptology - ASIACRYPT’99. ASIACRYPT 1999. Lecture Notes in Computer Science, vol 1716. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-48000-6_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66666-0
Online ISBN: 978-3-540-48000-6
eBook Packages: Springer Book Archive