US4881264A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital signature system and method based on a conventional encryption function
Assignee: Individual
•
Filing: 1987-07-30
•
Granted: 1989-11-14
•
Expires: 2007-07-30
Abstract
Abstract A method of generating digital signatures for signing an infinitely expandable series of messages M i . An infinitely expandable tree of signature nodes is used, where each node can be used to sign a message. Each node is also used to sign up to k subnodes, where k is an integer greater than one. Each signature used, both for signing messages and for signing subnodes, is a one time signature, which in the preferred embodiment is based on a one-way function F. The function F is made public. To sign a message M i the signer selects a previously unused node (i.e., node i) from the signature tree. The message signing key at this node is then used to sign this message. The sequence of nodes from the root of the tree (i.e. node l) to node i is then used to verify that the message signature is correct and has not been tampered with. Furthermore, this process proves that the message has not been tampered with. Advantages of the invention include the infinite expandability of the signature tree, dependable verification of messages based on the use of secure one time signatures (e.g., which may be based on one way functions), the small amount of computation required to set up a signature tree, the small amount of storage required to maintain a tree, and the ability to implement the invention using high speed conventional encryption equipment and methods.
Inventors
- 👤 Ralph C. Merkle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 08:19
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/3236; H04L9/321; H04L9/3247
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
196 words
A method of generating digital signatures for signing a series of messages M i , the steps of the method comprising: defining a tree of signature nodes having a root node and a multiplicity of additional nodes {node i }, wherein at least a multiplicity of said nodes include message signing means for signing a message using a predefined one time signature, and subnode signing means for signing a plurality of subnodes using a predefined one time signature, wherein said subnodes are nodes on said tree which branch from said node; storing a root node authentication value for authenticating said root node in a nonsecret location; signing a message M i by (a) generating a message signature for message M i using said message signing means of node i; (b) relating said message signature to said root node authentication value by using said subnode signing means for signing each node in said tree which forms a chain of subnodes between said root node and node i; whereby the receiver of message M i can authenticate message M i by using said predefined one time signatures to relate said message signature to said root node authentication value.
Claim 2
Independent Claim
196 words
A method of generating digital signatures for signing a series of messages M i , the steps of the method comprising: defining a tree of signature nodes having a root node and a multiplicity of additional nodes {node i }, wherein at least a multiplicity of said nodes include message signing means for signing a message using a predefined one time signature, and subnode signing means for signing a plurality of subnodes using a predefined one time signature, wherein said subnodes are nodes on said tree which branch from said node; storing a root node authentication value for authenticating said root node in a nonsecret location; signing a message M i by (a) generating a message signature for message M i using said message signing means of node i; (b) relating said message signature to said root node authentication value by using said subnode signing means for signing each node in said tree which forms a chain of subnodes between said root node and node i; whereby the receiver of message M i can authenticate message M i by using said predefined one time signatures to relate said message signature to said root node authentication value.
Claim 3
Dependent Claim
24 words
The method of claim 1, wherein said root node authentication value is generated by applying a predefined one time signature to said root node.
Claim 4
Dependent Claim
11 words
The method of claim 1, wherein said tree is infinitely expandable.
Claim 5
Dependent Claim
35 words
The method of claim 3, further including the step of defining a new node i on said tree, using a randomly selected number to generate a set of one time signatures for said new node.
Claim 6
Dependent Claim
38 words
The method of claim 4, wherein said new node defining step includes the steps of defining a set of pseudorandom numbers derived from said randomly selected number, and using said pseudorandom numbers to generate corresponding one time signatures.
Claim 7
Dependent Claim
38 words
The method of claim 4, wherein said pseudorandom numbers are generated by encryping a predefined set of values using a predefined cryptographic function S with said randomly selected number as the key for said predefined cryptographic function S.
Claim 8
Dependent Claim
109 words
The method of claim 1, wherein said tree is infinitely expandable so that each node can be the parent node for a plurality of subnodes, and each subnode has one parent node; and said step of signing each node in said chain is performed by denoting as the current node the node used to sign said message M i , and then repeatedly performing the steps of: signing the current node with said subnode signing means of the parent node of said current node; and denoting said parent node as the current node; and stopping the performance of said repeated steps when the current node is said root node.
Claim 9
Independent Claim
312 words
A method of generating digital signatures for signing a series of messages M i , the steps of the method comprising: defining a one way hash function F; defining a tree of signature nodes having a root node and a multiplicity of additional nodes {node i }, wherein said tree is infinitely expandable so that each node can be the parent node for a plurality of subnodes, and each subnode has one parent node; wherein said root node and at least a multiplicity of said additional nodes include: message signing means for signing a message using a predefined one time signature, and subnode signing means for signing a plurality of subnodes using a predefined one time signature; generating a root node authentication value for authenticating said root node by applying said function F to said message signing means and said subnode signing means for said root node, and storing said root node authentication value in a nonsecret location; generating a signature for message M i by (a) generating a message signature for message M i using said message signing means of node i; (b) relating said message signature to said root node authentication value by using said subnode signing means for signing each node in said tree which forms a chain of subnodes between said root node and node i; wherein said step of signing each node in said chain is performed by the steps of: generating a HASH value for said node by applying said function F to said message signing means and said subnode signing means for said node; and using said subnode signing means of the parent node of said node to generate a signature for said HASH value; whereby the receiver of message M i can authenticate message M i by using said predefined one time signatures to relate said message signature to said root node authentication value.
Claim 10
Independent Claim
312 words
A method of generating digital signatures for signing a series of messages M i , the steps of the method comprising: defining a one way hash function F; defining a tree of signature nodes having a root node and a multiplicity of additional nodes {node i }, wherein said tree is infinitely expandable so that each node can be the parent node for a plurality of subnodes, and each subnode has one parent node; wherein said root node and at least a multiplicity of said additional nodes include: message signing means for signing a message using a predefined one time signature, and subnode signing means for signing a plurality of subnodes using a predefined one time signature; generating a root node authentication value for authenticating said root node by applying said function F to said message signing means and said subnode signing means for said root node, and storing said root node authentication value in a nonsecret location; generating a signature for message M i by (a) generating a message signature for message M i using said message signing means of node i; (b) relating said message signature to said root node authentication value by using said subnode signing means for signing each node in said tree which forms a chain of subnodes between said root node and node i; wherein said step of signing each node in said chain is performed by the steps of: generating a HASH value for said node by applying said function F to said message signing means and said subnode signing means for said node; and using said subnode signing means of the parent node of said node to generate a signature for said HASH value; whereby the receiver of message M i can authenticate message M i by using said predefined one time signatures to relate said message signature to said root node authentication value.
Claim 11
Dependent Claim
124 words
The method of claim 8, wherein said message signing means for each said multiplicity of nodes includes message signature authentication means for verifying the signature of a message; said subnode signing means for each said multiplicity of nodes includes subnode signature authentication means for verifying the signature of a node; said method further including the step authenticating said signature for message M i by the steps of: (a) applying said message signature authentication means for node i to said message signature for message M i ; (b) relating said message signature to said root node authentication value by using said subnode signature authentication means for authenticating each node in said tree which forms a chain of subnodes between said root node and node i.
References Cited (Backward Citations)
US4200770A
Cited
US4218582A
Cited
US4309569A
Cited
US4661658A
Cited
US4649233A
Cited
US4771459A
Cited
US4771461A
Cited
US4748668A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-11-13 | 1993-05-15 | 1993-11-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-11-13 | 1997-05-15 | 1997-11-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-11-13 | 2001-05-15 | 2001-11-14 | $7700.00 | Window Closed / Lapsed |