Abstract
A new type of signature scheme is proposed. It consists of two phases. The first phase is performed off-line, before the message to be signed is even known. The second phase is performed on-line, once the message to be signed is known, and is supposed to be very fast. A method for constructing such on-line/off-line signature schemes is presented. The method uses one-time signature schemes, which are very fast, for the on-line signing. An ordinary signature scheme is used for the off-line stage.
In a practical implementation of our scheme, we use a variant of Rabin's signature scheme (based on factoring) and DES. In the on-line phase all we use is a moderate amount of DES computation and a single modular multiplication. We stress that the costly modular exponentiation operation is performed off-line. This implementation is ideally suited for electronic wallets or smart cards.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bellare, M., and Micali, S., How To Sign Given Any Trapdoor Function,Proc. STOC 88, pp. 32–42.
Biham, E., and Shamir, A., Differential Cryptanalysis of DES-Like Cryptosystems,Journal of Cryptology, Vol. 4, No. 1, 1991, pp. 3–72.
Damgard, I., Collision-Free Hash Functions and Public-Key Signature Schemes,EuroCrypt 87, LNCS, Vol. 304, Springer-Verlag, Berlin, 1988, pp. 203–216.
Even, S., Secure Off-Line Electronic Fund Transfer Between Nontrusting Parties, inSmart Card 2000:The Future of IC Cards, D. Chaum and I. Schaumuller-Bichl (eds.), North-Holland, Amsterdam, 1989, pp. 57–66.
Even, S., Goldreich, O., and Yacobi, Y., Electronic Wallet,Advances in Cryptology: Proc. Crypto 83, D. Chaum (ed.), Plenum, New York, 1984, pp. 383–386.
Even, S., Goldreich, O., and Micali, S., On-Line/Off-Line Digital Signatures,Advances in Cryptology: Proc. Crypto 89, G. Brassard (ed.), LNCS, Vol. 435, Springer-Verlag, Berlin, 1990, pp. 263–277.
Goldreich, O., Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme,Advances in Cryptology—Crypto 86, A. M. Odlyzko (ed.), LNCS, Vol. 263, Springer-Verlag, Berlin, 1987, pp. 104–110.
Goldwasser, S., Micali, S., and Rivest, R. L., A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks,SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 281–308.
Hastad, J., Impagliazzo, R., Levin, L. A., and Luby, M., Construction of Pseudorandom Generator from Any One-Way Function, Manuscript, 1993. See preliminary versions by Impagliazzo, Levin, and Luby inProc. 21st STOC and by Hastad inProc. 22nd STOC.
Levin, L. A., One-Way Functions and Pseudorandom Generators,Combinatorica, Vol. 7, No. 4, 1987, pp. 357–363.
MacWilliams, F. J., and Sloane, N. J. A.,The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
Merkle, R. C., A Digital Signature Based on a Conventional Encryption Function,Advances in Cryptology—Crypto 87, C. Pomerance (ed.), LNCS, Vol. 293, Springer-Verlag, Berlin, 1987, pp. 369–378.
Naor, M., Bit Commitment Using Pseudorandom Generators,Proc. Crypto 89, pp. 123–132.
Naor, M., and Yung, M., Universal One-Way Hash Functions and Their Cryptographic Application,Proc. 21st STOC, 1989, pp. 33–43.
National Bureau of Standards,Federal Information Processing Standards, Publ. 46 (DES 1977).
Rabin, M. O., Digital Signatures, inFoundations of Secure Computation, R. A. DeMilloet al. (eds.), Academic Press, New York, 1978, pp. 155–168.
Rabin, M. O., Digitalized Signatures and Public-Key Functions as Intractable as Factorization, Report TR-212, Lab. for Computer Science, MIT, January 1979.
Rivest, R. L., The MD4 Message Digest Algorithm,Proc. Crypto 90, A. J. Menezes and S. A. Vanstone (eds.), LNCS, Vol. 537, Springer-Verlag, Berlin, 1991, pp. 303–311.
Rivest, R. L., The MD5 Message-Digest Algorithm, Internet Request for Comments, April 1992.
Rivest, R. L., Shamir, A., and Adleman, L., A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120–126.
Rompel, J., One-Way Functions Are Necessary and Sufficient for Secure Signatures,Proc. 22nd STOC, 1990, pp. 387–394.
Roth, R., Topics in Coding Theory, Lecture Notes, Computer Science Dept., Technion, Haifa, 1993.
Williams, H. C., A Modification of the RSA Public-Key Encryption Procedure,IEEE Transactions on Information Theory, Vol. 26, No. 6, 1980, pp. 726–729.
Yao, A. C., Theory and Applications of Trapdoor Functions,Proc. IEEE Symp. on Foundations of Computer Science, 1982, pp. 80–91.
Author information
Authors and Affiliations
Additional information
Communicated by Gilles Brassard
A preliminary version appeared in theProceedings of Crypto 89. Shimon Even was supported by the fund for the Promotion of Research at the Technion.
Rights and permissions
About this article
Cite this article
Even, S., Goldreich, O. & Micali, S. On-line/off-line digital signatures. J. Cryptology 9, 35–67 (1996). https://doi.org/10.1007/BF02254791
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02254791