US4309569A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of providing digital signatures
Assignee: Leland Stanford Junior University
•
Filing: 1979-09-05
•
Granted: 1982-01-05
•
Expires: 1999-09-05
Abstract
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.
Inventors
- 👤 Ralph C. Merkle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 13:34
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/3236; H04L9/3247; H04L2209/00; H04L2209/30; H04L9/50
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
142 words
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.
Claim 2
Dependent Claim
142 words
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.
Claim 3
Dependent Claim
123 words
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 H(i,i,Y)=F(Y.sub.i) and 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 1 ,Y 2 , . . . 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).
Claim 4
Independent Claim
75 words
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.
Claim 5
Independent Claim
75 words
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.
Claim 6
Dependent Claim
78 words
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.
References Cited (Backward Citations)
US4200770A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1985-01-04 | 1985-07-06 | 1986-01-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1989-01-04 | 1989-07-06 | 1990-01-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1993-01-04 | 1993-07-06 | 1994-01-05 | $7700.00 | Window Closed / Lapsed |