Method of providing digital signatures

• US 4,309,569 A
• Filed: 09/05/1979
• Issued: 01/05/1982
• Est. Priority Date: 09/05/1979
• Status: Expired due to Term

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Merkle, Ralph C.
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US06/072,363
• Time in Patent Office: 853 Days
• Field of Search: 178/22, 340/149 R, 340/149 A, 340/152 R, 235/379, 235/380, 235/382, 375/2
• US Class Current: 713/177
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

The invention comprises a method of providing a digital signature for purposes of authentication of a message, which utilizes an authentication tree function of a one-way function of a secret number.

Claims

1. In a method of providing a digital signature of the type which generates a secret number X_i, computes Y_i =F(X_i) where F( ) is a one way function, authenticates Y_i and F( ) at the receiver and transmits X_i to the receiver as the digital signature, the improvement characterized by:

the step of

selecting an authentication tree with an authentication tree function comprising a one way function of the Y_i ;

authenticating at the receiver the root of the authentication tree and the authentication tree function;

transmitting from the transmitter to the receiver the Y_i and the corresponding authentication path values of the authentication tree; and

authenticating the Y_i at the receiver by computing the authentication path of the authentication tree between the Y_i and the root of the authentication tree.

2. In a method of providing a digital signature as in claim 1 wherein the step of:

defining an authentication tree is performed by defining a function H(i,j,Y) such that

space="preserve" listing-type="equation">H(i,i,Y)=F(Y.sub.i)

and

space="preserve" listing-type="equation">H(i,j,Y)=F(H(i,(i+j-1)/2,Y), H((i+j+1)/2,j,Y))

where F( ) is a one way function, i and j are integers less than or equal to n, Y_i =F(X_i) and Y is a vector of data items Y=Y₁,Y₂, . . . Y_n ;

authenticating at the receiver is performed by authenticating H(1,n,Y) and the function H(i,j,Y) as the transmitter'"'"'s root and authentication tree function respectively; and

authenticating the Y_i at the receiver is performed by computing the authentication path of the authentication tree between the Y_i and H(1,n,Y).

3. A method of authenticating an item in a list of items comprising the steps of:

defining an authentication tree with an authentication tree function comprising a one way function of the items in the list;

authenticating the root of the authentication tree and the authentication tree function; and

authenticating the item in the list of items by computing the authentication path of the authentication tree between said item and the root of the authentication tree.

4. A method of authenticating an item as in claim 3 wherein the step of:

defining an authentication tree is performed by defining an authentication tree function comprising a one way function of the roots, R, of u users of a digital signature system; and

authenticating the item is performed by authenticating the R_j of the J^th user by computing the authentication path of the authentication tree between R_j and the root of the authentication tree.