Twin signatures: an alternative to the hash-and-sign paradigm

ABSTRACT

This paper introduces a simple alternative to the hash-and-sign paradigm, from the security point of view but for signing short messages, called twinning. A twin signature is obtained by signing twice a short message by a signature scheme. Analysis of the concept in different settings yields the following results:

• We prove that no generic algorithm can efficiently forge a twin DSA signature. Although generic algorithms offer a less stringent form of security than computational reductions in the standard model, such successful proofs still produce positive evidence in favor of the correctness of the new paradigm.
• We prove in standard model an equivalence between the hardness of producing existential forgeries (even under adaptively chosen message attacks) of a twin version of a signature scheme proposed by Gennaro, Halevi and Rabin and the Flexible RSA Problem.

We consequently regard twinning as an interesting alternative to hash functions for eradicating existential forgery in signature schemes.

REFERENCES

• 1: Masayuki Abe , Tatsuaki Okamoto, A Signature Scheme with Message Recovery as Secure as Discrete Logarithm, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.378-389, November 14-18, 1999
• 2: N.Baric and B.P .tzmann.Collision-Free Accum lators and Fail-Stop Signature Schemes without Trees.In Eurocrypt '97 ,LNCS 1233,pages 480 -484.Springer-Verlag,Berlin,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: J.-S.Coron and D.Naccache.Security Analysis of the Gennaro-Halevi-Rabin Signature Scheme.In Eurocrypt '99 ,LNCS 1592,pages 91 -101. Springer-Verlag,Berlin,1999.
• 5: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, Proceedings of the 6th ACM conference on Computer and communications security, p.46-51, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319716]
• 6: T.El Gamal.A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory , IT -31(4):469 -472,July 1985.
• 7: 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
• 8: R.Gennaro,S.Halevi,and T.Rabin.Secure Hash-and-Sign Signature Without the Random Oracle.In Eurocrypt '99 ,LNCS 1592,pages 123 -139. Springer-Verlag,Berlin,1999.
• 9: 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]
• 10: IEEE P1363.Standard Speci .cations for Public Key Cryptography.Available from http://grouper.ieee.org/groups/1363 August 1998.
• 11: M.Jakobsson and C.P.Schnorr.Security of Discrete Logarithm Cryptosystems in the Random Oracle Model and Generic Model.Available from http://www.bell-labs.com/~markusj 1998.
• 12: H.Krawczyk and T.Rabin.Chameleon Hashing and Signatures.In Proc.of NDSS '2000 .Internet Society, 2000.
• 13: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 14: David M'Raïhi , David Naccache, Batch exponentiation: a fast DLP-based signature generation strategy, Proceedings of the 3rd ACM conference on Computer and communications security, p.58-61, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238187]
• 15: V.I.Nechaev.Complexity of a Determinate Algorithm for the Discrete Logarithm.Mathematical Notes ,55(2):165 -172,1994.
• 16: NIST.Digital Signature Standard (DSS).Federal Information Processing Standards PUBlication 186, November 1994.
• 17: K.Nyberg and R.A.Rueppel.Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem.In Eurocrypt '94 ,LNCS 950,pages 182 -193. Springer-Verlag,Berlin,1995.
• 18: J.M.Pollard.Monte Carlo Methods for Index Computation (mod p).Mathematics of Computation , 32(143):918 -924,July 1978.
• 19: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 20: C.P.Schnorr.E .cient Signature Generation by Smart Cards.Journal of Cryptolo y ,4(3):161 -174, 1991.
• 21: V.Shoup.Lower Bounds for Discrete Logarithms and Related Problems.In Eurocrypt '97 ,LNCS 1233, pages 256 -266.Springer-Verlag,Berlin,1997.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Security

Keywords:
digital signatures, discrete logarithm, flexible RSA problem, generic model, provable security, standard model