US5432852A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Large provably fast and secure digital signature schemes based on secure hash functions
Assignee: Individual
•
Filing: 1993-09-29
•
Granted: 1995-07-11
•
Expires: 2013-09-29
Abstract
Abstract The present invention describes new digital signature schemes that are provably secure against any adaptive chosen-message attack. The scheme, which is based on selection of a hash function from a space of such functions, has a very short public key, fast signing, a reasonable signature length and high security. Several algorithmic techniques are provided for enhancing the efficiency of the signature scheme in terms of time and memory.
Inventors
- 👤 Frank T. Leighton
- 👤 Silvio Micali
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 18:23
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/3236; H04L9/08; H04L9/0816; H04L9/0819; H04L9/083; H04L9/0833; H04L9/0836; H04L9/30; H04L9/3006; H04L9/3013; H04L9/302; H04L9/3247; H04L9/50; H04L2209/00; H04L2209/30
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
105 words
A method for generating a digital signature of a message, comprising the steps of: (a) choosing a secret key including a set of pseudoramdom integers; (b) generating a verification key by evaluating at least once a one-way function on a string that is derived at least in part from one or more of the pseudorandom integers and security information associated with a signer; and (c) releasing, as the digital signature of the messages, information that enables a verifier to compute a string such that when the one-way function is applied to the string computed by the verifier, some part of the verification key is derived.
Claim 2
Independent Claim
105 words
A method for generating a digital signature of a message, comprising the steps of: (a) choosing a secret key including a set of pseudoramdom integers; (b) generating a verification key by evaluating at least once a one-way function on a string that is derived at least in part from one or more of the pseudorandom integers and security information associated with a signer; and (c) releasing, as the digital signature of the messages, information that enables a verifier to compute a string such that when the one-way function is applied to the string computed by the verifier, some part of the verification key is derived.
Claim 3
Dependent Claim
53 words
The method as described in claim 1 wherein the security information includes at least one of the following items: an identifier for the signer, an identifier for the verification key within a set of verification keys, and positional information of the pseudorandom value within a set of pseudorandom values in the secret key.
Claim 4
Independent Claim
154 words
A method for generating a digital signature of a message, comprising the steps of: (a) generating a plurality of secret keys and their corresponding verification keys, each secret key and its corresponding verification key being used or digitally signing a single message; and (b) authenticating the verification keys by means of a directed acyclic graph according to the following steps: (i) associating the verification keys to some nodes of the directed acyclic graph; (ii) publishing the values associated with some of the nodes of the directed acyclic graph such that each verification key to be authenticated has a directed path from its node to a node whose value is published, each directed edge of the directed acyclic graph corresponding to obtaining the value associated to its end-node from the value associated to its start node and security information associated with a signer by an operation that includes evaluating a one-way function at least once.
Claim 5
Independent Claim
154 words
A method for generating a digital signature of a message, comprising the steps of: (a) generating a plurality of secret keys and their corresponding verification keys, each secret key and its corresponding verification key being used or digitally signing a single message; and (b) authenticating the verification keys by means of a directed acyclic graph according to the following steps: (i) associating the verification keys to some nodes of the directed acyclic graph; (ii) publishing the values associated with some of the nodes of the directed acyclic graph such that each verification key to be authenticated has a directed path from its node to a node whose value is published, each directed edge of the directed acyclic graph corresponding to obtaining the value associated to its end-node from the value associated to its start node and security information associated with a signer by an operation that includes evaluating a one-way function at least once.
Claim 6
Dependent Claim
50 words
The method for digitally signing as described in claim 3 wherein a signer recomputes secret signing keys prior to signing a message by running an efficient algorithm on a short secret seed value such that less than log N additional signing keys need to be reconstructed before signing the message.
Claim 7
Independent Claim
48 words
A method of digitally signing a message comprising the steps of: (a) hashing the message to a second string by means of a pseudorandom one-way hash function; (b) authenticating the one-way hash function; and (c) digitally signing the second string to generate a digital signature of the message.
Claim 8
Independent Claim
48 words
A method of digitally signing a message comprising the steps of: (a) hashing the message to a second string by means of a pseudorandom one-way hash function; (b) authenticating the one-way hash function; and (c) digitally signing the second string to generate a digital signature of the message.
Claim 9
Dependent Claim
61 words
The method as described in claim 5 wherein the one-way nash function is selected by means of a fixed hash function by: (a) choosing an auxiliary value; (b) selecting the one-way hash function to be a function that hashes the message by evaluating the fixed hash function on the message together with the auxiliary value; and (c) authenticating the auxiliary value.
Claim 10
Dependent Claim
17 words
The method as described in claim 6 wherein the auxiliary value is chosen to include security information.
Claim 11
Dependent Claim
17 words
The method as described in claim 6 wherein the auxiliary value is chosed include a pseudorandom number.
Claim 12
Independent Claim
174 words
A method for providing secure digital signing using a collection of hash functions, where K s .sup.(i) denotes a secret key of an ith 1-time scheme, K p .sup.(i) denotes a public key of an ith 1-time scheme for 1<i<N, and K s =(K s .sup.(1) . . . K s .sup.(N)) denotes a secret key of an N-time scheme, wherein a 1-time scheme creates a digital signature that is used with only a single message, comprising the steps of: generating a directed acyclic graph having a plurality of nodes, each node having a value associated therewith, the value derived at least in part by evaluation a one-way function association with one or more predecessor nodes; generating a public key for an N-time digital signature scheme from one or more values of the directed acyclic graph; and generating a signature of a message, the signature comprising a 1-time signature for the message produced by an ith 1-time scheme, the public key K p .sup.(i) and a predetermined value derived from the directed acyclic graph.
Claim 13
Independent Claim
174 words
A method for providing secure digital signing using a collection of hash functions, where K s .sup.(i) denotes a secret key of an ith 1-time scheme, K p .sup.(i) denotes a public key of an ith 1-time scheme for 1<i<N, and K s =(K s .sup.(1) . . . K s .sup.(N)) denotes a secret key of an N-time scheme, wherein a 1-time scheme creates a digital signature that is used with only a single message, comprising the steps of: generating a directed acyclic graph having a plurality of nodes, each node having a value associated therewith, the value derived at least in part by evaluation a one-way function association with one or more predecessor nodes; generating a public key for an N-time digital signature scheme from one or more values of the directed acyclic graph; and generating a signature of a message, the signature comprising a 1-time signature for the message produced by an ith 1-time scheme, the public key K p .sup.(i) and a predetermined value derived from the directed acyclic graph.
Claim 14
Independent Claim
41 words
A method to enhance the security of a digital signature scheme, comprising the steps of: (a) combining a message to be signed with an auxiliary value to produce a string; (b) digitally signing the string; and (c) authenticating the auxiliary value.
Claim 15
Independent Claim
41 words
A method to enhance the security of a digital signature scheme, comprising the steps of: (a) combining a message to be signed with an auxiliary value to produce a string; (b) digitally signing the string; and (c) authenticating the auxiliary value.
Claim 16
Dependent Claim
17 words
The method as described in claim 10 wherein the auxiliary value is chosen to include security information.
Claim 17
Dependent Claim
17 words
The method as described in claim 10 wherein the auxiliary value is chosed include a pseudorandom number.
References Cited (Backward Citations)
US4771459A
Cited
US4944009A
Cited
US5016274A
Cited
US4932056A
Cited
US5136647A
Cited
US5136646A
Cited
US5231668A
Cited
US5263085A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-07-10 | 1999-01-09 | 1999-07-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-07-10 | 2003-01-09 | 2003-07-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-07-10 | 2007-01-09 | 2007-07-11 | $7700.00 | Window Closed / Lapsed |