On the fly signatures based on factoring

ABSTRACT

In response to the current need for fast, secure and cheap public-key cryptography largely induced by the fast development of electronic commerce, we propose a new on the fly signature scheme, i.e. a scheme that requires very small on-line work for the signer It combines provable security based on the factorization problem, short public and secret keys, short transmission and minimal on-line computation. It is the first RSA-like signature scheme that can be used for both efficient and secure applications based on low cost or contactless smart cards.

REFERENCES

• 1: IEEE P1363 Draft (Standard Specifications For Pub|ic Key Cryptography), August 1998. Available from h~tp ://grouper. ieee. org/groups/1363/index, hcml
• 2: 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]
• 3: BELLARE, M., AND ROGAWAY, P. The Exact Security of Dzgital Signatures - How to Sign with RSA and Rabia. In Eurocrypt '96 (1996), LNCS 1070, Springex- Verlag, pp. 399--416.
• 4: BONEH, D, AND DURFEE, G. Cryptanalysis of RSA with Private Key d Less than n " . In Eurocryp~ 99 (1999), LNOS 1592, Springer-VerIag, pp. 1-11.
• 5: BONEIt, D., AND VENKATESAN, R. Breaking RSA May Not Be Equivalent to Factoring. In Eurocrypt '98 (1998), LNCS 1403, Springer-Verlag, pp. 59-71.
• 6: Ernest F. Brickell , Kevin S. McCurley, An interactive identification scheme based on discrete logarithms and factoring, Journal of Cryptology, v.5 n.1, p.29-39, 1992
• 7: Jan Camenisch , Markus Michels, A Group Signature Scheme with Improved Efficiency, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.160-174, October 18-22, 1998
• 8: CAMENISCH, J., AND MICHELS, M. Proving in Zero- Knowledge That a Number Is the Product of Two Safe Primes. In Eurocrypt '99 (1999), LNCS 1592, Springer- Verlag, pp. 107-122.
• 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: EL GAMAL, T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In IEEE Transactions on Information Theory (july 1985), vol. IT-31, no. 4, pp. 469-472.
• 11: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 12: 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
• 13: FUJIOKA, A., MIYAGUCHI, S., AND OKAMOTO, T. ES- IGN: An Efficient Digital Signature Implementation for Smart Cards. In Eurocrypt '91 (1992), LNCS 547, Springer-Verlag, pp. 446-457.
• 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: FUJISAKL E., AND OKAMOTO, T. A Practical and Provably Secure Scheme for Publicly Verifiable Secret Sharing and Its Applications. In Eurocrypt '98 (1998), LNCS 1403, Springer-Verlag, pp. 32-46.
• 16: Marc Girault, An identity-based identification scheme based on discrete logarithms modulo a composite number, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.481-486, February 1991, Aarhus, Denmark
• 17: GIRAULT, M. Self-certified public keys. In Eurocryp, '91 (1992), LNCS 547, Springer-Verlag, pp. 490--497.
• 18: Marc Girault , Jacques Stern, On the Length of Cryptographic Hash-Values Used in Identification Schemes, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.202-215, August 21-25, 1994
• 19: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 20: L. C. Guillou , J. J. Quisquater, A “paradoxical” identity-based signature scheme resulting from zero-knowledge, Proceedings on Advances in cryptology, p.216-231, February 1990, Santa Barbara, California, United States
• 21: LENSTRA, A., AND LENSTRA, H. The Development of the Number Field Szeve, vol. 1554 of Lecture No~es ~n Mathemat, cs. Springer-Verlag, 1993.
• 22: MENEZES, A., VAN OORSCHOT, P., AND VANSTONE~ S.
• 23: MII, LER, G. Riemann's hypothesis and tests for prireality. Journal of Computer and System Sciences I3 (1976), aoo-al 7.
• 24: NACCACHE, D., M'RAi'm, D., VAUDENAY, S., AND RAPnAELI, D. Can DSA be improved ? In Eurocrypi '94 (1995), LNCS 950, Springer-Verlag, pp. 77-85.
• 25: NIST. Digital Signature Standard (DSS). Federal Information Processing Standards PUBlication XX~ Draft, august 1991.
• 26: NIST. Secure Hash Standard (SHS) Federal Information Processing Standards PUBlication 180-1, april 1995
• 27: POINTCHEVAL, D., AND STERN, J. Security Proofs for Signature Schemes. In Eurocrypt '96 (1996), LNCS 1070, Springer-Ver{ag, pp. 387-398.
• 28: POINTCHEVAL, D., AND STERN, J. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology (1999). to appear, available at http://wwu, dmi. ens .fr/ pointche.
• 29: POUPARD, G., AND STERN, J. Security Analysis of a Practical "on the fly" Authentication and Signature Generation. In Eurocryp~ '98 (1998), LNCS 1403, Springer-Verlag, pp. 422-436.
• 30: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 31: P~Iv~sT, R. The MD5 Message-Digest Algorithm. RFC 1321, april 1992.
• 32: 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]
• 33: SCHNORP~, C. P. Efficient identification and Signatures for Smart Cards. Ia Crypta '89 (1990)~ LNCS 435, Springex-Verlag, pp. 235-251.
• 34: Sell,oaR, C. P. Efficient Signature Generation by Smaxt Caxds. Journal of Cryptolog~ .~, 3 (1991), 161- 174.
• 35: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 36: WI~.~eR, M. Cryptanalysis of short RSA secret exponents IEEE Transactwns on Informatwn Theory 36~ 3 (1990), 553-558.
• 37: WImNEa, M. Performance Comparison of Public-Key Cryptosystems. CryptoBytes 4, 1 (summer 1998), 1-5.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Smartcards

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Algorithms, Reliability, Security, Theory, Verification