Efficient digital signature algorithm and use thereof technical field

• US 5,537,475 A
• Filed: 02/01/1994
• Issued: 07/16/1996
• Est. Priority Date: 02/01/1994
• Status: Expired due to Term

• Current Assignee: Silvio Micali
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/189,977
• Time in Patent Office: 896 Days
• Field of Search: 380/23, 380/25, 380/30, 380/28
• US Class Current: 380/30
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

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.

Claims

1. A digital signature scheme wherein the signature of a message M relative to a public key is computed by means of a secret key by:

(a) selecting a number x independent of M;

(b) computing a string σ

dependent on M, wherein the string σ

together with the secret key specify a permutation G.sub.σ

composed from a given set of permutations, the secret key is a number that squared mod n at least once, yields a number computable from public information identifying the signer;

(c) applying the permutation G.sub.σ

to the number x to produce a string z; and

(d) releasing the string z and the string σ

as the digital signature of the message M.

2. The digital signature scheme as described in claim 1 wherein the string σ

is obtained from the number x and the message M by a computation that includes hashing.

3. The digital signature scheme as described in claim 1 wherein the yielded number is 4.

4. The digital signature scheme as described in claim 1 wherein a group of signers share the same public key, and wherein at least two of the signers have distinct secret keys.

5. The digital signature scheme as described in claim 4 wherein a given agent computes the secret key of at least one signer.

6. The digital signature scheme as described in claim 1 wherein the set of given permutations include one permutation mapping a square mode n to S·

x² mod n, where S is a given number.

7. The digital signature scheme as described in claim 1 wherein the public key includes a composite number n and one permutation in the set of permutations maps a square mod n to Sx² mod n, where S is a fixed number.

8. The digital signature scheme as described in claim 7, wherein a group of signers share the same public key and at least two of the signers have distinct secret keys.

9. The digital signature scheme as described in claim 8 wherein at least one agent computes the secret key of at least one signer.

10. The digital signature scheme as described in claim 8 wherein a set of agents choose the secret key of at least one signer, and wherein information in possession of a single agent does not enable the single agent to compute the secret keys.