Digital signature system and method based on a conventional encryption function

• US 4,881,264 A
• Filed: 07/30/1987
• Issued: 11/14/1989
• Est. Priority Date: 07/30/1987
• Status: Expired due to Fees

• Current Assignee: Ralph C. Merkle
• Original Assignee: Ralph C. Merkle
• Inventors: Merkle, Ralph C.
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): Gregory, Bernarr E.
• Application Number:
  US07/079,675
• Time in Patent Office: 838 Days
• Field of Search: 380/23-25, 380/28, 380/49, 380/50, 380/59
• US Class Current: 713/177
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

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.

Claims

1. 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.

2. The method of claim 1, wherein said root node authentication value is generated by applying a predefined one time signature to said root node.

3. The method of claim 1, wherein said tree is infinitely expandable.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.