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.
Claims58
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;
- 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.
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.
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.
A method performed by a computing system for generating signatures for multiple instances of content, the method comprising:
- generating a public key based on a first OTS key pair and a first fallback OTS key pair;
- generating a first signature of a first instance that includes a first OTS signature based on the first OTS key pair and first metadata based on the first fallback OTS key pair;
- and
- generating a second signature of a second instance that includes a second OTS signature based on a second OTS key pair and second metadata based on a second fallback OTS key pair and a fallback OTS signature of data derived from the second OTS key pair and the second fallback OTS key pair generated based on the first fallback OTS key pair.
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, 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 bit-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 bit-value that is not greater than the bit-value of the unit;
- and
- performing zero or more hashes of the hash value so that the hash value corresponds to the bit-value of the unit;
- wherein the signature includes the hash values that correspond to the bit-values of the units of the data.
A method performed by a computing system for generating a signature for data, the method comprising:
- dividing the data into data units, each data unit having a same data unit number of bits and a value;
- for each data unit of the data, generating a chain of hashes with a length that is based on the value of that data unit;
- generating a checksum for the data;
- dividing the checksum into one or more checksum units, each checksum unit having a number of bits and a value, at least one checksum unit having a number of bits that is different from the data unit number of bits;
- and
- for each checksum unit of the checksum, generating a chain of hashes with a length that is based on the value of that checksum unit.
Dependencies are inferred from the claim text.