Odd index precomputation for authentication path computation

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.

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.