Abstract

A digital signature scheme wherein the signature of a message M relative to a public key is computed by means of a secret key. The scheme begins by having the user select a number x independent of M. This step may occur off-line and before there is any knowledge of the particular message M to be signed. To sign the message, the routine computes a description of a function G which is dependent of the message M, and then applies the function G to x to produce a string z. The routine outputs z and a description of a second function F as the desired signature of the message M. Thus according to the invention a signature of the message is obtained by applying to an independent argument x a function dependent on M. This operation provides enhanced efficiency and security over the prior art and facilitates use of the scheme to allow multiple users of a secure communications system to share the same public key; alternatively, the scheme is useful for generating short certificates of public keys used in such systems.

Other References

• "Contemporary Cryptology"Edition by G. Simmons, 1992, pp. 348-350, Techniques for Digital Signatures
• Konigs, H.-P.: "Cryptographic Identification Methods for Smart Cards in the Process of Standardization", IEEE Communications Magazine, vol. 29, No. 6 (Jun. 1991), pp. 42-48
• Rivest, et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, " Comm. ACM, vol. 21, pp. 120-126 (Feb. 1978)
• Rabin, "Digitized Signatures as Intractable as Factorization, " MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-212, Massachusetts Institute of Technology, Cambridge, MA, pp. 1-26 (Jan. 1979)
• Williams, "A Modification of RSA Public-Key Cryptosystem," IEEE Trans. Information Theory, vol. IT-26, pp. 726-729 (1980)
• Goldwasser, et al., "A Digital Signature Secure Against Adaptive Chosen-Message Attacks", SIAM J. Comput., vol. 17, No. 2, pp. 281-308 (Apr. 1988)
• Goldreich, "Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme", Proc. Crypto 86, pp. 1-9 (Sept. 1986)
• Even, et al., "On-Line/Off-line Digital Signatures", Proc. Crypto 89, Springer Verlag, pp. 264-275 (1990)
• Fiat, et al., "How to Prove Yourself Practical Solutions of Identification and Signature Problems", Proc. Crypto 86, Springer Verlag, pp. 186-194
• Micali, et al., "An Improvement of the Fiat-Shamir Identification and Signature Scheme", Proc. Crypto 88, pp. 244-247 (Mar. 1988). Springer-Verlag
• Ong, et al., "Fast Signature Generation with a Fiat-Shamir Like Scheme", Proceedings of Eurocrypt 90, pp. 432-440 (1991). Springer-Verlag
• Schnorr, C.-P. "Efficient Identification and Signatures for Smart Cards", Proc. Crypto 89, Springer Verlag, pp. 239-252 (1990)
• National Institute of Standard and Technology, "A Digital Signature Standard as Described in Debating Encryption Standards," Comm. ACM, vol. 35, No. 7, pp. 33-54, (Jul. 1992)
• Merkle, R. "A Certified Digital Signature," Proc. Crypto 89, Springer Verlag, pp. 218-238 (1990)
• Naor, et al., "Universal Hash Functions and Their Cryptographic Applications,"Proc. 21st Annual Symposium the Theory of Computing, ACM, pp. 33-43 (1989)
• Shamir, A. "Identity-Based Cryptosystems and Signature Schemes,"Proc. Crypto 84 pp. 47-53 (1985). Springer-Velag
• Bellare, et al., "How to Sign Any Trapdoor Permutation," Journal of ACM, vol. 39, No. 1, pp. 214-233 (Jan., 1992)
• Guillou, et al., "A Paradoxial Identity-Based Signature Scheme Resulting from Zero-Knowledge," Proceedings Crypto 88, pp. 216-231 (1988). Springer-Velag
• Elgamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," IEEE Trans. on Information Theory, vol. IT-31, No. 4, pp. 469-472 (Jul., 1985