R3 publishes a new post-quantum signature algorithm tailored to blockchains

August 09, 2018

R3 publishes a new post-quantum signature algorithm tailored to blockchains

You might have noticed a few external tweets and reddit posts mentioning that the Corda team has recently announced a new digital signature scheme that unlike RSA and ECDSA, it will remain secure even against a powerful quantum computer. Indeed, our protocol, BPQS, has been published and presented to the IEEE Blockchain 2018 conference which was held in Halifax, Canada a week ago. You can find a copy of the paper in this IACR link.

Note that this post is as less technical as possible and it mainly focuses on:
a) presenting why quantum computers pose a threat to classical cryptography
b) showing why we need to explore quantum resistant algorithms before it’s too late
c) highlighting the false impression that a hashed key policy is immune against quantum attacks
d) explaining why BPQS is a great candidate protocol for post-quantum secure blockchains

* Please read and study the BPQS paper if you want to dive into the cryptographic details on how it actually works and feel free to contact any of the authors for clarifications and potential research collaboration opportunities.

It is also true that this work gained the attention of many researchers, blockchain engineers, industry leaders and HSM (hardware wallet) vendors from all over the world and I got really happy, when after our presentation, and especially the following day, I received more than 50 questions for which I had to draw multiple diagrams and modified Merkle-trees on notebooks and whiteboards in order to explain how BPQS works to excited academics and software developers. Well, this is just the beginning of a new collaboration era for R3 with strong connections to academia and probably joint industry research on “hot” cryptographic topics.

So, how it all begun and what is the secret recipe that makes the BPQS paper unique? To make it clear, it’s not the first scheme that provides post-quantum guarantees, we didn’t even invent a new cryptographic hardness assumption. So what’s the trick? I will just quote three of the reviewers’ comments:

“the idea is fresh and interesting in particular with respect to blockchain applications”, “amazingly, the blockchain structure itself can be used to minimise signature size” and “worth referencing when consider how to improve the blockchain to be quantum resistant”.

Quantum Computers

Before we explain the superiority of BPQS and why it was likely to be invented by a blockchain company, like R3, let’s first take a quick look at current state of the art. I am also highlighting that when we hear the word “post-quantum” it usually implies an algorithm that still runs on conventional CPUs, however it is carefully designed in a way that we don’t know of any quantum algorithm that can break it (yet). Well, we should better say “quantum-resistant”, but literature usually refers to it as “post-quantum”, so we stick to it.

The threat quantum computers pose to classical cryptography has increased the interest in post-quantum research; this is obvious from the increased number of articles dealing with either quantum-based or quantum-resistant solutions. More specifically, due to Shor’s algorithm, a quantum computer could easily factor a big integer in polynomial time, thus effectively break RSA in seconds. Implementations of Shor’s algorithm can also solve discrete logarithms and render today’s digital signatures, such as DSA, ECDSA and EdDSA, useless.

10 years ago there was little evidence of practical quantum computers. But the race has already begun. In 2018, Google unveiled Bristlecone, a new quantum computing chip with 72 qubits, 22 more than the 50-qubit processor announced by IBM in 2017. We should also mention D-Wave, a company that recently announced a 2000-qubit processor optimised for quantum annealing metaheuristics; however, there are reports that D-Wave’s quantum speedup analysis is debatable. To summarise, even though more research and experiments are required to allow for stable quantum chips with low error and noise rates, it is a fact that quantum technology is progressing.

The reality is we have yet to build a computer with the thousands of stable logical qubits required to make classical public key cryptography obsolete. However, some optimistic predictions estimate that a large quantum computer capable of breaking asymmetric cryptography might be available in the next 10 to 20 years. I’m personally more conservative and it might take a bit more than that, but I would highlight that research is driven by market requirements for more time-efficient computing and the ability to solve problems that were previously considered impracticable… and human intelligence usually surprises us.

If the quantum-apocalypse ever happens, the security impact of breaking public key cryptography would be tremendous, as almost everything from HTTPS, VPN
and PKI in general, is basing their authentication, key exchange and digital signatures on classical cryptography. Blockchains would be hit equally hard, and would perhaps be one of the most affected sectors due to direct and untraceable economic incentives.

So, why R3 is exploring post-quantum?

Corda is probably the most “cryptographically” agile blockchain/DLT and since early 2017, users have the option to choose between multiple signing key-types including RSA, ECDSA, EdDSA and SPHINCS. Note that EdDSA is currently the default scheme in Corda, mainly due to its efficiency and security against side-channel attacks. You might not be familiar with the last scheme though, SPHINCS, which is a quantum resistant algorithm, whose construction and security are completely based on hash functions and nothing else; no elliptic curves, no prime numbers, no special maths.

Many of you might not know, but Corda is one of the first blockchains where “obsessed with security” users can sign transactions with post-quantum secure keys. Well, this would make sense especially for long-term contracts, like mortgages and pension schemes. In short, post-quantum algorithms are usually a candidate option in cases where assets should remain locked or inactive for dozens of years.

But, why not use SPHINCS for every transaction? Because there are two major caveats that make it impractical for many blockchain applications: a) its relatively slow signing speed and b) its 41KB signature output.

* The above results are not 100% aligned with reported comparative performance in https://bench.cr.yp.to/ but this is due to Java’s Bouncycastle and i2p libraries implementation details.

It’s true there have been various attempts in the literature to optimise SPHINCS and we know how to produce shorter signatures by using stateful hash-based solutions, such as XMSS and its variants. We went a step further so as to build an efficient post-quantum scheme tailored to blockchains that we could use in Corda and also influence HSM vendors to eventually support post-quantum solutions for demanding customers and applications.

BPQS is actually a modified XMSS protocol, best suited to two types of application requirements:
a) when signing keys are used once or just a few times (i.e., 3 times). The most common example is one-time addresses, which is the recommended approach in public blockchains
b) when there is an underlying immutable graph structure which can serve the role of a global cache, independently on how many times a key is reused. For instance, in permissioned blockchains some entities are known to sign with the same legal-identity key again and again, i.e., notaries or oracles.

Ah, forgot to mention that the crypto agility feature is one of the differentiation factors between Corda and other distributed ledgers. For some reason we don’t advertise it a lot, but one can practically build a new post-quantum token or secure critical contracts requiring multiple signature key-types. The latter is possible via the CompositeKey feature in Corda, where you can apply a “belts and braces” approach and simultaneously sign a transaction with multiple keys, such as ECDSA, RSA and BPQS, so that all of these algorithms should break for your assets to be stolen. A similar combined method was recently explored by Google in their CECPQ1 post-quantum cipher suite TLS experiments.

The misconception: hashed keys to the rescue for existing blockchains, such as Bitcoin and Ethereum.

Most blockchains mitigate the quantum threat by using addresses that are generated from cryptographic hashes of the public keys. This additional layer
of security means that a public key only gets exposed to the ledger after the first transaction that it participates in occurs (i.e., when a Bitcoin is spent). Until this point, only the hashed recipient key (the address) is exposed and consequently attacks such as Shor’s algorithm are not applicable at this stage.

However, the following attack vectors are still applicable, even when hashed keys are utilised:

In short, users tend to reuse their keys on purpose, by mistake or some times because they don’t have other options. The most interesting example is forked blockchains, where the same key holds assets in two or more chains and at the time you spend on one of them, the public key gets exposed. In-flight transactions and transaction mixing also reveal the public keys for a few moments, and this time-window will be more than enough to derive the private key when a proper quantum computer gets available.

Hash-Based Signature schemes

BPQS is a hash-based signature and as such, it uses one-time signature (OTS) schemes as a fundamental building block. Unlike most other signature schemes, OTS requires only a secure cryptographic hash function and no other hardness assumption (about a number-theoretic problem) and is not known to be vulnerable to Shor’s algorithm. Secure here refers to either hash collision resistance or mere second pre-image resistance, depending on the specific one-time signature used.

Common examples of one-time signature schemes are the seminal one by Lamport, the Winternitz scheme and its recent variant W-OTS+. In one-time signatures, the private key consists of randomly generated values and the public key is a function of the private key, involving the underlying hash function.

The picture below depicts a very basic voting example where I want to sign one bit of information using Lamport’s algorithm. Briefly,
a) I initially generate two random values and I use them as my private key (in this picture 2cf24dba5fb0 and ab321687ddf1, respectively).
b) Then, I hash both values independently and the resulted outputs form my public key (f3287632cd32 and 90fffe215668).
c) I then publish my two public key parts and we all agree that the left part will correspond to bitValue=0 (i.e., if my vote is NO), while the one on the right corresponds to bitValue=1 (i.e., if my vote is YES).
d) Now, when I actually submit my vote, I will reveal one of the two private keys depending on my choice. As I am the only person who knows these two values, if I publish ab321687ddf1, then every verifier can check that it corresponds to my right public key part, so they can be convinced I voted YES.

If we use the same logic for extra bits of information, we will eventually be able to sign any message. There is an excellent post that explains with easy to follow diagrams how the major hash-based signature schemes work, thus, if you want to learn more, visit this link.

For the time being, I’m not getting into the low-level cryptographic details. But, I need to mention that OTS, as its name states, are inadequate on their own in practice, since each one-time private key can only be used to securely sign a single message. Hm… we’ve already mentioned we might need to reuse a key and sign a second message. Now what?

Blockchained Post-Quantum Signatures

Unfortunately, each time we reuse an OTS key, the advertised bits of security are reduced to half (on average). Surprisingly, there are existing blockchains that assume one-time is enough, which is obviously wrong. IOTA is such an example, and it has been reported that some wallets do not allow you to sign for a second time with the same key. The latter results to asset freezing if for instance the first transaction never goes through. I’m wondering what is the plan in case of a fork, in which case it will be inevitable that one needs to sign at least two times.

Although there are extensions of the simple OTS schemes to allow for multiple times signing, such as SPHINCS, they are not that fast and succinct, while in some cases key generation is very expensive. However, in blockchains, most of the times we need to sign once and in rare cases we need to reuse a key. But because these are exceptional cases, we realised we don’t really need the complexity of schemes like SPHINCS and XMSS, but a fallback key, which will be activated only when we need to sign again.

BPQS is actually a chain/path of fallback keys. This way, we always need 2 OTS keys and nothing more. One of them is used to sign the actual message (transaction). The other is the fallback key that will sign a new set of 2 OTS keys and so on…

And what if for any reason I need to sign thousands of times?
Here is the magic behind BPQS, “if you signed in the past and it has been recorded in the blockchain, just provide a link to the block that contains your authentication path”.

Due to above trick, each signature remains very short as previous paths are delegated to existing blocks (which are already verified — so no extra computations). Permissioned blockchains, like Corda, can benefit a lot from the BPQS approach, because notaries and oracles need to sign multiple times with their legal identity keys. If post-quantum security is a requirement, BPQS should definitely be considered.

We will keep you updated for any news related to BPQS and I am pretty sure you will hear again from our research team in the next few months, as the hype of BPQS and its potential extensions for use in IoT and Zero Knowledge Proofs seem very very very promising.