Toolkit for post-quantum secure protocols in ledgers

blog
One of the deliverables of the PRIViLEDGE project is a toolkit for post-quantum secure protocols in ledgers. The toolkit will provide client components to enable access to two security mechanisms expected to provide post-quantum security.

Both mechanisms are based on hash functions which are widely believed to be resistant to quantum attacks, with best known quantum attacks against them still having exponential complexity (in contrast with the polynomial complexity of quantum attacks against systems based on the hardness of factoring or computing discrete logarithms).

The purpose of the BLT signature scheme is to provide an alternative authentication mechanism. The KSI time-stamping service is a supporting component for the BLT signature scheme, but it may also be of independent interest in some use-cases.

Hash functions

In general, a hash function h maps arbitrary-sized bit-strings as inputs to fixed-size bit-strings as outputs. Hash values are often used as representatives of data that are either too large or too confidential to be used directly. To facilitate such uses, cryptographic hash functions are required to have several additional properties.

One-wayness (a.k.a. pre-image resistance). Given an input x, it should be efficient to compute y = h(x). But, given an output y, it should be infeasible to find a matching input x such that h(x) = y. In classical world, there is a natural upper bound of 2k on the one-wayness of a hash function with k-bit outputs: assuming uniform distribution of outputs, a randomly generated x will map to the desired value with probability 2-k and an adversary that can afford to generate 2k random inputs and evaluate the function on all of them is expected to find a match. A good hash function is expected to have one-wayness close to that theoretical upper bound. However, an adversary using a quantum computer can use Grover's algorithm to find a pre-image of y in just 2k/2 guesses.

Second pre-image resistance. Given an input x, it should be infeasible to find a second input x' such that x' ≠ x, but h(x') = h(x). For a good hash function, second pre-image resistance is expected to be the same as one-wayness against both classical and quantum adversaries.

Collision resistance. It should be infeasible to find two inputs x1 and x2 such that x1 ≠ x2, but h(x1) = h(x2). The difference from the second pre-image resistance is that the attacker has the freedom to choose both x1 and x2. In classical setting, the upper bound for the collision resistance of a k-bit hash function is 2k/2: in a set of randomly generated inputs, the probability of any pair forming a collision is 2-k; as the number of pairs grows quadratically with the size of the set, an adversary that can afford to generate 2k/2 inputs and check for duplicates in the set of corresponding outputs is expected to find a matching pair. A quantum adversary can use the BHT algorithm to find a collision in 2k/3 attempts instead.

The important point to note is that the attacks have exponential costs even for quantum adversaries.

A hash tree (a.k.a. Merkle tree) is a tree-shaped data structure built using a 2-to-1 hash function h mapping 2k-bit inputs to k-bit outputs. The nodes of the tree contain k-bit values. Each node is either a leaf with no children or an internal node with two children. The value x of an internal node is computed as x = h(xl, xr), where xl and xr are the values of the left and right child, respectively. To prove that a value xi participated in the computation of the root hash r, it is sufficient to present values of all the sibling nodes on the unique path from xi to the root in the tree.


Figure 1: A hash tree with 4 leaves (left) and the hash chain for x3 (right).

For example, to claim that x3 belongs to the tree shown on the left in Fig. 1, one has to present the values x4 and x1,2 to enable the verifier to compute x3,4 = h(x3, x4) and r = h(x1,2, x3,4), essentially re-building a slice of the tree, as shown on the right in Fig. 1. If the newly computed value of r matches the original, this proves that x3 indeed was part of the original tree.


KSI time-stamping

The KSI blockchain provides a hash-and-publish time-stamping service backed by control publications in physical media. Once connected to the publications, the evidentiary value of the time-stamp tokens relies only on security properties of cryptographic hash functions and does not depend on asymmetric cryptographic primitives or secrecy of any keys or passwords.

Aggregation and linking. The service operates in fixed-length rounds. During each round, incoming client requests are aggregated into a globally distributed temporary hash tree (Fig. 2, left). At the end of the round, the root of the aggregation tree is added to a persistent append-only data structure built around another hash tree, called the calendar blockchain (Fig. 2, right), and each client receives a two-part response consisting of

  • a hash chain linking their request to the root of the aggregation tree; and
  • another hash chain linking the root of the aggregation tree to the new root of the calendar tree; this chain can be used to verify that the new state of the calendar blockchain was obtained from the previous one by appending the new aggregation tree root without changing anything else.

After that, the aggregation tree can be discarded and a new one is built for the next round.


Figure 2: KSI architecture: aggregation (left) and linking (right).

Publishing. Periodically, the root hash value of the calendar blockchain is printed as a control publication in physical media (Fig. 3, left). Each such publication printed in a widely circulated newspaper (Fig. 3, right) acts as a trust anchor that protects the integrity of the history of the blockchain up to the round from which the publication was extracted.


Figure 3: KSI publishing (left) and a publication (right).

Client passwords or keys may be used for service access control, but they do not affect the proof of data integrity or time. A set of symmetric keys is used to authenticate communications among the consensus nodes maintaining and updating the calendar blockchain, but their compromise also does not affect the evidentiary value of the time-stamp tokens already issued and linked to control publications.

A possible use of the KSI service in other ledgers is to time-stamp blocks of a private ledger to provide immunity against the so-called rewind-edit-replay attacks where the consortium managing the ledger agrees to retroactively edit some past transactions and modify all subsequent blocks to match the modified history. Alternatively, direct access to the KSI service from smart contract applications may be enabled for similar purposes.

Of course, the consortium maintaining the ledger could issue their own publications, but this would incur additional cost and hassle that can be avoided by delegating the task to the KSI service designed specifically for the purpose. Additionally, most ledgers have a linear structure and a proof linking any particular transaction to a publication would have to traverse many blocks. The KSI blockchain uses a hash tree to enable proofs whose size is logarithmic in the number of aggregation rounds.

BLT signature scheme

BLT combines a time-stamping service and message authentication codes with time-bound one-time keys to obtain a server-assisted signature scheme whose long-term evidentiary value relies only on security of cryptographic hash functions and the assumption of secrecy of the one-time keys up to the signing time .

Key generation. Each of the signing keys z1, z2, ..., zN is generated as an unpredictable value drawn from a sufficiently large set. Each key is pre-bound to a designated usage time by computing commitments xi = h(ti, zi), where ti is the designated usage time for the key zi. The commitments are aggregated into a hash tree T and the root hash value of the tree is distributed as the signer's public key p. The purpose of the resulting data structure (Fig. 4) is to be able to extract hash chains linking the signing key commitments h(ti, zito the public key p.


Figure 4: Computation of BLT public key for N = 4.

Signing. To sign the message m at time ti, the signer authenticates the message with the corresponding signing key by computing y = h(m, zi) and then proves the time of usage of the key by obtaining a time-stamp at on the message authenticator y. The signature is then composed as s = (ti, zi, ci, at), where ci is the hash chain authenticating the membership of the pair (ti, zi) in the hash tree of the client's signing keys. Note that it is safe to release the key zi as part of the signature, as its designated usage time has passed and thus it can't be used to generate any new signatures.

Verification. To verify the signature s = (t, z, c, a) on message m against the public key p, the verifier checks that

  • z was committed as signing key for time t (by verifying that the hash chain c links the commitment x = h(t, z) to the public key p); and
  • m was authenticated with z at time t (by verifying that a correctly time-stamps the authenticator y = h(m, z) at time t).

The primary goal of the BLT component of the toolkit is to provide a replacement for asymmetric-key based digital signature schemes as transaction authentication mechanism.

Note that the security of the signature scheme critically depends on the security of the time-stamping service against back-dating attacks by the adversary. Therefore, a post-quantum secure time-stamping service is a necessary pre-condition for post-quantum security of the signature scheme.

Additionally, the ledger whose transactions are to be authenticated by the signatures cannot itself be used to prove the usage times of the keys, and therefore an external time-stamping service is needed for that purpose.

The toolkit is currently in development and expected to be released in the first half of 2020.


Written by Ahto Truu, Guardtime