# 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)

## Abstract

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).

## Keywords

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.

## References

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.
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.
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.
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.
20. 20.
A. Shamir, On the Generation of Cryptographically Strong Pseudo-Random Number Sequences, ACM Trans. Comput. Sys., 1 (1983), pp. 38–44.