An Efficient Existentially Unforgeable Signature Scheme and its Applications

  • Cynthia Dwork
  • Moni Naor
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


We present a practical existentially unforgeable signature scheme and point out applications where its application is desirable. A signature scheme is existentially unforgeable if, given any polynomial (in the security parameter) number of pairs
$$ (m_1 ,S(m_1 )),(m_2 ,S(m_2 )), \ldots (m_k ,S(m_k )) $$
where S(m) denotes the signature on the message m, it is computationally infeasible to generate a pair (m k+1, S(m k+1)) for any message m k+1 ∉ {m 1, ... m k{. We have developed a signature scheme that requires at most 6 times the amount of time needed to generate a signature using RSA (which is not existentially unforgeable).


Signature Scheme Internal Node Modular Exponentiation Choose Plaintext Attack Subset Product 
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.


  1. 1.
    M. Bellare and S. Micali, How to Sign Given Any Trapdoor Function, Proc. 20th ACM Annual Symposium on the Theory of Computing, 1988, pp.32–42.Google Scholar
  2. 2.
    J. Bos and D. Chaum, Provably Unforgeable Signatures, Proc. Advances in Cryptology — Crypto’92 Proceedings, Springer Verlag, 1993, pp. 1–14.Google Scholar
  3. 3.
    W. Diffie and M. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory 22(6), 1976, pp. 644-654.Google Scholar
  4. 4.
    T. El Gamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Inform. Theory, IT-31(4), 1985, pp. 469–472Google Scholar
  5. 5.
    S. Even, O. Goldreich, and S. Micali, On-line/Off-line Digital Signatures, Proc. Advances in Cryptology — Crypto’ 89, Springer Verlag, pp. 263–275, 1990.Google Scholar
  6. 6.
    A. Fiat, Batch RSA, Proc. Advances in Cryptology — Crypto’ 89, Springer Verlag, 1990.Google Scholar
  7. 7.
    A. Fiat and A. Shamir, How to Prove Yourself, Proc. of Advances in Cryptology — Crypto’ 86, Springer Verlag, 1987, pp. 641–654.Google Scholar
  8. 8.
    A. Fiat and A. Shamir, Method, Apparatus, and Article for Identification and Signature, United States Patent 4,748,668 (5/31/88)Google Scholar
  9. 9.
    O. Goldreich, Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme, Proc. Advances in Cryptology — Crypto’ 86, Springer Verlag, 1987.Google Scholar
  10. 10.
    S. Goldwasser, S. Micali, and R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM J. Computing 17(2), pp. 281–301, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    R. Impagliazzo and M. Naor, Efficient Cryptographic Schemes Provably as Secure as Subset Sum, Proc. of the 30th Symp. on Foundations of Computer Science, 1989, pp. 236–241. Full version: Technical Report CS93-12, Weizmann Institute.Google Scholar
  12. 12.
    R. Merkle, A Digital Signature Based on a Conventional Encryption Function, Proc. Advances in Cryptology — Crypto’ 87, Springer Verlag, 1988, pp. 369–378.Google Scholar
  13. 13.
    R. C. Merkle and M. Hellman, Hiding information and Signature in Trapdoor Knapsack, IEEE Transaction on Information Theory, Vol 24, 1978, pp. 525–530.CrossRefGoogle Scholar
  14. 14.
    S. Micali and A. Shamir, An Improvement of the Fiat-Shamir Identification and Signature Scheme, Proc. Advances in Cryptology — Crypto’ 88, LNCS 403, Springer-Verlag, pp. 244–247, 1990Google Scholar
  15. 15.
    M. Naor and M. Yung, Universal One Way Hash Functions and Their Cryptographic Applications, Proc. 21st ACM Annual Symposium on the Theory of Computing, 1989, pp. 33–43.Google Scholar
  16. 16.
    M. O. Rabin Digital Signatures and Public Key Functions as Intractable as Factoring, Technical Memo TM-212, Lab. for Computer Science, MIT, 1979.Google Scholar
  17. 17.
    R. Rivest, A. Shamir, and L. Adelman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of ACM, 21 (1978), pp. 120–126.zbMATHCrossRefGoogle Scholar
  18. 18.
    J. Rompel, One-way Function are Necessary and Sufficient for Signatures, Proc. 22nd ACM Annual Symposium on the Theory of Computing, 1990, pp. 387–394.Google Scholar
  19. 19.
    C. P. Schnorr, Efficient Signature Generation by Smart Cards, J. Cryptology 4, pp. 161–174, 1991.zbMATHCrossRefMathSciNetGoogle Scholar
  20. 20.
    A. Shamir, On the Generation of Cryptographically Strong Pseudo-Random Number Sequences, ACM Trans. Comput. Sys., 1 (1983), pp. 38–44.CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Cynthia Dwork
    • 1
  • Moni Naor
    • 2
  1. 1.IBM Almaden Research CenterUSA
  2. 2.Weizmann InstituteIsrael

Personalised recommendations