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 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: BARIC, N. AND PFITZMANN, B. 1997. Collision-free accumulators and fail-stop signature schemes without trees. In Proceedings of the Conference on Advances in Cryptology (EUROCRYPT'97, Berlin, Germany), W. Fumy, Ed. Springer-Verlag, New York, NY, 480-494.
• 3: BATEMAN, P. AND HORN, R. 1962. A heuristic asymptotic formula concerning the distribution of prime numbers. Math. Comput. 16, 363-367.
• 4: BATEMAN, P. AND HORN, R. 1965. Primes represented by irreducible polynomials in one variable. In Proceedings of the Symposium on Pure Mathematics . 119-135.
• 5: 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]
• 6: 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
• 7: BLEICHENBACHER, D. 1996. Efficiency and security of cryptosystems based on number theory. Ph.D. Dissertation. Swiss Federal Institute of Technology, Zurich, Switzerland.
• 8: BRILLHART, J., LEHMER, D., AND SELFRIDGE, J. 1975. New primality criteria and factorizations of 2 m 61. Math. Comput. 29, 620-647.
• 9: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 10: 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
• 11: DAMGAARD, I., LANDROCK, P., AND POMERANCE, C. 1993. Average case error estimates for the strong probable prime test. Math. Comput. 61, 204 (Oct.), 177-194.
• 12: 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
• 13: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 14: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 15: GENNARO, R., HALEVI, S., AND RABIN, T. 1999. Secure hash-and-sign signatures without the random oracle. In Proceedings of the Conference on Advances in Cryptology (EUROCRYPT '99). Springer-Verlag, New York, NY, 123-139.
• 16: 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]
• 17: 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
• 18: HALBERSTAM, H. AND RICHERT, H. 1974. Sieve Methods. Academic Press, Inc., Duluth, MN.
• 19: IMPAGLIAZZO, R. AND ZUCKERMANN, D. 1989. How to recycle random bits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS '89, Research Triangle Park, NC, Oct. 30-Nov. 1). IEEE Computer Society Press, Los Alamitos, CA, 248-253.
• 20: Joe Kilian , Phillip Rogaway, How to Protect DES Against Exhaustive Key Search, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.252-267, August 18-22, 1996
• 21: KRAWCZYK, H. AND RABIN, T. 1998. Chameleon Hashing and Signatures.
• 22: 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
• 23: Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
• 24: MAURER, U. 1995. Fast generation of prime numbers and secure public-key cryptographic parameters. J. Cryptology 8, 123-155.
• 25: 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]
• 26: David Pointcheval , Jacques Stern, Provably Secure Blind Signature Schemes, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.252-265, November 03-07, 1996
• 27: RABIN, M. O. 1980. Probabilistic algorithms for testing primality. J. Number Theory 12, 128-138.
• 28: ROSSER, J. AND SCHOENFELD, L. 1962. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6, 64-94.
• 29: SCHWEINBERGER, T. AND SHOUP, V. 2000. ACE: The Advanced Cryptographic Engine. Cryptology ePrint Archive, Report 2000/022. http://eprint.iacr.org.
• 30: SHA AND NIST. 1995. NIST FIPS PUB 180-1, Secure Hash Standard. National Institute of Standards and Technology, Gaithersburg, MD.
• 31: SHOUP, V. 2000a. A composition theorem for universal one-way hash functions. In Proccedings of the Workshop on Advances in Cryptology (EUROCRYPT 2000). Springer-Verlag, New York, NY.
• 32: SHOUP, V. 2000b. Using hash functions as a hedge against chosen ciphertext attack. In Proccedings of the Workshop on Advances in Cryptology (EUROCRYPT 2000). Springer-Verlag, New York, NY.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Algorithms, Security, Theory

Keywords:
RSA, digital signatures, provable security