Merkle signature scheme tree expansion
AssigneeAmazon Technologies, Inc.
InventorsSlavka Praus, Matthew John Campagna, Nicholas Alexander Allen, Petr Praus
Life of this patent
Estimating the term…
Abstract
A first public key is generated based at least in part on a first plurality of signing keys and a second public key is generated based at least in part on a second plurality of signing keys. The signing keys may be used to generate digital signatures. The second public key may be made available to verify a digital signature generated using a signing key from the second plurality of signing keys. In some cases, a first Merkle tree may be formed by the first public key and the first plurality of signing keys, and a second Merkle tree may be formed by the second public key, the first public key, and the second plurality of signing keys.
Claims20
A computer-implemented method, comprising:
- obtaining, from a client computer system, a signature verification request comprising:
- a message;
- a digital signature;
- a signing key of a first plurality of signing keys, wherein the first plurality of signing keys are used to compute a first Merkle tree with a first root value that corresponds to a first public key;
- and
- a first set of public signature verification information derived at least in part from the first plurality of signing keys;
- verifying the digital signature using at least the message and the signing key;
- verifying the first public key is derivable based at least in part on the signing key and the first set of public signature verification information;
- verifying a second public key is derivable based at least in part on the first public key and a second set of public signature verification information derived at least in part from a second plurality of signing keys, wherein the second plurality of signing keys and the first public key are used to compute a second Merkle tree with a second root value that corresponds to the second public key;
- and
- as a result of successfully deriving the second public key, providing an indication to the client computer system that the digital signature is authentic.
A system, comprising one or more processors and memory storing instructions that, as a result of execution by the one or more processors, cause the system to:
- obtain a request comprising:
- a message;
- a digital signature;
- a signing key of a first plurality of signing keys;
- and
- a first set of public signature verification information derived at least in part from the first plurality of signing keys;
- verify the digital signature using at least the message and the signing key;
- verify a first public key is derivable based at least in part on the signing key and the first set of public signature verification information;
- verify a second public key is derivable based at least in part on the first public key and a second set of public signature verification information derived at least in part from a second plurality of signing keys;
- and
- provide a response to the request indicating that the digital signature is authentic.
A non-transitory computer-readable storage medium storing executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
- obtain, from a client computer system, a signature verification request comprising:
- a message;
- a digital signature;
- a signing key of a first plurality of signing keys;
- and
- a first set of public signature verification information derived at least in part from the first plurality of signing keys;
- verify the digital signature using at least the message and the signing key;
- verify a first public key is derivable based at least in part on the signing key and the first set of public signature verification information;
- verify a second public key is derivable based at least in part on the first public key and a second set of public signature verification information derived at least in part from a second plurality of signing keys;
- and
- provide an indication to the client computer system that the digital signature is authentic.
Dependencies are inferred from the claim text.