Signature schemes based on the strong RSA assumption

ABSTRACT

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.

REFERENCES

• 1: Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
• 2: N. Bari6 and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Advances in Oryptology-Eurocrypt '97, pages 480--494, 1997.
• 3: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 4: Mihir Bellare , Phillip Rogaway, Collision-Resistant Hashing: Towards Making UOWHFs Practical, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 17-21, 1997
• 5: D. Bleiehenbacher. Bl~ciency and security of cryptosysterns based on number theory. Phi) thesis, Swiss Federal Institute of Technology Zurich, 1996.
• 6: J. Brillhart, D. Lehmer, and J. Selfridge. New primality criteria and factorizations of 2m :i: 1. Math. Comp., 29:620-647, 1975.
• 7: Ronald Cramer , Ivan Damgård, New Generation of Secure and Practical RSA-Based Signatures, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.173-185, August 18-22, 1996
• 8: I. Damgard, P. Landrock, and C. Pomerance. Average case error estimates for the strong probable prime test. Math. Comp., 61:177-194, 1993.
• 9: Cynthia Dwork , Moni Naor, An Efficient Existentially Unforgeable Signature Scheme and its Applications, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.234-246, August 21-25, 1994
• 10: R. Gennaro, S. Halevi, and T. Rabin. Secure hash-andsign signatures without the random oracle. In Advances in Oryptology--Eurocrypt '99, pages 123-139, 1999.
• 11: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 12: L. C. Guillou , J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.123-128, April 1988, Davos, Switzerland
• 13: H. Krawczyk and T. Rabin. Chameleon hashing and signatures. Preprint, Theory oj Cryptography L,brary, March 1998.
• 14: Chae Hoon Lim , Pil Joong Lee, More Flexible Exponentiation with Precomputation, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.95-107, August 21-25, 1994
• 15: U. Mattrer. Fast generation of prime numbers and secure public-key cryptographic parameters. J. Cryptology, 8:123-155, 1995.
• 16: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 17: M. O. Rabin. Probabilistic algorithms for testing prireality. J. o} Number Theory, 12:128-138, 1980.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Security, Theory, Verification