Managing nodes of a cryptographic hash tree in a hash-based digital signature scheme

• US 10,581,616 B1
• Filed: 07/11/2019
• Issued: 03/03/2020
• Est. Priority Date: 07/11/2019
• Status: Active Grant

• Current Assignee: ISARA Corporation
• Original Assignee: ISARA Corporation
• Inventors: Paruzel, Marek
• Primary Examiner(s): Getachew, Abiy
• Application Number:
  US16/508,809
• Time in Patent Office: 236 Days
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

In some aspects, nodes of a cryptographic hash tree are stored in a buffer memory. Nodes of an active subtree are stored in a first set of indexed locations in the buffer memory, and nodes of a future subtree are stored in a second set of indexed locations in the buffer memory. A one-time signature (OTS) is generated based on a signing key associated with a current value of a signing index. An authentication path for the OTS is generated by retrieving a subset of the nodes from the buffer memory. A new node of the future subtree is calculated based on the current value of the signing index and stored in the buffer memory. The signing index is then advanced from the current value to a next value of the signing index.

Claims

1. A method comprising:

storing nodes of a cryptographic hash tree in a buffer memory, wherein storing the nodes in the buffer memory comprises;

storing a first subset of nodes of an active subtree in a first set of indexed locations in the buffer memory; and

storing a second subset of nodes of a future subtree in a second set of indexed locations in the buffer memory, wherein the active subtree and the future subtree are non-overlapping subtrees of the same size;

generating a one-time signature (OTS) based on a signing key associated with a current value of a signing index, wherein the current value of the signing index is associated with a current leaf node of the active subtree;

generating an authentication path for the OTS based on the current value of the signing index, wherein generating the authentication path comprises retrieving one or more of the first subset of nodes from the buffer memory;

providing a digital signature for transmission to a message recipient, the digital signature comprising the OTS and the authentication path;

calculating a new node of the future subtree based on the current value of the signing index;

storing the new node of the future subtree in the buffer memory; and

advancing the signing index from the current value to a next value of the signing index.

2. The method of claim 1, comprising:

identifying a right node stored in a first memory location of the first set of indexed locations;

replacing the right node with its left sibling node in the first memory location.

3. The method of claim 1, wherein the active subtree and the future subtree are subtrees of height K, and the total number of nodes in the first and second subsets of nodes is equal to 2^K+(K−

2).

4. The method of claim 1, wherein:

the buffer memory comprises a bottom nodes cache;

the active subtree and the future subtree each include nodes below a cut-off level of the cryptographic hash tree; and

generating the authentication path comprises retrieving, from a top nodes cache, one or more nodes above the cut-off level of the cryptographic hash tree.

5. The method of claim 4, comprising storing OTS states associated with the active subtree in an OTS cache, wherein generating the OTS signature comprises using one or more of the OTS states associated with the current value of the signing index.

6. The method of claim 4, comprising:

identifying a right node stored in a first memory location of the top nodes cache;

replacing the right node with its left sibling node in the first memory location.

7. The method of claim 1, wherein the buffer memory comprises a circular buffer memory, the first set of indexed locations are contiguous and the second set of indexed locations are contiguous.

8. The method of claim 7, wherein storing the new node of the future subtree in the buffer memory depletes the nodes of the active subtree from the buffer memory, and the next value of the signing index is associated with a leaf node in the future subtree.

9. The method of claim 1, wherein storing the new node of the future subtree in the buffer memory comprises storing the new node in a first memory location associated with a first index value, and the method comprises identifying the first index value based on the current value of the signing index.

10. The method of claim 1, wherein calculating a new node of the future subtree based on the current value of the signing index comprises:

identifying an index of a leaf node of the future subtree based on the current value of the signing index; and

calculating the new node of the future subtree based on the index of the leaf node.

11. The method of claim 1, wherein the method is executed according to a hash-based signature scheme that calculates new leaf nodes of the future subtree in reverse order as the value of the signing index advances through a sequence of values.

12. The method of claim 11, wherein, according to the hash-based signature scheme, each new node of the future subtree is calculated based on a respective current value of the signing index, and calculating each new node of the future subtree requires calculating only one leaf node of the cryptographic hash tree.

13. A computer system, comprising:

a buffer memory;

one or more processors; and

memory storing instructions that are operable when executed by the one or more processors to perform operations comprising;

storing nodes of a cryptographic hash tree in the buffer memory, wherein storing the nodes in the buffer memory comprises;

storing a first subset of nodes of an active subtree in a first set of indexed locations in the buffer memory; and

storing a second subset of nodes of a future subtree in a second set of indexed locations in the buffer memory, wherein the active subtree and the future subtree are non-overlapping subtrees of the same size;

generating a one-time signature (OTS) based on a signing key associated with a current value of a signing index, wherein the current value of the signing index is associated with a current leaf node of the active subtree;

generating an authentication path for the OTS based on the current value of the signing index, wherein generating the authentication path comprises retrieving one or more of the first subset of nodes from the buffer memory;

providing a digital signature for transmission to a message recipient, the digital signature comprising the OTS and the authentication path;

calculating a new node of the future subtree based on the current value of the signing index;

storing the new node of the future subtree in the buffer memory; and

advancing the signing index from the current value to a next value of the signing index.

14. The computer system of claim 13, the operations comprising:

identifying a right node stored in the buffer memory at a first memory location of the first set of indexed locations;

replacing the right node with its left sibling node in the first memory location.

15. The computer system of claim 13, wherein the active subtree and the future subtree are subtrees of height K, and the total number of nodes in the first and second subsets of nodes is equal to 2^K+(K−

2).

16. The computer system of claim 13, wherein:

the buffer memory is a first buffer memory comprising a bottom nodes cache;

the system further comprises a second buffer memory comprising a top nodes cache;

the active subtree and the future subtree each include nodes below a cut-off level of the cryptographic hash tree; and

generating the authentication path comprises retrieving, from the top nodes cache, one or more nodes above the cut-off level of the cryptographic hash tree.

17. The computer system of claim 16, the operations comprising storing OTS states associated with the active subtree in an OTS cache, wherein generating the OTS signature comprises using one or more of the OTS states associated with the current value of the signing index.

18. The computer system of claim 16, the operations comprising:

identifying a right node stored in a first memory location of the top nodes cache;

replacing the right node with its left sibling node in the first memory location.

19. The computer system of claim 13, wherein the buffer memory comprises a circular buffer memory, the first set of indexed locations are contiguous and the second set of indexed locations are contiguous, and storing the new node of the future subtree in the circular buffer memory shifts a boundary between the first and second sets of indexed locations in the circular buffer memory.

20. The computer system of claim 13, calculating a new node of the future subtree based on the current value of the signing index comprises:

identifying an index of a leaf node of the future subtree based on the current value of the signing index; and

calculating the new node of the future subtree based on the index of the leaf node; and

storing the new node of the future subtree in the buffer memory comprises storing the new node in a first memory location associated with a first index value, and the operations comprise identifying the first index value based on the current value of the signing index.

21. The computer system of claim 13, wherein:

the operations are executed according to a hash-based signature scheme that calculates new leaf nodes of the future subtree in reverse order as the value of the signing index advances through a sequence of values; and

according to the hash-based signature scheme;

each new node of the future subtree is calculated based on a respective current value of the signing index; and

calculating each new node of the future subtree requires calculating only one leaf node of the cryptographic hash tree.

22. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:

storing nodes of a cryptographic hash tree in a buffer memory, wherein storing the nodes in the buffer memory comprises;

storing a first subset of nodes of an active subtree in a first set of indexed locations in the buffer memory; and

storing a second subset of nodes of a future subtree in a second set of indexed locations in the buffer memory, wherein the active subtree and the future subtree are non-overlapping subtrees of the same size;

generating a one-time signature (OTS) based on a signing key associated with a current value of a signing index, wherein the current value of the signing index is associated with a current leaf node of the active subtree;

generating an authentication path for the OTS based on the current value of the signing index, wherein generating the authentication path comprises retrieving one or more of the first subset of nodes from the buffer memory;

providing a digital signature for transmission to a message recipient, the digital signature comprising the OTS and the authentication path;

calculating a new node of the future subtree based on the current value of the signing index;

storing the new node of the future subtree in the buffer memory; and

advancing the signing index from the current value to a next value of the signing index.

23. The computer-readable medium of claim 22, further comprising:

identifying a right node stored in a first memory location of the first set of indexed locations;

replacing the right node with its left sibling node in the first memory location.

24. The computer-readable medium of claim 22, wherein the active subtree and the future subtree are subtrees of height K, and the total number of nodes in the first and second subsets of nodes is equal to 2^K+(K−

2).

25. The computer-readable medium of claim 22, wherein:

the buffer memory comprises a bottom nodes cache;

the active subtree and the future subtree each include nodes below a cut-off level K; and

generating the authentication path comprises retrieving, from a top nodes cache, one or more nodes above the cut-off level of the cryptographic hash tree.

26. The computer-readable medium of claim 25, the operations comprising storing OTS states associated with the active subtree in an OTS cache, wherein generating the OTS signature comprises using one or more of the OTS states associated with the current value of the signing index.

27. The computer-readable medium of claim 25, the operations comprising:

identifying a right node stored in a first memory location of the top nodes cache;

replacing the right node with its left sibling node in the first memory location.

28. The computer-readable medium of claim 22, wherein the buffer memory comprises a circular buffer memory, the first set of indexed locations are contiguous and the second set of indexed locations are contiguous, and storing the new node of the future subtree in the circular buffer memory shifts a boundary between the first and second sets of indexed locations in the circular buffer memory.

29. The computer-readable medium of claim 22, wherein:

calculating a new node of the future subtree based on the current value of the signing index comprises;

identifying an index of a leaf node of the future subtree based on the current value of the signing index; and

calculating the new node of the future subtree based on the index of the leaf node; and

storing the new node of the future subtree in the buffer memory comprises storing the new node in a first memory location associated with a first index value, and the operations comprise identifying the first index value based on the current value of the signing index.

30. The computer-readable medium of claim 22, wherein:

the operations are executed according to a hash-based signature scheme that calculates new leaf nodes of the future subtree in reverse order as the value of the signing index advances through a sequence of values; and

according to the hash-based signature scheme;

each new node of the future subtree is calculated based on a respective current value of the signing index; and

calculating each new node of the future subtree requires calculating only one leaf node of the cryptographic hash tree.