Efficiency improvements for signature schemes with tight security reductions

ABSTRACT

Much recent work has focused on constructing efficient digital signature schemes whose security is tightly related to the hardness of some underlying cryptographic assumption. With this motivation in mind, we show here two approaches which improve both the computational efficiency and signature length of some recently-proposed schemes:Diffie-Hellman signatures. Goh and Jarecki [18] recently analyzed a signature scheme which has a tight security reduction to the computational Diffie-Hellman problem. Unfortunately, their scheme is less efficient in both computation and bandwidth than previous schemes relying on the (related) discrete logarithm assumption. We present a modification of their scheme in which signing is 33% more efficient and signatures are 75% shorter; the security of this scheme is tightly related to the decisional Diffie-Hellman problem.PSS. The probabilistic signature scheme (PSS) designed by Bellare and Rogaway [3] uses a random salt to enable a tight security reduction to, e.g., the RSA problem. Coron [12] subsequently showed that a shorter random salt can be used without impacting the security of the scheme. We show a variant of PSS which avoids the random salt altogether yet has an equally-tight security reduction. This furthermore yields a version of PSS-R (PSS with message recovery) with optimal message length. Our technique may also be used to improve the efficiency of a number of other schemes.

REFERENCES

• 1: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 2: Ernest F. Brickell , David Pointcheval , Serge Vaudenay , Moti Yung, Design Validations for Discrete Logarithm Based Signature Schemes, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.276-292, January 18-20, 2000
• 3: 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]
• 4: David Chaum , Hans van Antwerpen, Undeniable signatures, Proceedings on Advances in cryptology, p.212-216, July 1989, Santa Barbara, California, United States
• 5: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 6: J.-S. Coron. Optimal security proofs for PSS and other signature schemes. Eurocrypt 2002. Full version available at http://eprint.iacr.org/2001/062/.
• 7: Y. Dodis and L. Reyzin. On the power of claw-free permutations. Security in Communication Networks 2002.
• 8: T. El Gamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory 31(4): 469--472 (1985).
• 9: Federal Information Processing Standards publication #186-2. 2000. Digital signature standard (DSS). U.S. Department of Commerce/National Institute of Standards and Technology.
• 10: 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
• 11: Eiichiro Fujisaki , Tatsuaki Okamoto , David Pointcheval , Jacques Stern, RSA-OAEP Is Secure under the RSA Assumption, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.260-274, August 19-23, 2001
• 12: E.-J. Goh and S. Jarecki. A signature scheme as secure as the Diffie-Hellman problem. Eurocrypt 2003.
• 13: 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]
• 14: Louis Granboulan, Short Signatures in the Random Oracle Model, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.364-378, December 01-05, 2002
• 15: J. Jonsson. An OAEP variant with a tight security proof. Available at http://eprint.iacr.org/2002/034/.
• 16: Ueli M. Maurer , Stefan Wolf, The Diffie–Hellman Protocol, Designs, Codes and Cryptography, v.19 n.2-3, p.147-171, March 2000 [doi>10.1023/A:1008302122286]
• 17: S. Micali and L. Reyzin. Improving the exact security of digital signature schemes. J. Cryptology 15(1): 1--18 (2002).
• 18: D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology 13(3): 361--396 (2000).
• 19: Claus P. Schnorr, Efficient identification and signatures for smart cards, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.688-689, November 1990, Houthalen, Belgium
• 20: V. Shoup. Lower bounds for discrete logarithms and related problems. Eurocrypt '97.
• 21: Victor Shoup, OAEP Reconsidered, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.239-259, August 19-23, 2001
• 22: V. Shoup. A proposal for an ISO standard for public-key encryption. Available at http://eprint.iacr.org/2001/112.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Security, Theory

Keywords:
digital signatures