# US 2019/0319798 A1 · Blockchain post-quantum signature scheme

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

- Number: US 2019/0319798 A1
- Document ID: US20190319798A1
- Status: Published application
- Kind: A1
- Application number: 16/024,604
- Filed: 2018-06-29
- Published: 2019-10-17
- Earliest claimed: 2018-04-16
- Assignees: R3 Ltd.
- Applicants: R3 Ltd.
- Inventors: Konstantinos Chalkias
- Web page: https://patentgrep.com/patent/US20190319798A1

## CPC

- H04L 9/3247: {involving digital signatures}
- 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/0863: {involving passwords or one-time passwords (network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067)}
- H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)}
- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 9/3236: {using cryptographic hash functions}
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- H04L 9/3297: {involving time stamps, e.g. generation of time stamps}
- 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

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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1 wherein the designating designates the last generated hash as the public key.

### Claim 3 (depends on 1)

The method of claim 1 wherein the previously generated hash is the last generated hash.

### Claim 4 (depends on 1)

The method of claim 1 wherein the hashes form a hash tree with the hash of the seed and the hashes derived from the OTS public keys of the OTS key pairs being the values of leaf nodes of the hash tree.

### Claim 5 (depends on 1)

The method of claim 1 wherein the generated hashes are values of root nodes of a chain of hash trees wherein the last hash tree in the chain has as the value of its root node a hash of the hash of the seed and the hash an OTS public key and the first hash tree in the chain has as the value of its root node the last generated hash.

### Claim 6 (depends on 1)

The method of claim 1 wherein the OTS key pairs are based on a Lamport OTS scheme.

### Claim 7 (depends on 1)

The method of claim 1 wherein the OTS key pairs are based on a Winternitz-based OTS scheme.

### Claim 8 (depends on 1)

The method of claim 1 wherein the seed is a hash of a non-OTS public key.

### Claim 9 (depends on 1)

The method of claim 1 wherein the public key is based on a hash of a non-OTS public key.

### Claim 10

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.

### Claim 11 (depends on 10)

The method of claim 10 wherein the OTS key pairs are based on a Lamport OTS scheme.

### Claim 12 (depends on 10)

The method of claim 10 wherein the OTS key pairs are based on a Winternitz-based OTS scheme.

### Claim 13 (depends on 10)

The method of claim 10 further comprising generating a first signature of the first message that includes a first OTS signature of the first message and a hash of the first fallback OTS public key.

### Claim 14 (depends on 13)

The method of claim 13 further comprising generating a second signature of a second message that includes a second OTS signature of the second message based on a second OTS private key of the second OTS key pair and includes a hash of the first OTS public key.

### Claim 15 (depends on 14)

The method of claim 14 wherein the second signature includes a hash of a second fallback OTS public key of a second fallback OTS key pair.

### Claim 16

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.

### Claim 17 (depends on 16)

The method of claim 16 wherein the generating of the hash further comprises:
generating a first hash derived from a hash of a fallback OTS public key of the fallback OTS key pair and a hash of a first OTS public key of first OTS key pair; and
for each other OTS key pair, generating a next hash derived from an OTS public key of the OTS key pair and the last generated hash.

### Claim 18 (depends on 16)

The method of claim 16 wherein the OTS key pairs are based on a Lamport OTS scheme.

### Claim 19 (depends on 16)

The method of claim 16 wherein the OTS key pairs are based on a Winternitz-based OTS scheme.

### Claim 20

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.

### Claim 21 (depends on 20)

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

### Claim 22 (depends on 21)

The method of claim 21 wherein at least some of the OTS key pairs used to generate a signature were not used to generate the public key.

### Claim 23

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.

### Claim 24 (depends on 23)

The method of claim 23 wherein the first public key is a hash of a hash of a first OTS public key of the first OTS key pair and of a hash of a first fallback OTS public key of the first fallback OTS key pair.

### Claim 25 (depends on 23)

The method of claim 23 wherein the first metadata includes a hash of a first fallback OTS public key of the first fallback OTS key pair.

### Claim 26 (depends on 23)

The method of claim 23 wherein the second metadata includes a hash of a second fallback OTS public key of the second fallback OTS key pair and the fallback OTS signature is of data that includes a hash of a hash of the second fallback OTS public key and of a hash of a second OTS public key of the second OTS key pair.

### Claim 27 (depends on 23)

The method of claim 23 wherein each instance of content is a block of a distributed ledger.

### Claim 28 (depends on 27)

The method of claim 27 wherein the distributed ledger is a blockchain.

### Claim 29 (depends on 23)

The method of claim 23 wherein each instance is a transaction to be recorded in a distributed ledger.

### Claim 30 (depends on 29)

The method of claim 29 wherein the transactions form a sequence of transactions.

### Claim 31 (depends on 23)

The method of claim 23 wherein the second metadata includes a reference to the first instance.

### Claim 32

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.

### Claim 33 (depends on 32)

The method of claim 32 wherein a public key corresponding to the private key is a hash of the private key.

### Claim 34 (depends on 32)

The method of claim 32 wherein the signature is based on a one-time signature technique.

### Claim 35 (depends on 34)

The method of claim 34 wherein the target characteristic is a pattern of pattern bits within the target hash with each pattern bit having a pattern value.

### Claim 36 (depends on 35)

The method of claim 35 wherein the signing of the target hash is based on bits that are not pattern bits.

### Claim 37 (depends on 35)

The method of claim 35 wherein the target hash has pattern bits and non-pattern bits, the private key is a one-time signature private key with a private key pair for each non-pattern bit, and for each non-pattern bit, the signature includes one of the private keys of the private key pair for each non-pattern bit.

### Claim 38 (depends on 37)

The method of claim 37 wherein the private key includes a private key pair for only non-pattern bits.

### Claim 39 (depends on 32)

The method of claim 32 wherein the target characteristic is based on number of bits having a value of 1.

### Claim 40 (depends on 39)

The method of claim 39 wherein the signature is based on zero or more hashes of a private key for a bit or group of bits.

### Claim 41 (depends on 32)

The method of claim 32 wherein the target characteristic is a pattern of pattern bits within the target hash with each pattern bit having a pattern value and wherein a private key and corresponding public key do not include values for pattern bits.

### Claim 42 (depends on 32)

The method of claim 32 wherein the target characteristic is a pattern of pattern bits within the target hash with each pattern bit having a pattern value and the signature does not include a value for the pattern bits.

### Claim 43 (depends on 32)

The method of claim 32 wherein the target characteristic is that a target number of bits in sequence of the target hash has a target value.

### Claim 44

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.

### Claim 45 (depends on 44)

The method of claim 44 wherein the signature represents a Winternitz-based one-time signature.

### Claim 46 (depends on 44)

The method of claim 44 wherein a hash value is generated for each possible bit-value of a unit.

### Claim 47 (depends on 44)

The method of claim 44 wherein a hash value is generated for possible bit-values of a unit that are an interval apart.

### Claim 48 (depends on 44)

The method of claim 44 wherein the generated hash values are stored in a cache for use when signing the data.

### Claim 49 (depends on 44)

The method of claim 44 wherein the hash values are generated prior to the data being accessed.

### Claim 50 (depends on 44)

The method of claim 44 wherein each private key is a random number with a corresponding public key being a number of hashes of the private key that is based on the maximum bit-value of a unit.

### Claim 51 (depends on 44)

The method of claim 44 wherein the data is a hash of target data.

### Claim 52

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.

### Claim 53 (depends on 52)

The method of claim 52 wherein the at least one checksum unit has more bits than the data unit number of bits.

### Claim 54 (depends on 52)

The method of claim 52 wherein the at least one checksum unit has less bits than the data unit number of bits.

### Claim 55 (depends on 52)

The method of claim 52 wherein the checksum is divided into one checksum unit.

### Claim 56 (depends on 52)

The method of claim 52 wherein the generating of the checksum includes generating a summation based on the values of the data units.

### Claim 57 (depends on 52)

The method of the claim 52 wherein the signature is based on a one-time signature scheme.

### Claim 58 (depends on 52)

The method of claim 52 wherein the signature is based on a Winternitz-based one-time signature scheme.