Efficient digital signature algorithm and use thereof technical field

Abstract

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.

Inventors

• 👤 Silvio Micali

Bibliographic Details