Odd index precomputation for authentication path computation

Patent metadata

Field	Value
Publication number	US-11770262-B2
Application number	US-202217568919-A
Country	US
Kind code	B2
Filing date	Jan 5, 2022
Priority date	Jun 28, 2019
Publication date	Sep 26, 2023
Grant date	Sep 26, 2023

Abstract

In one example an apparatus comprises a computer-readable memory, signature logic to compute a message hash of an input message using a secure hash algorithm, process the message hash to generate an array of secret key components for the input message, apply a hash chain function to the array of secret key components to generate an array of signature components, the hash chain function comprising a series of even-index hash chains and a series of odd-index hash chains, wherein the even-index hash chains and the odd-index hash chains generate a plurality of intermediate node values and a one-time public key component between the secret key components and the signature components and store at least some of the intermediate node values in the computer-readable memory for use in one or more subsequent signature operations. Other examples may be described.

First claim

What is claimed is:

1. An apparatus, comprising a hardware processor to:
compute a message hash of an input message using a secure hash algorithm;
process the message hash to generate an array of secret key components for the input message;
apply a hash chain function to the array of secret key components to generate an array of signature components, the hash chain function comprising a series of even-index hash chains and a series of odd-index has chains, wherein the even-index hash chains and the odd-index hash chains generate a plurality of intermediate node values and a one-time public key component between the secret key components and the signature components; and
store at least some of the intermediate node values in the computer-readable memory for use in one or more subsequent signature operations
compute the message hash of the input message using at least one of a Winterniz One Time Signature (WOTS) scheme or a WOTS+scheme that invokes a secure hash algorithm (SHA) hash function
apply a L-tree operation to the public key components to compress the public key components into a single leaf node value; and
provide the single leaf node value as an input to the Merkle tree.

2. The apparatus of claim 1 , the hardware processor to:
store the intermediate node values generated and one time public key components generated by the even-index hash chains in the computer-readable memory; and
use the one-time public key components to define computations through an authentication path through a Merkle tree.

3. The apparatus of claim 1 , the hardware processor to:
perform a first hash operations using the single leaf node value and a first odd-index public key component to generate a first parent node in the Merkle tree; and
perform a series of hash operations using subsequent odd-index public key components to determine a root node value of the Merkle tree.

4. The apparatus of claim 3 , the hardware processor to:
compare the root node value of the Merkle tree to a multi-signature public key value associated with the signing device; and
generate an authentication success signal when the root node value of the Merkle tree matches the multi-signature public key value associated with the signing device.

5. The apparatus of claim 3 , the hardware processor to:
compare the root node value of the Merkle tree to a multi-signature public key value associated with the signing device; and
generate an authentication fail signal when the root node value of the Merkle tree does not match the multi-signature public key value associated with the signing device.

6. A method implemented in a hardware processor, comprising:
computing a message hash of an input message using a secure hash algorithm;
processing the message hash to generate an array of secret key components for the input message;
applying a hash chain function to the array of secret key components to generate an array of signature components, the hash chain function comprising a series of even-index hash chains and a series of odd-index hash chains, wherein the even-index hash chains and the odd-index hash chains generate a plurality of intermediate node values and a one-time public key component between the secret key components and the signature components; and
storing at least some of the intermediate node values in the computer-readable memory for use in one or more subsequent signature operations
computing the message hash of the input message using at least one of a Winterniz One Time Signature (WOTS) scheme or a WOTS+scheme that invokes a secure hash algorithm (SHA) hash function
applying a L-tree operation to the public key components to compress the public key components into a single leaf node value; and
providing the single leaf node value as an input to the Merkle tree.

7. The method of claim 6 , further comprising:
storing the intermediate node values generated and one time public key components generated by the even-index hash chains in the computer-readable memory; and
using the one-time public key components to define computations through an authentication path through a Merkle tree.

8. The method of claim 6 , further comprising:
performing a first hash operations using the single leaf node value and a first odd-index public key component to generate a first parent node in the Merkle tree; and
performing a series of hash operations using subsequent odd-index public key components to determine a root node value of the Merkle tree.

9. The method of claim 8 , further comprising:
comparing the root node value of the Merkle tree to a multi-signature public key value associated with the signing device; and
generating an authentication signal when the root node value of the Merkle tree matches the multi-signature public key value associated with the signing device.

10. The method of claim 8 , further comprising:
comparing the root node value of the Merkle tree to a multi-signature public key value associated with the signing device; and
generating an authentication fail signal when the root node value of the Merkle tree does not match the multi-signature public key value associated with the signing device.

11. A non-transitory computer-readable medium comprising instructions which, when executed by a hardware processor, configure the hardware processor to perform operations, comprising:
storing a public key associated with a signing device in a computer-readable medium;
computing a message hash of an input message using a secure hash algorithm;
processing the message hash to generate an array of secret key components for the input message;
applying a hash chain function to the array of secret key components to generate an array of signature components, the hash chain function comprising a series of even-index hash chains and a series of odd-index hash chains, wherein the even-index hash chains and the odd-index hash chains generate a plurality of intermediate node values and a one-time public key component between the secret key components and the signature components; and
storing at least some of the intermediate node values in the computer-readable memory for use in one or more subsequent signature operations
computing the message hash of the input message using at least one of a Winterniz One Time Signature (WOTS) scheme or a WOTS+scheme that invokes a secure hash algorithm (SHA) hash function
applying a L-tree operation to the public key components to compress the public key components into a single leaf node value; and
providing the single leaf node value as an input to the Merkle tree.

12. The non-transitory computer-readable medium of claim 11 , further comprising instructions which, when executed by the hardware processor, configure the hardware processor to perform operations, comprising:
storing the intermediate node values generated and one time public key components generated by the even-index hash chains in the computer-readable memory; and
using the one-time public key components to define computations through an authentication path through a Merkle tree.

13. The non-transitory computer-readable medium of claim 11 , further comprising instructions which, when executed by the hardware processor, configure the hardware processor to perform operations, comprising:
performing a first hash operations using the single leaf node value and a first odd-index public key component to generate a first parent node in the Merkle tree; and
performing a series of hash operations using subsequent odd-index public key components to determine a root node value of the Merkle tree.

14. The non-transitory computer-readable medium of

Assignees

• Intel Corp

Inventors

• Misoczki Rafael
• Suresh Vikram
• Ghosh Santosh
• Sastry Manoj
• Mathew Sanu
• Kumar Raghavan

Classifications

• H04L9/3247 Primary

  involving digital signatures · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L9/0852 Primary

  Quantum cryptography (transmission systems employing electromagnetic waves other than radio waves, e.g. light, infrared H04B10/00; wavelength-division multiplex systems H04J14/02; WDM arrangements H04J14/03) · CPC title

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L9/3239 Primary

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title