Blockchain post-quantum signature scheme
AssigneeR3 Ltd.
InventorKonstantinos Chalkias
Life of this patent
Estimating the term…
Abstract
Various systems for providing secure signatures based on post-quantum computing are provided. The systems allow may one-time signatures (“OTS”) to be based on the same public key. The systems provide for efficient use of OTS signatures with blockchains. The systems provide for rapid verification of signatures. The systems provide for caching for Winternitz-based OTS schemes and for use of short checksum.
Claims79
A method performed by a computing system for generating a public key, the method comprising:
- generating a plurality of one-time signature (“OTS”) key pairs, each OTS key pair including an OTS private key and an OTS public key;
- for each of the OTS key pairs, generating a hash of the OTS public key of that OTS key pair;
- generating a hash that is a hash of a seed, the seed being a random number that is not an OTS private key or an OTS public key;
- for each OTS key pair in sequence, generating a hash of a hash derived from the OTS public key of that OTS key pair and a previously generated hash;
- and
- designating as the public key a generated hash.
A method performed by a computing system for generating a public key, the method comprising:
- generating a first one-time signature (“OTS”) key pair that includes a first OTS private key and a first OTS public key;
- generating a first fallback OTS key pair that includes a first fallback OTS private key and a first fallback OTS public key;
- and
- generating as the public key a hash of a hash of the first fallback OTS public key and a hash of the first OTS public key wherein the first OTS private key is for signing a first message and the first fallback OTS private key is for signing a hash of a hash of a second fallback OTS public key of second fallback OTS key pair and hash of a second OTS public key of a second OTS key pair.
(canceled)
(canceled)
A method performed by a computing system for generating a public key, the method comprising:
- generating multiple OTS key pairs;
- generating a fallback OTS key pair;
- and
- generating a hash derived from the multiple OTS key pairs and the fallback OTS key pair wherein the hash is the public key.
(canceled)
A method performed by a computing system for generating a signature for content based on a public key, the method comprising:
- adding to the signature a one-time signature (“OTS”) signature of the content, the OTS signature generated based on an OTS key pair used to generate the public key;
- and
- adding to the signature metadata to generate the public key based on one or more other OTS key pairs used to generate the public key and a fallback OTS key pair
- wherein the metadata includes:
- zero or more hashes that are each derived from an OTS key pair used to generate a signature based on the public key;
- and
- a hash derived from an OTS key pair not used to generate a signature based on the public key and the fallback OTS key pair.
23-31. (canceled)
A method performed by a computing system for generating a signature for data, the method comprising:
- identifying a nonce such that a target hash of a combination of the data and the nonce has a target characteristic;
- signing the target hash with a private key;
- and
- providing the signed target hash as the signature with the nonce as metadata of the signature.
A method performed by a computing system for generating a signature based on a chain of hashes, the signature being generated using a private key for each unit of data to be signed, each unit of data comprising multiple bits of the data, the method comprising:
- for each of the private keys, generating hash values for one or more multiple hashes of the private key, each hash value representing a number of hashes of the private key, the number corresponding to one of the possible values of a unit;
- and
- after generating the hash values,
- receiving an indication of the data;
- and
- for units of the data,
- retrieving a hash value for the unit of the data that corresponds to a value that is not greater than the value of the unit;
- and
- performing zero or more hashes of the hash value so that the hash value corresponds to the value of the unit;
- wherein the signature includes the hash values that correspond to the values of the units of the data.
52-58. (canceled)
A computer-readable storage medium storing a chain of hash trees, the chain of hash trees comprising:
- a last hash tree in the chain that has a first leaf node with a value that is a hash of a seed and a second leaf node with a value that is a hash derived from a one-time signature (“OTS”) public key of an OTS key pair and having a root node with a value that is a hash of the combination of the value of the first leaf node and the second leaf node;
- and
- for each next level in the chain until a first level, a hash tree having a first leaf node with the value of the root node of the previous level in the chain and a second leaf node with a value that is a hash derived from an OTS public key of an OTS key pair and having a root node with a value that is a hash of the combination of the value of the first leaf node and the second leaf node.
A computing system for generating a public key, the computing system comprising:
- one or more computer-readable storage mediums storing computer-executable instructions for controlling the computing system to:
- access a plurality of one-time signature (“OTS”) key pairs, each OTS key pair including an OTS private key and an OTS public key;
- for each of the OTS key pairs, generate a hash of the OTS public key of the OTS key pair;
- generate a public key hash that is based on a seed and hashes of the OTS public keys;
- and
- designate the public key hash as the designated public key;
- and
- one or more processors for executing the computer-executable instructions stored in the one or more computer-readable storage mediums.
A method performed by a computing system for generating a signature for a message, the signature for use in regenerating a public key based on multiple one-time signature (“OTS”) key pairs, the method comprising:
- adding to the signature an OTS signature for the message generated using an OTS private key of an OTS key pair;
- and
- adding to the signature metadata that includes:
- for each signature previously generated based on the public key, a hash derived from the OTS public key of the OTS key pair used to generate the OTS signature for that signature;
- and
- a value derived from hashes of OTS public keys for OTS key pairs not yet used to generate a signature based on the public key.
A computer-readable storage medium storing a signature based on a public key derived from multiple one-time signature (“OTS”) key pairs, the signature comprising:
- an OTS signature generated using an OTS private key of an OTS key pair;
- and
- metadata that includes:
- for each signature previously generated based on the public key, a hash derived from the OTS public key of the OTS key pair used to generate the OTS signature for that signature;
- and
- a value derived from hashes of OTS public keys for OTS key pairs not yet used to generate a signature based on the public key.
A computing system for generating a signature for data, the signature for use in regenerating a public key based on multiple one-time signature (“OTS”) key pairs, the computing system comprising:
- one or more computer-readable storage mediums storing computer-executable instructions for controlling the computing system to:
- generate an OTS signature for the data, the OTS signature generated using an OTS private key of an OTS key pair;
- and
- generate metadata that includes used metadata derived from one or more OTS public keys used to generate an OTS signature for one or more signatures previously generated based on the public key and not used metadata derived from one or more OTS public keys for OTS key pairs not yet used to generate a signature based on the public key;
- and
- one or more processors for executing the computer-executable instructions stored in the one or more computer-readable storage mediums.
A method performed by a computing system for regenerating a public key, the public key generated from one-time signature (“OTS”) public keys of multiple OTS key pairs, the method comprising:
- accessing a signature having:
- an OTS signature generated using an OTS key pair;
- for each OTS key previously used to generate a signature if any, a used hash derived from an OTS public key of the OTS key pair;
- and
- a not used hash derived from a seed and hashes of OTS public keys for OTS key pairs if any not yet used to generate a signature based on the public key;
- regenerating an OTS public key from the OTS signature;
- generating as a value for a new root a hash of a combination of the not used hash of and the regenerated OTS public key;
- and
- for each used hash in reverse order of usage, generating as a value for a new root a hash of a combination of the value of the last root and a hash of the OTS public key of the OTS key pair;
- wherein the last generated value for a new root node is the regenerated public key.
A computing system for regenerating a public key, the public key generated from one-time signature (“OTS”) public keys of multiple OTS key pairs, the computing system comprising:
- one or more computer-readable storage mediums storing computer-executable instructions for controlling the computing system to:
- access a signature having an OTS signature and metadata;
- regenerate an OTS public key from the OTS signature generated using an OTS key pair;
- and
- generate the public key as a hash based on the regenerated OTS public key, not used metadata of the signature, and used metadata of the signature, the used metadata derived from one or more OTS public keys of OTS key pairs if any used to generate an OTS signature for one or more signatures previously generated based on the public key, the not used metadata derived from one or more OTS public keys for OTS key pairs if any not yet used to generate a signature based on the public key;
- and
- one or more processors for executing the computer-executable instructions stored in the one or more computer-readable storage mediums.
A method performed by a computing system for generating a public key, the method comprising:
- generating a plurality of one-time signature (“OTS”) key pairs;
- and
- generating a hash derived from the OTS public keys of the OTS key pairs wherein the hash is the public key.
A method performed by a computing system for generating a signature for content based on a public key, the method comprising:
- adding to the signature a one-time signature (“OTS”) signature of the content, the OTS signature generated based on an OTS key pair used to generate the public key;
- and
- adding to the signature metadata to generate the public key based on one or more other OTS key pairs used to generate the public key.
A method performed by a computing system for regenerating a public key generated based on multiple one-time signature (“OTS”) key pairs, the method comprising:
- regenerating, from a signature and content, an OTS public key of one of the OTS key pairs used to sign the content;
- and
- generating a hash derived from the regenerated OTS public key and metadata of the signature, the metadata being derived from one or more other OTS key pairs used to generate the public key.
Dependencies are inferred from the claim text.