 |
Description  |
|
|
TECHNICAL FIELD
The present invention relates to secure communications and more particularly to new digital signature schemes that are provably secure against any adaptive chosen-message attack.
BACKGROUND OF THE INVENTION
In recent years, there has been a dramatic increase in the need for systems that can protect digital data from potential eavesdroppers, forgers, and other adversaries. This is largely due to the fact that an unprecedented portion of all
commercial transactions and communications are now handled with digital electronics. In addition, the sophistication of potential adversaries has increased, which has made the problem of protecting digital data even more pressing.
In response to this need, a wide variety of interesting and novel schemes have been developed for protecting and authenticating digital data. The problem now faced by many corporations and government bodies is to choose a scheme from among the
many that will be both secure and economical. NIST, in particular, is faced with the task of selecting "standard" methods for encrypting and authenticating data.
Traditionally, written data has been authenticated by appending the handwritten signature of the appropriate individual to the data. Modern methods for authenticating digital data proceed in a similar fashion except that the handwritten
signature is replaced with a digital signature. The digital signature consists of a stream of bits which is computed by the signer based on the message being signed. The digital signature should have the properties that anyone can verify that a
signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature.
The most popular method for computing digital signatures today is the RSA scheme. In the RSA scheme, each individual is provided with a secret pair of large (e.g., 500-digit) prime numbers P.sub.1 and P.sub.2. The pair (P.sub.1,P.sub.2) is
referred to as the secret key for the individual. The corresponding public key for the individual is the pair (Q,r) where Q=P.sub.1 P.sub.2 and r is a fixed positive integer that is relatively prime to P.sub.1 -1 and P.sub.2 -1. The signature for a
message M is a number x for which x.sup.r =h(M)mod Q. The function h is a publicly-available hash function that maps any data string M into a k-bit number where k.ltoreq.log Q. The step of computing h(M) is known as pre-hashing. This initial step is
common to all known digital signature algorithms because applying the signing procedure directly to M, rather than h(M), is either impossible or impossibly time-consuming. The hash function h used for pre-hashing needs to have two important properties:
it must be easy to compute h(M) given M but impossibly hard to compute M given h(M), and it should be impossibly hard to find two strings M and M' such that h(M)=h(M').
Many similar schemes have also been proposed, including the well-known DSA algorithm. The practicality of schemes such as RSA and DSA is based on several factors: it is not overly difficult for an individual's computer to produce a signature x
for a message M given that the computer knows the secret key (P.sub.1, P.sub.2), the fact that it is relatively easy for someone else's computer to verify that x is a signature for M given knowledge of the public key (r,M), the fact that the signature
itself is relatively short (e.g., it consists of about 1000 bits), and the fact that the public key is also relatively short (e.g., it also consists of about 1000 bits).
The security of schemes such as RSA and DSA is based on the hope that it is impossible for an adversary to produce a signature for any message M without knowledge of the private key, even if the adversary is aware of the public key and can obtain
valid signatures for messages other than M. More specifically, the security of these prior art schemes is based on the hope that number-theoretic problems such as factoring and computing discrete logarithms are impossibly hard for almost all large
numbers, the hope that it is impossibly hard to find a collision for the hash function (i.e., to find a pair of messages M and M' such that h(M)=h(M')) and that it is impossibly hard to invert the hash function (i.e., to compute an M such that h(M)=z
given z), and the hope that an adversary must perform one of the preceding (presumably difficult) tasks in order to be able to forge a signature.
For example, if the adversary is able to factor, then he can compute the private key from the public key, whereupon he can begin to forge signatures at will for the RSA scheme. If the adversary can compute discrete logarithms, then he can
compute forged signatures for the DSA scheme directly, without knowledge of the secret key. Moreover, if the adversary can find two messages M and M' for which h(M)=h(M'), then he can forge a signature for M' by obtaining a legitimate signature for M
(since the signatures for M and M' are the same). If the adversary can invert h, then he can forge signatures by an alternative method using a slightly more complex attack. Finally, it might be possible for an adversary to forge signatures using an
altogether different as-yet-unknown attack. Hence, in addition to the hope that it is not possible to achieve a known attack, the security of schemes such as RSA depend on the hope that there are no easier alternative attacks. In summary, this means
that the security of signature schemes such as RSA and DSA is based on assumptions which may not always be defensible.
It is also known in the prior art how to convert a hash function into a 1-time signature scheme, i.e., a signature that is used with one particular message and then discarded. If the hash function is ideal (or at least secure against inversion),
then the signature scheme will be secure against forgery. In one known technique, the Basic Lamport Scheme, there are two important parameters: k and m. The value of m denotes the length of the message to be signed and it must be specified in advance.
The parameter k is the security parameter and h is a hash function with k-bit outputs. The secret signing key Ks consists of 2 m randomly-generated strings A.sub.1, . . . ,A.sub.m, B.sub.1, . . . ,B.sub.m, each with k bits. The corresponding public
verification key Kp consists of X.sub.1, . . . ,X.sub.m, Y.sub.1, . . . ,Y.sub.m, where X.sub.i =h(A.sub.i) and Y.sub.i =h(B.sub.i) for 1.ltoreq.i.ltoreq.m. The signature of an m-bit message M=b.sub.1 . . . b.sub.m consists of S.sub.1, S.sub.2, . .
. ,S.sub.m where S.sub.i =A.sub.i (if b.sub.i =0) and B.sub.i (if b.sub.i =1). The signature is verified by checking that h(S.sub.i)=X.sub.i (if b.sub.i =0) and Y.sub.i (if b.sub.i =1).
The Basic Lamport Scheme has been improved in various ways. One improvement, the Lamport/2 Scheme, essentially halves all the costs of the basic scheme. In the Lamport/2 scheme, the signer chooses the secret key by selecting at random m+n+2
k-bit strings A.sub.1, . . . ,A.sub.m, B.sub.1, . . . ,B.sub.n, C.sub.0, C.sub.1, where n=[log ([m/2]+1)]. The signer then sets the corresponding public key to consist of the values X.sub.i =h(A.sub.i) for 1.ltoreq.i.ltoreq.m, Y.sub.j =h(B.sub.j) for
1.ltoreq.i.ltoreq.n, and Z.sub.d =h(C.sub.d) for d=0,1. The signature of an m-bit message M=b.sub.l . . . b.sub.m is computed as follows. If more than m/2 of the m bits of M are zeros, then the signer complements all of the bits of M and sets d=1.
Otherwise, the b.sub.i are left unchanged and d is set to 0. The signer next computes the number e of zeros among the b.sub.i 's. Since by definition, 0.ltoreq.e.ltoreq.m/2, the binary representation of e is e.sub.l . . . e.sub.n. If .epsilon.
denotes the empty string, the signature of M then consists of S.sub.1, . . . ,S.sub.m, T.sub.1, . . . ,T.sub.n, U where S.sub.i =A.sub.i (if b.sub.i =0) and .epsilon. otherwise for 1.ltoreq.i.ltoreq.m, and T.sub.j =B.sub.j (if .epsilon..sub.j =0) and
.epsilon. otherwise for 1.ltoreq.j.ltoreq.n, and U=C.sub.d. The signature of M is verified by first computing d from U and the two Z-values in the public key, and then checking that each of the appropriate preimages of h has been correctly supplied in
the signature.
The main drawback of the 1-time schemes described above is that they can only be used to sign a single message. To overcome this disadvantage, it is also known in the prior art how to convert a 1-time scheme into an N-time scheme, where N is an
arbitrarily large parameter that is selected in advance. In one trivial technique, any of the 1-time schemes described above can be converted into an N-time scheme by simply forming a set of N secret and public keys and using each set once. The public
(and secret) key for the N-time scheme will then be the union (or concatenation) of the individual 1-time keys.
Unfortunately, there are two serious problems with this approach. First, the public and secret key are enormous. For example, even if N=1000, the public key will consist of millions of bits, which is clearly not practical for most applications. Second, the scheme is vulnerable to attack since the adversary only has to find the preimage of one of the strings in one of the 1-time keys in order to forge a signature. As the number of targets increases, the security of the overall N-time scheme
decreases substantially.
One technique for overcoming the difficulties with key length in the trivial N-time scheme is the so-called Basic Merkle Scheme. In this scheme, the signer starts by setting up N 1-time schemes using a common hash function h. Let K.sub.s.sup.(i)
denote the secret key of the ith 1-time scheme and let K.sub.p.sup.(i) denote the public key of the ith 1-time scheme for 1.ltoreq.i.ltoreq.N. Then the secret key of the N-time scheme will be K.sub.s =K.sub.s.sup.(1), . . . ,K.sub.s.sup.(N). The
public key of the N-time scheme is obtained using a tree-based hashing procedure. In particular, let tn denote the complete binary tree with N leaves, and label the nodes of .tau.n so that v.sub..phi. is the root (where .phi. denotes the empty
string), v.sub.0 and v.sub.1 are the left and right children of v.sub..phi., respectively, and so that v.sub..alpha.0 and v.sub..alpha.1 are the left and right children of v.sub..alpha., respectively, for all .alpha. belonging to [0,1].sup.i where
i<log N. Each node in the tree has a special memory location that contains a k-bit hash value. The value stored in node v.sub..alpha. is R.sub..alpha. for all .alpha. (0.ltoreq.(.alpha.).ltoreq.log N). The value stored in the jth leaf v.sub.bin
(.sub.j) is R.sub.bin (.sub.j)=h(K.sub.p (.sup.j)) for 0.ltoreq.j<N, where bin(j) denotes the log N-bit binary representation of j and h is a hash function with k-bit outputs. The values stored in the interior nodes of the tree are computed in a
bottom-up fashion as follows. The value stored in node v.sub..alpha. is R.sub..alpha. =h(R.sub..alpha.0 R.sub..alpha.) for all .alpha. (0.ltoreq.(.alpha.).ltoreq.log N). The k-bit value R.sub..phi. that is computed and stored at the root serves as
the public key Kp for the N-time scheme.
In the Basic Merkle Scheme the signature for a message M is formed as follows. Let i denote the number of signatures performed previously by the owner of the tree .tau..sub.N (for 0.ltoreq.i<N) and let b.sub.1 b.sub.2 . . . blogN denote the
log N-bit binary representation of i. In addition, define .alpha..sub.j =b.sub.1 b.sub.2 . . . b.sub.j-1 b.sub.j for 1.ltoreq.j.ltoreq.log N. Then the signature for M consists of the signature for M produced by the ith 1-time scheme (counting starting
with i=0) along with i, the public key K.sub.p (.sup.i) of the ith 1-time scheme, and R.sub..alpha.j 1.ltoreq.j.ltoreq.log N. Given i, K.sub.p (.sup.i), and R.sub..alpha.j 1.ltoreq.j.ltoreq.log N, it is easy for the verifier to check that the signature
is authentic. First, the verifier checks that the portion of the signature for the ith one-time scheme is valid assuming that the declared value of K.sub.p (.sup.i ) is indeed the public key for the ith one-time scheme. Next, the verifier checks that
K.sub.p (.sup.i) is authentic by computing Ralpha for all alpha that are prefixes of bin(i). These are the values contained in nodes that are on the path from leaf i to the root in .tau..sub.N. If the value for R.phi. computed by the verifier matches
the public key for the tree, then the signature is authentic.
Although the Basic Merkle Scheme has a short public key and short signatures, it has a very large secret key and thus it requires the signer to remember a large amount of data (N secret 1-time keys, N public 1-time keys, and the 2.sup.N-1
R-values of .tau..sub.N). The memory requirements of the Basic Merkle Scheme are likely prohibitive for many applications. One solution to the memory problem is to generate all the N 1-time keys from a single and short private key, which serves as the
seed for a random number generator, and then reconstruct the entire tree .tau..sub.N prior to signing each message. Although this approach solves the memory problem, it requires a considerable amount of time to produce each signature. Another solution,
the Small-Memory Merkle Scheme, requires the signer to remember (log.sup.2 N)/2 R-values from the tree and log N states of the pseudo-random number generator at any time. In addition, the method can generate a signature by regenerating log N secret and
public 1-time keys and by performing log N additional hash computations.
The major problem with both the Basic Merkle Scheme and the Small-Memory Merkle Scheme is security. In particular, the schemes are vulnerable to numerous square-root attacks, several of which are described in what follows. As a consequence, a
signer using one of these schemes will need to use values of k and m that are at least twice as large as the values that would be needed for any 1-time scheme in isolation. This means that key lengths, signature lengths, signing times, memory
requirements, and verifying times will all need to be increased by an order of magnitude in an attempt to make up for these insecurities.
The best known of these attacks is the attack on the pre-hashing. This is a chosen-message attack aimed at the messages to be signed. It works whenever the digital signature of a long message M is obtained by first hashing the message and then
properly signing h(M). In this attack, the enemy chooses 2.sup.m/2 messages M.sub.i and then computes the m-bit values h(M.sub.i) which will be actually signed. By the birthday paradox, with constant probability he finds i and j such that
h(M.sub.i)=h(M.sub.j). Then, by requesting and obtaining the signature of M.sub.i from the signer, the enemy forges the signature of M.sub.j. Hence Merkle's algorithm and all previously known signing algorithms are at most 2.sup.m/2 secure (as defined
herein, this measure of security means that a signature can be forged with reasonable probability by an algorithm running in 2.sup.m/2 steps), even if h is an ideal hash function.
It should be appreciated that in such a forgery the enemy may essentially choose the message whose signature is forged. For example, the forger may compute a set 2.sup.m/2 h-hashed "innocent" messages (i.e., requests for very small payments), a
set of 2.sup.m/2 h-hashed "advantageous" messages (i.e., requests for very large payments), and then look for a point in the intersection of these two sets. Then, by obtaining a signature for a single small check, the forger will be able to forge the
signature of a large check. This weakness forces all prior digital signature schems to use a large value of m.
Another form of attack of the Merkle Scheme is the tree attack which works regardless of the 1-time signature scheme employed at the leaves and regardless of what pseudo-random number generator is used to generate 1-time secret keys. The first
attack is a collision-based attack aimed at the leaves of the tree. Leaf i stores the k-bit value R.sub.bin(i) =h(K.sub.p.sup.(i)), which is authenticated via the sequence of R-values comprising the ith authenticating path. In this attack, the enemy
tries to compute a 1-time public key K.sub.p for which he knows the corresponding secret key and for which h(K.sub.p)=h(K.sub.p.sup.(i)) for some small i. Then, he can use one of the authenticating paths (namely the ith path) that has already been
released by the legitimate signer to forge an authentication of K.sub.p. If the signer has signed 2.sup.k/2 messages, then 2.sup.k/2 leaf values have become available to the enemy. The enemy then generates 2.sup.k/2 1-time public keys, K.sub.p.sup.(1)
', . . . ,K.sub.p.sup.(2k/2) ' , together with their corresponding secret keys, and hashes them to k-bit values by using h. By the birthday paradox, with constant probability, he finds an a and b such that 1.ltoreq.a,b.ltoreq.2.sup.k/2 and
h(K.sub.p.sup.(a))=h(K.sub.p.sup.(b) '). In this case, the legitimate ath authenticating path also authenticates K.sub.p.sup.(b) ', and since the enemy knows K.sub.s.sup.(b) ', he can then forge the signature of any message he wants. Thus in this
attack, the enemy pretends that the forged signature is that of the ith message, since the current total number of messages legitimately signed is not generally available to the verifier.
Thus, the Merkle Scheme is at most 2.sup.k/2 -secure, even if h is an ideal hash function. Moreover, the attack can also be applied to the internal nodes of the signing tree. Once 2.sup.k/2 R-values have been revealed on any level of the tree
(or in any collection of trees), the enemy can mount a collision-based attack by generating a tree of his own choosing and hoping to match an R-value on the same level of the tree. The attack can also be extended for use with many signers. Thus even if
the Merkle scheme were made secure for a single signer, problems can arise when there are many signers. In particular, once a total of 2.sup.k/2 messages have been signed, a collision-based attack can proceed as before.
Thus, the N-time Merkle Scheme is generally described given an "abstract but secure" 1-time signature scheme. As noted above, however, no matter what the 1-time signature scheme may be, the Merkle schemes are prone to attacks. Depending on the
1-time signature scheme that is used, however, there may also be additional attacks. For example, depending on the 1-time scheme used, then it is also possible to apply a collision attack aimed at the individual hashes in the 1-time public key. In
particular, once a total of 2.sup.k/2 hash values have been revealed (and m or more are revealed for each signature), then the attacker can apply a collision-based attack to find a preimage of one of the hashes in one of the 1-time public keys in about
2.sup.k/2 steps. Once a preimage is found, then the attacker can forge a signature by using a chosen-message attack. Hence, the forger can expect to be able to produce a forgery in about 2.sup.k/2 steps.
There are also attacks on the Small-Memory Merkle Scheme aimed at the pseudo-random number generator. Even if the pseudo-random number generator is unpredictable, if it is used in a standard way, a collision-based attack can be used to invert
the generator.
To overcome some of these significant problems, Merkle has proposed an Alternative Merkle Scheme in which each node contains a 1-time scheme that is used to authenticate the 1-time schemes in its left and right children. The public key of the
scheme is the same as the public key of the 1-time scheme in the root of the tree. This scheme has the advantage that the value of N does not need to be fixed in advance, but has the greater disadvantage that the signatures become very large as N
increases, which makes the scheme impractical for even moderate values of N. The scheme also has security problems that are analogous to those described above.
As a result of the current state of the prior art, there remains a long felt need for provably fast and secure digital signature algorithms based on secure hash functions.
BRIEF SUMMARY OF THE INVENTION
It is a principal object of the present invention to describe an efficient method for converting a hash function into a digital signature scheme.
It is another object of the invention to provide a digital signature scheme in which it can be proved that in order to forge the signature of any single message an adversary must be able to "break" the underlying hash function; therefore, if the
underlying hash function is secure, then so is the digital signature algorithm.
It is a further object of the invention to describe such a signature scheme that is provably secure in view of a concrete measure of security that allows counting of the precise number of computational steps that any adversary needs to take in
order to forge the signature of even a single message.
It is still another object of the invention to provide a new technique for hashing in the context of signing that is provably immune to square-root attacks. The technique facilitates hashing of long messages into very short strings, thereby
gaining speed without compromising security.
It is yet another object of the invention to provide a scheme whose security relies on fewer assumptions that prior art schemes which are vulnerable to forgery if the underlying hash function is insecure or if fast algorithms are developed for
problems such as factoring or discrete-log. The inventive scheme relies on no more assumptions than any scheme which one-way hashes a message as the first step in producing the digital signature for the message.
It is another object of the invention to provide a signature scheme which works given any secure hash function h whose security does not depend on number theory. Thus, the inventive scheme is invulnerable to any attack based on algorithmic
advances for problems such as factoring integers or finding discrete logarithms.
It is still a further object of the invention to provide a signature algorithm that cannot be easily converted into a public-key encryption algorithm.
It is another important object of the invention to provide a new signature scheme that has significantly shorter public keys than prior art schemes, can be implemented without special-purpose hardware or software for large-integer arithmetic,
and, depending on the secure hash function that is used, requires substantially less time for signing and verifying than prior art schemes including RSA and DSA.
It is a further object of the invention to provide new techniques whereby once the risk of standardizing a hash function is accepted, no additional risk need be taken (and no additional testing need be performed) to standardize a digital
signature scheme (since the digital signature scheme described herein is provably secure if the hash function it uses is secure).
A further object of the invention is to provide a signature scheme which is secure (or can be made secure with simple modifications) even if the underlying hash function is not ideal. All that is needed is that it be difficult to find inverses
for the hash function.
It is another object of the present invention to provide a secure digital signature wherein any form of generalized directed acyclic graph (with plural authenticating paths) is used for obtaining a public key of an N-time scheme.
The foregoing has outlined some of the more pertinent objects of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial
results can be attained by applying the disclosed invention in a different manner or modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the following Detailed
Description of the preferred embodiment.
BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention and the advantages thereof, reference should be made to the following Detailed Description taken in connection with the accompanying drawings in which:
FIG. 1 is a diagram of an 8-leaf binary tree .tau..sub.8 for use in the LM Scheme of the present invention;
FIG. 2 is an analysis of the binary tree of FIG. 1 showing the computation through an authenticating path;
FIG. 3 is a representation of a tree for use by the TREEHASH algorithm according to the N.sup.1/2 algorithm of the present invention for computing R-values for .tau..sub.16 ;
FIG. 4 is a further representation of the tree of FIG. 3 wherein the number on each node denotes the step at which the R-value is computed for that node when the algorithm is repeatedly run on .tau..sub.16 ;
FIG. 5 is a further representation of the tree showing the R-values that are remembered after an initialization phase;
FIG. 6 is still a further representaiton of the tree showing the R-values for the squared nodes;
FIG. 7 shows a representation of a tree according to the N.sup.1/3 algorithm of the present invention for .tau..sub.64 ; and
FIG. 8 shows a preferred embodiment of the invention wherein a generalized directed acyclic graph (with plural authenticating paths is provided).
Similar reference characters refer to similar steps throughout the several views of the drawings.
DETAILED DESCRIPTION
The principal object of the invention is to provide a method for authenticating data with digital signatures. Like the prior art RSA and DSA techniques, the method is practical in that it is relatively easy to compute a signature given the
secret key, and it is easy to verify a signature given the public key. In addition, the public keys and signatures for the method are very short. The main advantage of the new method, however, is its security. Unlike RSA or DSA, the security of our
method does not rely on the hope that number-theoretic problems such as factoring and discrete-log are intractable. Nor does the scheme rely on the hope that such an intractable problem needs to be solved in order to forge a signature. Rather, the
security of the scheme relies solely on the security of the associated hash function h. If the hash function is random or if it is otherwise secure (as defined herein), then the digital signature algorithm based on such hash function is provably secure
against forgeries.
All known signature schemes (including the present invention) require the existence of a secure hash function in order to be secure against forgery. For example, if h is easy to invert, then it is possible to forge RSA signatures even if
factoring turns out to be hard. The difference between the inventive method and schemes such as DSA and RSA is that such schemes also require number theoretic problems such as factoring and discrete-log to be intractable in order to be secure. The
present method requires no such additional assumptions.
To facilitate an understanding of the present invention, some additional background information is now described with respect to digital signature schemes and hash functions.
Digital Signature Schemes
A digital signature scheme consists of the following entities: a random number generator R for producing random numbers for each individual, a key generation algorithm G for producing public and private keys for each individual, a signing
algorithm S for computing digital signatures, and a verification algorithm V for verifying digital signatures. Each component of the scheme must run in polynomial time, and at least the random number generator should be probabilistic. In addition, each
component depends on a security parameter k that determines the size of the random numbers, the size of the secret and public keys, and the amount of computational effort required to forge a signature.
The random number generator R assigns a secret random number R(I) to each individual. The variable I is used to denote the identity of an individual. This number is used to derive a secret key for the individual using the key generation
algorithm. The length of the random number depends on k and the signature scheme. If desired, the value of R(I) can be computed by the individual himself (i.e., each individual can select his or her own random number R(I)). The key generation
algorithm G takes as input the identity of the individual I for whom the keys are being produced, the value of R(I), and the security parameter k. The output of the algorithm consists of a public key for I (denoted by K.sub.p.sup.(I)) and a secret key
for I (denoted by K.sub.s.sup.(I)). The pair (I,K.sub.p.sup.(I)) are published so that everyone has access to everyone else's public key. The key generation algorithm is also public, but each individual can still produce their own keys in private,
since the random numbers used to produce the keys are secret.
The signing algorithm S takes as input the secret key K.sub.s.sup.(I) and identity number I of the individual who is signing, the message M that is being signed, and the index i of the message that is being signed. (The index of the message is i
if the signer has previously signed i-1 other messages.) The output of the signing algorithm is a bit-string .sigma. that forms the digital signature of the signer for the message. The verification algorithm V takes as input the message that was signed
M, the public key K.sub.p.sup.(I) and identity number I of the individual who produced the signature, and the signature .sigma.. The output of the algorithm is either valid or invalid. In particular, it must be the case that
V(I,K.sub.p.sup.(I),M,.sigma.)=Valid if S(I,K.sub.s.sup.(I),M,i)=.sigma. for any I, M, i, and .sigma.. In other words, the verification algorithm must correctly recognize any valid signature. As described herein, the algorithms for signing, verifying,
and key generation will also depend on a parameter N that denotes an upper bound on the number of signatures that will ever be computed (collectively over all individuals). They may also depend on a parameter B that denotes an upper bound on the number
of bits that will ever be signed using the system. The values of N and B can be arbitrarily large, and they are present primarily for the analysis of security.
Hash Functions
Signature schemes make use of a hash function h as part of the signing process. For example, in RSA, the first step in signing a message M is to compute h(M). In order for such schemes to be secure, it is important that h satisfy several
properties. For example, it is very important that it be computational infeasible for an adversary to find a collision for h. A collision for h is a pair of strings M and M' such that h(M)=h(M'). This is because the signature for a message M using RSA
(or any similar algorithm) only depends on h(M). If h(M)=h(M'), then the adversary can forge a signature for M' by first obtaining a valid signature for M (since both strings will have the same signature).
Any function from [0, 1]* to [0, 1].sup.m (where m is a predetermined parameter) can be a hash function. Usually a hash function is picked at random from a family of functions with some specific structure. For example, an ideal hash function
herein means a function that is selected at random from the space of all functions with domain [0,1]* and range [0,1]m. In other words, the ideal hash function is a function that assigns a random m-bit number to every string. So, reference to a single
function h refers to a randomly-chosen function from a set of functions. (Typically m will be equal to the security parameter k.)
Ideal hash functions have several useful properties. For example, it is provably hard to find a collision for ideal hash functions. In fact, as will be seen it is possible to show that any t-step algorithm that attempts to find a collision for
an ideal h can only do so with small probability. In addition, ideal hash functions are hard to invert. This can be expressed in two ways. First, given h(M) where M is an unknown random m-bit string, it is hard to find an M' (possibly equal to M) such
that h(M)=h(M'). Second, given a random m-bit string z, it is hard to find an M' such that h(M')=z (if such an M' even exists). Lastly, ideal hash functions are a good source of randomness. For example, h(00), h(01), h(10), and h(11) are all
independent random strings in [0,1]m. Hence, h can be adapted for use as a pseudo-random number generator. In fact, one can treat an ideal hash function as a random oracle, which given a string omega as a query, responds with a random m-bit number that
is defined to be the value of h(.theta.).
According to the invention, it will be seen how to use a hash function to construct a digital signature scheme. If the hash function is ideal, then the signature scheme will be 2.sup.m-1 -secure. By making m large (say 100 or 200), then the
signature scheme is immune to forgery. In addition, each public key will consist of m bits, and each signature will consist of a few thousand bits. The signing process will consist of hashing a few thousand bytes of data (in addition to M). Most of
the hashing can be performed ahead of time in an off-line fashion. The verification process also consists of hashing M along with a few thousand bytes of data. Overall, the scheme will rival or beat schemes such prior art schemes as DSA or RSA in terms
of speed and efficiency, and it will dominate them in terms of security.
A Concrete Measure of Security
With this background, a new formal definition of what it means for a digital signature scheme to be secure against forgery is now provided. Unlike most definitions of security, which are asymptotic in nature, the present invention adopts a
definition of security that specifies in a concrete fashion how much time will be needed by the strongest possible adversary to generate a forged signature. The following also defines what it means for a hash function to be secure, and the properties of
a hash function which are sufficient to guarantee the security of the signature scheme are also described.
For a digital signature scheme to be useful, it is necessary that a forger not be able to compute a valid signature. More generally, it is necessary that the forger not be able to compute any triple .sigma., I, and M for which
V(I,K.sub.p.sup.(I),M,.sigma.)=Valid.
There are many ways one could try to formalize the preceding requirement, depending on how much power is given to the potential forger and on how "useful" the string M must be for a forgery to be considered successful. In this invention, the
strongest possible definition of security is adopted. In particular, it is assumed the potential forger is allowed to conduct an adaptive chosen-message attack, and the forger is considered to be successful if he or she finds any I, M, and .sigma. for
which V(I,K.sub.p.sup.(I),M,.sigma.)=Valid. The only exclusions will be values of M and I for which a signature for M is directly obtained from I as part of the chosen-message attack. (In an adaptive chosen-message attack, the forger is allowed to
obtain a signature for any message of his choosing at each step of the attack. Moreover, the message that is chosen at each step can depend on the signatures that were obtained for messages chosen at prior steps.)
The present invention measures the security of a signature scheme in a very concrete manner by specifying a precise lower bound on the amount of time that will be required by an adversary to have a .rho. chance of producing a forgery. The
probability .rho. is based on the random number generator R as well as any randomization that is used in G, S, V, or the attempt to produce a forgery. In particular, the present invention formally defines the security of a digital signature scheme as
follows.
Definition 1.
A digital signature scheme (R,G,S,V) is said to be it T-secure if for all t>0 and for all adaptive chosen-message forging algorithms F that run in t steps (and that have fewer than t lines of code), the probability that F can produce a triple
(I,M,.sigma.) for which:
the value of S(I,K.sub.s.sup.(I),M,i) was not provided to the forger by a signer as part of the chosen-message attack (for any i), and
V (I,K.sub.p.sup.(I),M,.sigma.)=Valid,
is at most .rho..ltoreq.t/T. The probability .rho. is taken over all randomness that occurs in the use of R, G, S, V, and F during the attack.
For example, if a digital signature scheme is 2.sup.200 -secure, then the probability that a forger can produce some valid signature for some signer and some message (that has not already been signed by that signer) in less than 2.sup.100 steps
is at most 2.sup.-100.
This definition of security represents a dramatic departure from traditional definitions of asymptotic security which are based on the notions of polynomial and exponential time. In particular, the definition provided here has the advantage of
being very concrete. It allows the user of the signature scheme to specify precisely the level of security desired. For example, it can be argued that there will not be enough computational cycles available in the next 50 years (worldwide) to have more
than a 2.sup.-40 chance of being able to produce even a single forgery for a signature scheme that is 2.sup.170 -secure. For most practical purposes, it is probably sufficient that a scheme be 2.sup.100 -secure, since 1000 machines that run 1000 times
faster than today's fastest Teraflops machines would still need to run for several millenia before having any reasonable chance of producing a single forgery (even a potentially worthless forgery). Even better, the security still holds even if
mathematicians figure out how to factor numbers and compute discrete logs.
The definition of security adopted herein is much more stringent than other definitions typily found in the literature. In addition to being concrete instead of asymptotic, the definition upper bounds the probability of a successful forgery
within a certain time frame. This is much more useful than lower bounds on the expected time needed to forge since the expected time to forge might be very large even though the chances for a quick forgery are high. In addition, the definition allows
for an adaptive chosen-message attack, and the attack is considered to be successful if the adversary succeeds in forging any message (even one that is of no use). These distinctions are important since there are popular schemes in the prior art that
are hoped to be secure under less stringent definitions of security, but which are known to readily succumb to the kind of attacks permitted under the disclosed definition of security. For example, the RSA scheme is well-known to be susceptable to very
damaging chosen-text attacks if it is not used in conjunction with a secure hash function. Even when used with a secure hash function, however, there is no reason to believe that number theoretic schemes such as RSA are immune to chosen-text attacks
(even if the underlying number-theoretic problem turns out to be hard). This drawback limits the usefulness of such schemes in pract | | |
