zbMATH — the first resource for mathematics

On-line/off-line digital signatures. (English) Zbl 0844.94011
Summary: 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.

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] Bellare, M., and Micali, S., How To Sign Given Any Trapdoor Function,Proc. STOC 88, pp. 32-42. · Zbl 0715.94006
[2] Biham, E.; Shamir, A., Differential Cryptanalysis of DES-Like Cryptosystems, Journal of Cryptology, 4, 1, 3-72 (1991) · Zbl 0729.68017
[3] Damgard, I., Collision-Free Hash Functions and Public-Key Signature Schemes,EuroCrypt 87, 203-216 (1988), Berlin: Springer-Verlag, Berlin
[4] Even, S.; Chaum, D.; Schaumuller-Bichl, I., Secure Off-Line Electronic Fund Transfer Between Nontrusting Parties, Smart Card 2000:The Future of IC Cards, 57-66 (1989), Amsterdam: North-Holland, Amsterdam
[5] Even, S.; Goldreich, O.; Yacobi, Y.; Chaum, D., Electronic Wallet, Advances in Cryptology: Proc. Crypto 83, 383-386 (1984), New York: Plenum, New York
[6] Even, S.; Goldreich, O.; Micali, S.; Brassard, G., On-Line/Off-Line Digital Signatures, Advances in Cryptology: Proc. Crypto 89, 263-277 (1990), Berlin: Springer-Verlag, Berlin
[7] Goldreich, O.; Odlyzko, A. M., Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme, Advances in Cryptology—Crypto 86, 104-110 (1987), Berlin: Springer-Verlag, Berlin · Zbl 0635.94010
[8] Goldwasser, S.; Micali, S.; Rivest, R. L., A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing, 17, 2, 281-308 (1988) · Zbl 0644.94012
[9] 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.
[10] Levin, L. A., One-Way Functions and Pseudorandom Generators, Combinatorica, 7, 4, 357-363 (1987) · Zbl 0641.68061
[11] MacWilliams, F. J.; Sloane, N. J. A., The Theory of Error-Correcting Codes (1977), Amsterdam: North-Holland, Amsterdam · Zbl 0369.94008
[12] Merkle, R. C.; Pomerance, C., A Digital Signature Based on a Conventional Encryption Function, Advances in Cryptology—Crypto 87, 369-378 (1987), Berlin: Springer-Verlag, Berlin
[13] Naor, M., Bit Commitment Using Pseudorandom Generators,Proc. Crypto 89, pp. 123-132.
[14] Naor, M., and Yung, M., Universal One-Way Hash Functions and Their Cryptographic Application,Proc. 21st STOC, 1989, pp. 33-43.
[15] National Bureau of Standards,Federal Information Processing Standards, Publ. 46 (DES 1977).
[16] Rabin, M. O.; DeMillo, R. A., Digital Signatures, Foundations of Secure Computation, 155-168 (1978), New York: Academic Press, New York
[17] Rabin, M. O., Digitalized Signatures and Public-Key Functions as Intractable as Factorization, Report TR-212, Lab. for Computer Science, MIT, January 1979.
[18] Rivest, R. L.; Menezes, A. J.; Vanstone, S. A., The MD4 Message Digest Algorithm, Proc. Crypto 90, 303-311 (1991), Berlin: Springer-Verlag, Berlin · Zbl 0800.68418
[19] Rivest, R. L., The MD5 Message-Digest Algorithm, Internet Request for Comments, April 1992.
[20] Rivest, R. L.; Shamir, A.; Adleman, L., A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005
[21] Rompel, J., One-Way Functions Are Necessary and Sufficient for Secure Signatures,Proc. 22nd STOC, 1990, pp. 387-394.
[22] Roth, R., Topics in Coding Theory (1993), Haifa: Technion, Haifa
[23] Williams, H. C., A Modification of the RSA Public-Key Encryption Procedure, IEEE Transactions on Information Theory, 26, 6, 726-729 (1980) · Zbl 0466.94018
[24] Yao, A. C., Theory and Applications of Trapdoor Functions,Proc. IEEE Symp. on Foundations of Computer Science, 1982, pp. 80-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.