# US 2019/0319803 A1 · Odd index precomputation for authentication path computation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0319803 A1
- Document ID: US20190319803A1
- Status: Published application
- Kind: A1
- Application number: 16/456,064
- Filed: 2019-06-28
- Published: 2019-10-17
- Earliest claimed: 2019-06-28
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: RAFAEL MISOCZKI; VIKRAM SURESH; SANTOSH GHOSH; MANOJ SASTRY; SANU MATHEW; RAGHAVAN KUMAR
- Web page: https://patentgrep.com/patent/US20190319803A1

## CPC

- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- H04L 9/3247: {involving digital signatures}
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- H04L 9/0852: {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)}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

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

## Claims

### Claim 1

An apparatus, comprising:
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 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.

### Claim 2 (depends on 1)

The apparatus of claim 1, further comprising logic to:
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.

### Claim 3 (depends on 1)

The apparatus of claim 1, further comprising logic 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.

### Claim 4 (depends on 2)

The apparatus of claim 2, the signature logic to:
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.

### Claim 5 (depends on 4)

The apparatus of claim 4, the signature logic 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.

### Claim 6 (depends on 5)

The apparatus of claim 5, comprising logic 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.

### Claim 7 (depends on 5)

The apparatus of claim 5, wherein:
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.

### Claim 8

A computer-implemented method, 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.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
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.

### Claim 10 (depends on 9)

The method of claim 9, 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.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
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.

### Claim 12 (depends on 11)

The method of claim 11, 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.

### Claim 13 (depends on 12)

The method of claim 12, 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.

### Claim 14 (depends on 12)

The method of claim 12, 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.

### Claim 15

A non-transitory computer-readable medium comprising instructions which, when executed by a processor, configure the 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.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, further comprising instructions which, when executed by the processor, configure the processor to perform operations, comprising:
computing the message hash of the input message using at least one of a Winternitz One Time Signature (WOTS) scheme or a WOTS+ scheme that invokes a secure hash algorithm (SHA) hash function.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, further comprising instructions which, when executed by the processor, configure the 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.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, further comprising instructions which, when executed by the processor, configure the processor to perform operations, comprising:
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.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, further comprising instructions which, when executed by the processor, configure the 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.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19, further comprising instructions which, when executed by the processor, configure the processor to perform operations, 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.

### Claim 21 (depends on 19)

The non-transitory computer-readable medium of claim 19, further comprising instructions which, when executed by the processor, configure the processor to perform operations, 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.
