Large provably fast and secure digital signature schemes based on secure hash functions
First Claim
Patent Images
1. 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.
0 Assignments
0 Petitions
Accused Products
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.
164 Citations
12 Claims
-
1. 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. - View Dependent Claims (2)
-
-
3. 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. - View Dependent Claims (4)
-
-
5. 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. - View Dependent Claims (6, 7, 8)
-
-
9. A method for providing secure digital signing using a collection of hash functions, where Ks.sup.(i) denotes a secret key of an ith 1-time scheme, Kp.sup.(i) denotes a public key of an ith 1-time scheme for 1<
- i<
N, and Ks =(Ks.sup.(1) . . . Ks.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 Kp.sup.(i) and a predetermined value derived from the directed acyclic graph.
- i<
-
10. 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. - View Dependent Claims (11, 12)
-
Specification