US4309569A — Method of providing digital signatures
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
United States Patent (19) 11 4,309,569
Merkle Best Available Coe 45 Jan. 5, 1982
(54) METHOD OF PROVIDING DIGITAL 56) References Cited
SIGNATURES U.S. PATENT DOCUMENTS
75 Inventor: t C. Merkle, Mountain View, 4,200,770 4/1980 Hellman et al. ........................ 375/2
1.
73 Assignee: The Board of Trustees of the Leland Primary Examiner-Howard A. Birmiel
73) 8. Stanford Junior University, Stanford, Attorney, Agent, or Firm-Flehr, Hohbach, Test,
Calif. Albritton & Herbert
21 Appl. No.: 72,363 57 ABSTRACT
22 Filed: Sep. 5, 1979 The invention comprises a method of providing a digi
3 tal signature for purposes of authentication of a mes
: s
saw
OTS/36A:
was s a s a sea a a sa a as s a sea e s so sea e e s '340/825.34
sage, which utilizes an authentication tree function of a
one-way function of a secret number.
58 Field of Search ......... 178/22; 340/149 R, 149 A,
340/152 R; 235/379, 380, 382; 375/2 4 Claims, 1 Drawing Figure
U.S. Patent Jan. 5, 1982 4,309,569
CDCD 949),
1.
4,309,569
2
The Diffie et al method is a one time signature; each
METHOD OF PROVIDENG DIGITAL Y=y1, y2, ... y2's can only be used to sign one message.
SGNATURES If more than one message is to be signed, then new
values where Yi = yi, yi2, yi3, . . . are needed, a new Yi
The government has rights in this invention pursuant for each message. One time signatures, as embodied in
to U.S. Air Force Office of Scientific Research Con the Diffie et al method, are practical between a single
tract F49620-78-C-0086 and U.S. Army Research Office pair of users who are willing to exchange the large
Contract DAAG29-78-C-0036. amount of data necessary but they are not practical for
The invention relates to cryptographic systems and most applications without further refinements.
more particularly to a method of providing digital sig 10 Accordingly, it is an object of the invention to design
natures. a digital signature system wherein the security of the
In conventional paper oriented business transactions, system rests on the security of a conventional crypto
signatures provide a generally accepted level of authen graphic function.
tication. But as electronic communication replaces Another object of this invention is to lessen the large
paper oriented business transactions, the need for an 15 storage requirements of the Diffie et al method.
alectronic or digital signature is created. Currently, An illustrated embodiment of the present invention
most digital message authentication consists of append describes a method for providing a digital signature of
ing an authenticator pattern, known only to the trans the type which generates a secret number Xi, where
mitter and intended receiver, to each message and en Xi=Xil, Xiz, Xi8. . . Xin computes Yi=F(X) and transmits
crypting the combination. This method, however, pro 20 part of Xi to the receiver as the digital signature. The
vides no protection against the problem of disputes improvement is characterized by defining an authenti
between the transmitter and receiver regarding the true cation tree with an authentication tree function com
content of the message. prising a one way function of the Yi. The root of the
Diffie, et al., “New Directions in Cryptography', 25 authentication tree and the authentication tree function
IEEE Transactions on Information Theory, Vol. 1T-22, are authenticated at the receiver. The Yi and the corre
No. 6, November 1976, pages 644-654, suggested a sponding authentication path values of the authentica
public key cryptosystem as a means to implement a tion tree are transmitted from the transmitter to the
digital signature and authenticate the true content of the receiver. Finally, the Yi are authenticated at the re
message. But such a system suffers because the use of 30 ceiver by computing the authentication path of the
public key crytosystems to implement digital signatures authentication tree between the Yi and the rest of the
entails an unknown risk until the security of public key authentication tree.
cryptosystems has been carefully certified. FIG. is a diagram of an illustrative authentication
A signature system whose security rested on the secu tree with a binary tree structure where n is equal to 8.
rity of a conventional cryptographic system would be 35 The receiver must be able to authenticate the trans
"pre-certified” to the extent that the underlying encryp mitter's Yi values.
tion function had been certified. The delays and costs of The simplest method is for the receiver to store an
a new certification effort would be avoided. Diffie, et al, authenticated copy of all the transmitter's Yi's, as is
supra, suggested such a system, but it has severe perfor done in the Diffie et al method. As described, this
mance drawbacks. 40 method has limited application. It is practical between a
The Diffie method is a signature based on the concept pair of users who are willing to exchange a large
of a one way function. If y = F(x) is the result of apply amount of data for a one time signature. The present
ing the one way function F(.) to input x, then the key invention describes a method called "tree authentica
observation is: tion' which can be used to authenticate any Yi of the
The person who computed y=F(x) is the only person 45 transmitter and requires less storage.
who knows X. If y is publicly revealed, only the origina The present invention eliminates the large storage
tor of y can know x, and can choose to reveal or conceal requirement. For example, if the transmitter transmits
X at his whim. Yi to the receiver just before signing a message with the
In the Diffie scheme, to sign a message m whose size corresponding Xi, then the receiver will not previously
is s bits it is necessary to compute F(x1)=y1, F(x2)=y2, 50 have had to store all the transmitter's Yi's. Unfortu
... F(x)=ys. The transmitter and receiver would agree nately, such a protocol by itself would not work be
on the vector Y=y1, y2, ... ys. If the jth bit of m was a cause anyone could claim to be the transmitter and send
a false Yi. The receiver must be able to confirm that he
1, the transmitter would reveal X; if the jth bit of m was was sent an authentic Yi and not a forgery.
a 0, the transmitter would not reveal xi. In essence, each To implement a "tree authentication' method for a
bit of m would be individually signed. 55
vector of data items Y=Y1, Y2, . . . Yn a method is
The method as described thus far suffers from the
defect that the receiver can alter m by changing bits provided to authenticate a randomly chosen Yi. To
that are 1's into O's; the receiver may alter m by denying authenticate the Yi, define the function H(i,j,Y) as fol
that he ever received xi, in spite of the fact that he did. lows:
However, O's cannot be changed into 1's because the 60 H(ii, Y)=F(Y) (1)
receiver cannot create an x that he never received.
Diffie et all overcame this problem by signing a new H(ii,Y) = F(H(i,i-j- 1/2, Y), H(i-j-- 1)/2.j, Y)) (2)
message m', which is exactly twice as long as m and is
computed by concactenating m with the bitwise com where F (Y) is a one way function. H(i,j,Y) is a one way
plement of m. That is, each bit min the original message 65 function of Yi, Yi-L1 ... Yi and H(1,n,Y) can be used to
is represented by two bits, mand the complement of my authenticate Y1 through Yn. H(1,n,Y) is a one way func
in the new message m'. Clearly, one or the other bit tion of all the Yi. If H(1,n,Y) is only 100 bits, it can be
must be a 0 and is not alterable. conveniently stored. This method allows the receiver to
4,309,569
3 4.
selectively authenticate any "leaf, Yi, of the binary Yi and the authentication path for Yi. Tree authentica
"tree' defined with the function H(i,n,Y). tion and authentication using one time signatures can be
The following example is offered to illustrate a tree intermixed to produce systems with all the flexibility of
authentication where n=8. The sequence of recursive public key cryptosystems.
calls required to compute the root, H(1,8,Y) of the bi There are many methods for implementing the form
nary tree is shown in FIG. I. Once the root H(1,8,Y) is of the invention. For example, the authentication tree
computed, it is authenticated to the receiver along with need not be a binary tree but may be a trinary tree
the function H( ). To authenticate a Yi such as Y5, the where F() is a one way function having a 300 bit input
transmitter and receiver proceed in the following man and a 100 bit output. In general, the authentication tree
e 10 may have any integer K order of branching where F()
(1) H(1,8,Y) is already known and authenticated. is a one way function having a K:1 ratio of input to
(2) H(1,8,Y)=F(H(1,4,Y), H(5,8,Y)). Send H(1,4,Y) output bits. Clearly, the choice of a 200 bit input and a
and H(5,8Y) and let the receiver compute 100 bit output for the one way function, F(), of a binary
H(1,8,Y) = F(H(1,4,Y), H(5,8Y)) and confirm H (5,8,Y) tree is not essential; however, to preserve a constant
is correct. 15 word size it is desirable that there be a 2:1 ratio of input
(3) The receiver has authenticated H(5,8,Y). Send to output bits in the one way function of a binary tree.
H(5,6,Y) and H(7,8,Y) and let the receiver compute If a constant word size is not required, then the ratio of
H(5,8,Y) = F(H(5,6,Y), H(7,8,Y) and confirm H (5,6,Y) input to output bits in the one way function need not be
is correct. of the same order as the branching.
(4) The receiver has authenticated H(5,6,Y). Send The present invention has been described with re
H(5,5,Y) and H(6,6,Y) and let the receiver compute spect to authentication of signatures. However, its use is
H(5,6,Y)=F(H(5,5,Y), H(6,6,Y)) and confirm H(5,5,Y) not limited to signatures. It may be used to authenticate
is correct. a piece of information in a list of information, or one
(5) The receiver has authenticated H(5,5,Y). Send Ys item in a list of items.
and let the receiver compute H(5,5,Y) = F(Y5) and con 25 Thus, although the best mode contemplated for car
firm it is correct. rying out the present invention has been herein shown
(6) The receiver has authenticated Y5. and described, it will be apparent that modification and
Using this method, only log2 n transmissions are re variation may be made without departing from what is
quired, each of about 200 bits. Close examination of the regarded to be the invention.
method will reveal that half the transmissions are redun What is claimed is:
dant. For example, H(5,6,Y) can be computed from i. In a method of providing a digital signature of the
H(5,5,Y) and H(6,6,Y), so there is really no need to send type which generates a secret number Xi, computes
H(5,6,Y). Similarly, H(5,8,Y) need never be transmitted,
either. (The receiver must compute these quantities Yi = F(X) where F() is a one way function, authenti
cates Yi and F() at the receiver and transmits Xi to the
anyway for proper authentication.) Therefore, to au 35 receiver as the digital signature, the improvement char
thenticate Y5 it is only required that H(1,8,Y) was previ acterized by: the step of
ously authenticated, and Ys, H(6,6, Y), H(7,8,Y) and selecting an authentication tree with an authentica
H(1,4,Y) were transmitted to the receiver. That is, 100* tion tree function comprising a one way function of
log2 n bits of information are required to authenticate an the Yi;
arbitrary Yi. 40
authenticating at the receiver the root of the authenti
The method is called tree authentication because the
computation of the root, H(1,n,Y), forms a binary tree cation tree and the authentication tree function;
of recursive calls. Authenticating a particular leaf Yi in transmitting from the transmitter to the receiver the
the tree requires only those values of HO starting from Yi and the corresponding authentication path val
the leaf and progressing to the root, that is, from H(i- 45 ues of the authentication tree; and
authenticating the Yi at the receiver by computing the
,i,Y) to H(1,n,Y). H(1,n,Y) is referred to as the root of authentication path of the authentication tree be
the authentication tree, or R. The information near the tween the Yi and the root of the authentication tree.
path from R to H(i,i,Y) required to authenticate Yi is 2. In a method of providing a digital signature as in
called the authentication path for Yi. claim 1 wherein the step of:
The use of tree authentication is now fairly clear. The 50
defining an authentication tree is performed by defin
transmitter transmits Yi to the receiver. The transmitter ing a function H(i,j,Y) such that
then transmits the authentication path for Yi. The re
ceiver knows R, the root of the authentication tree, and
so can then authenticate Yi, and can accept as genuine a
message from the transmitter signed with the corre 55
sponding Xi.
As a further modification of the basic tree authentica.
tion method, if the jth user has a distinct authentication
tree with root R, then tree authentication can be used to where F() is a one way function, i and j are inte
authenticate Ri. It is not necessary for each user to 60 gers less than or equal to n, Y= F(X) and Y is a
remember all the R in order to authenticate them. A vector of data items Y =Y1, Y2, . . . Y.
central clearinghouse could accept the Ri from all u authenticating at the receiver is performed by authen
users, and compute H(1,u,R). This single 100 bit quan ticating H(1,n,Y) and the function H(i,j,Y) as the
tity could then be distributed and would serve to au transmitter's root and authentication tree function
thenticate all the Ri, which would in turn be used to 65 respectively; and
authenticate the Yi. In practice, the transmitter, A, authenticating the Yi at the receiver is performed by
would remember his root RA and the authentication computing the authentication path of the authenti
path for RA and send them to the receiver, B, along with cation tree between the Yi and H(1,n,Y).
4,309,569
5 6
3. A method of authenticating an item in a list of items 4. A method of authenticating an item as in claim 3
comprising the steps of: wherein the step of:
defining an authentication tree with an authentication defining an authentication tree is performed by defin
tree function comprising a one way function of the ing an authentication tree function comprising a
items in the list; 5 one way function of the roots, R, of u users of a
authenticating the root of the authentication tree and digital signature system; and
the authentication tree function; and authenticating the item is performed by authenticat
authenticating the item in the list of items by comput- ing the Rof the Jih user by computing the authenti
ing the authentication path of the authentication cation path of the authentication tree between Ri
tree between said item and the root of the authenti- 10 and the root of the authentication tree.
cation tree. is g g : :
15
2O
25
30
35
40
45
50
55
60
65