From Post-Quantum Cryptography to Post-Quantum Blockchains and Cryptocurrencies: an Introduction

Dated back to over 2,000 years ago, in our civilization, we already applied symmetric key cryptography for securing our messages in transit or at rest, for example, Caser’s cipher, simple substitution, and so on. In symmetric key cryptography, the same secret key sk has to be agreed in advance for both encryption and decryption. Despite more sophisticated symmetric key cryptosystems have been invented and got involved in some significant historical events, for example, Engima, the principle underlying the symmetric key cryptography has never been changed significantly. Block ciphers nowadays, for example, AES, dominate the symmetric key cryptography arena with just tens of bytes of randomly generated sk and a few dozen rounds of diffusion and confusion-based transformations, are not just efficient for both hardware and software implementations, but are also secure enough for almost all kinds of purposes both commercially and militarily.

Public Key Cryptography

Public key cryptography was invented in the 70s of last century. It has been revolutionary as for the first time in the history of mankind, we no longer need to rely on one single sk for both encryption and decryption. Instead, there are two keys pk and sk for encryption and decryption, respectively, of which, the encryption key pk can be publicly known, and is computationally infeasible to derive the corresponding decryption key sk. This significantly helps on provisioning the key exchange and key management between a sender and a receiver. The sender can obtain a publicly known pk, encrypt a message under pk, and send the generated ciphertext to the receiver, while the receiver can recover the original message from the ciphertext through decryption using a secret sk, which does not need to share with anybody including the sender. Compared with the conventional symmetric key cryptography, public key cryptography can be used effectively to exchange symmetric keys, and symmetric key cryptography is then used for efficiently securing the actual bulk data. Historically, the combined applications of both public key cryptography and symmetric key cryptography conjure up some terminologies such as hybrid encryption, Key Encapsulation Mechanism (KEM) and Data Encryption Mechanism (DEM).

If we look back into the public domain of research work in public key cryptography, some of the works that we would not miss. For example, the 1976 seminal paper on public key cryptography and key exchange over insecure channel by Diffie and Hellman, followed by 1977 RSA encryption and signature by Rivest, Shamir and Adleman, and further followed by Goldwasser and Micali’s rigorous definition of security in 1982 that had evolved into the well-known indistinguishability models against chosen plaintext attack (CPA), chosen ciphertext attack (CCA), and many more, and in particular, the introduction to provable security paradigm. In the context of blockchains and cryptocurrencies, we cannot stress more on the great contribution to public key cryptography by Koblitz and Miller in 1985 for their introduction to Elliptic Curve Cryptography (ECC), and many other devoted cryptographers who have devoted their entire life to the advancement of cryptology.

Quantum Computing

Quantum computing is based on quantum-mechanical phenomena, such as superposition and entanglement, and is different from binary digital electronic computers which are based on transistors. The work was initiated by several mathematicians and physicists such as Paul Benioff (1980), Yuri Manin (1980), Richard Feynman (1982), and David Deutsch (1985). With decades of researches, the development of quantum computing has been challenging yet groundbreaking. On hardware, it has recently been reported that Intel has successfully fabricated a 49-qubit chip where qubit stands for quantum bits, IBM has been working on a 50-qubit quantum machine, and Google has also recently shared some information about their work on a 72-qubit machine. There are a lot of discussions about the future development of quantum computing, and much of the attention has been drawn towards the question on how many qubits and when such a quantum computer can be built. An interesting question is whether Moore’s Law still applies to the quantum computing world despite we are not counting the density of transistors on a wafer here anymore. As a quick but blunt prediction here, the optimists, including many mathematicians and physicists, would say 5 to 10 years or at most 20 to 30 years before we are being able to build some large scale quantum computers, and very likely, the first set of such large-scale quantum machines will be put together by some major IT powerhouses, research institutions or national laboratories. We should also take note on the comments and views of some less optimistic scholars who do not think that in a foreseeable future that we can get close to building an affordable and capable quantum computer, which can disrupt today’s world of public key cryptography in practice.

On the quantum algorithmic development, there are two groundbreaking algorithms which have laid out a strong foundation towards breaking today’s number theoretic based public key cryptosystems. In 1994, Shor proposed a polynomial-time (efficient) algorithm for solving integer factorization and discrete logarithm problems. The algorithm relies on the existence of quantum computers, and hence this type of algorithms is called quantum algorithms in this article. Shor’s quantum algorithm and its variants can be used for breaking most of the currently used public key cryptosystems including those based on ECC, which is generally used in Blockchain systems and cryptocurrencies. In 1996, Grover proposed an O(√N)-time quantum algorithm for functions with N-bit domains. This quantum algorithm once realized on quantum computers can be used for breaking symmetric key cryptosystems, and to defend against attacks based on Grover’s algorithm, we need to double the key sizes in order to achieve the similar level of security against conventional computers. For example, for 128-bit symmetric key security, we need to use symmetric key cryptosystems which are originally designed for achieving 256-bit security against attacks based on Grover’s quantum algorithm.

Post-quantum Cryptography

Post-quantum cryptography is about devising cryptographic algorithms that are thought to be secure in the quantum era with security against both classical / conventional and quantum computers. To build a post-quantum cryptosystem, there are several major directions that researchers are pursuing.

1. Hash-based cryptography focuses on designing digital signature schemes based on the security of cryptographic hash functions, e.g. SHA-3.

2. Multivariate-based cryptography has its security relies on the hardness of solving multivariate systems of equations.

3. Code-based cryptography has its security relies on the hardness of problems from coding theory, for example, Syndrome Decoding (SD) and Learning Parity with Noise (LPN).

4. Lattice-based cryptography seems to be one of the most active directions in recent years due to several key reasons. First, it has strong security guarantees from some well-known lattice problems, for example, finding short vectors in high-dimensional lattices. Second, it enables powerful cryptographic primitives, for example, fully homomorphic encryption (FHE) and functional encryption. Third, some new lattice-based cryptographic schemes have become quite practical recently, for example, the key exchange protocol NewHope, and a signature scheme BLISS, to name a few.

In August 2015, the U.S. National Security Agency (NSA) announced that it plans to replace Suite B with a new cipher suite due to concerns about quantum computing attacks on ECC. Then in recent years, the National Institute of Standards and Technology (NIST) has been actively leading and coordinating the standardization effort of post-quantum cryptographic schemes. In late 2016, NIST opened a call for proposals, and the Institute nicely put the following background statement, quote

In recent years, there has been a substantial amount of research on quantum computers — machines that exploit quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere. The goal of post-quantum cryptography (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks.

At the end of 2017, NIST received 82 proposals and 69 of them entered the first round. Among these 69 proposals, there are 27 lattice-based schemes, 22 code-based, 10 multivariate-based, 2 hash-based, and 8 other-based. In January 2019, 26 were further shortlisted to enter the second round of the standardization process. Among them, there are 12 lattice-based schemes, 7 code-based, 4 multivariate-based, 1 hash-based, and 2 other-based. It is expected to have the first set of standards by 2025, and there will be standardized schemes for public key encryption (PKE) or KEM, and digital signature.

Post-quantum Blockchains and Cryptocurrencies

Blockchain is a distributed ledger for storing data amongst multiple parties. Data on ledger can be replicated and distributed for higher reliability, they can be time-stamped, the longer some data stored on the ledger the harder they are to tamper with, and it is difficult to make changes on the data, giving Blockchain the property of immutability. In order to achieve time-stamping and immutability in particular, cryptographic hash functions and digital signature schemes are employed in Blockchain.

On a public Blockchain ledger, for example, Bitcoin, any modifications of the data on the ledger should easily be detected, and all information about transactions should be shared by all parties. Conceptually, there is a `chain’ of hashes for ordering the sequence of transactions. For example, suppose there are three transactions T1, T2 and T3, and T1 occurred the first, then T2 and finally T3. On the public ledger, the following are stored in pairs, where Hash denotes a cryptographic hash function.

In Bitcoin, double SHA-256 is used as the underlying cryptographic hash function. Besides ordering or time-stamping using cryptographic hash functions, the sender who initiates a transaction also generates a digital signature using the sender’s private key sk on both the transaction and the hash value for ensuring the immutability of the transaction and the ordering.

In a nutshell, the basic security of Blockchain is ensured by the applications of cryptographic hash functions and digital signatures. They are used for `chaining’ blocks (in the traditional notion of Blockchain), the validation of transactions, consensus algorithms (e.g. proof-of-work), and the initiation and broadcasting of transactions. As Blockchain continues to evolve, there are other features introduced in the community, for example, recipient hiding, privacy coins, secret sharing, etc. Some of these features rely on some additional cryptographic primitives for ensuring their security. These cryptographic primitives include commitment schemes, ring signatures/group signatures, verifiable encryption, zero-knowledge proofs, and so on.

Privacy in Blockchain. Data privacy will be one of the major challenges in the near-future Blockchain applications, in both permissioned and permissionless cases. There are several cryptographic tools for privacy preserving. Fully Homomorphic Encryption (FHE), which is an in-principle universal solution to any privacy problem, is yet to be practical for the foreseeable future. Secure Multiparty Computation (MPC) gives answers to both privacy and verifiability of distributed computing, but general solutions in MPC are still quite inefficient in terms of both computation and communication complexities as of this writing. Functional Encryption (FE) enforces access control and data sharing based on expressive functional policies, but in its present form, there is no compelling use case in practice yet. Searchable Encryption (SE) allows an untrusted server to search a user’s data without learning the contents of the data or the search query. There have been some promising developments lately in terms of both theoretical researches and actual implementations. One of the main challenges in SE is on devising a more practical / efficient scheme for large datasets with its security being proven under a well-studied formal security model.

Abelian — Post-quantum Privacy Coin with Accountability

Abelian Coin is a new cryptocurrency platform. It is designed to achieve quantum resistant with three levels of privacy, and optionally, support accountability. The project is a joint work of CryptoBLK and cryptographers from Nanyang Technological University, Shanghai Jiao Tong University, and the University of Wollongong. As a quick review of some major cryptocurrencies, we know that Bitcoin can be considered as a `pseudonym’ system from the privacy perspective. Wallet addresses in the Bitcoin system are independent from the personal information of the wallet holders, while the privacy level is pretty basic because all the transactions on the Bitcoin system are recorded on a public ledger, and the transactions are traceable. From any single Bitcoin full node, one can obtain the complete view of all the transactions and the links between them. A graph can be built for illustration with all the wallet addresses as nodes and transactions as edges. Through graph analytics and information obtained from other sources on the Internet, it is feasible for us to identify the actual wallet holders behind their pseudonyms, and their transactions will become traceable.

Dash is a privacy coin which improves the privacy protection when compared with that of Bitcoin through the privacy-centric masternodes, which weaken the traceability by applying the mixing technique. CryptoNote goes one step further to weaken the traceability and linkability by hiding (1) the identity of the originator using ring signature, and (2) the identity of the recipient using a technique based on the well-known Diffie-Hellman key exchange protocol. Zerocoin is another privacy coin which breaks the link between individual transactions, and Monero combines techniques from Dash and CryptoNote for hiding the amount of each transaction while at the same time applying zero-knowledge range proof for ensuring that the originator is not over-spending while the actual amount in the transaction can remain hidden. Another major privacy coin available in the cryptocurrency market is Zerocash, which breaks the links between transactions, hides the identities of users, and also covers up each transaction amount through applying the zero-knowledge SNARKs. In contrast to the basic privacy that Bitcoin provides, we refer to the privacy level of Monero and Zerocash as full privacy due to its dual capabilities of keeping the originator and the recipient of each transaction anonymous and at the same time hiding the amount in each transaction.

Abelian Coin (ABE) is a quantum-safe privacy coin and by design, it is a collection of lattice-based cryptographic constructions. There are three levels of privacy supported with an optional accountability feature. Users of ABE can choose the privacy level for each of their transactions. The basic privacy level is comparable to that of Bitcoin, namely, the pseudonyms are public on the ledger and the transaction amounts are also public. The pseudonyms as wallet addresses can be one-time but the transactions are linkable. The full privacy level is comparable to that of Monero or Zerocash. It is infeasible to compromise the unlinkability of coin addresses and the transaction amounts are hidden. There is one more privacy level in between the basic and full privacy levels. We call this level as the Privacy with Accountability. If a user of ABE chooses this privacy level for a transaction, the user also needs to pick a designated authority so that this designated authority, identified by the authority’s unique public key pk, can link this transaction with the immediately previous transaction as well as crack open the actual transaction amount. While to other participants, this transaction can still achieve the full privacy level, namely the transaction will remain anonymous and untraceable to the public with the amount hidden, while to the designated authority chosen by the originator of the transaction, the authority is able to link the transaction with the previous one and reveal the transaction amount.

The security of the cryptographic primitives used in ABE is based on the intractability of several lattice-based hard problems and detailed security models can be found at the ABE whitepaper published in May 2018. These hard problems are Short Integer Solution (SIS) and Learning With Errors (LWE). Let

and

The SIS problem states that given uniformly random

find

such that

The Learning With Errors (LWE) problem states that given uniformly random

and small

distinguish (A, As + e) from a uniformly random pair. Module-SIS and -LWE enjoy high security guarantees, namely there exists some well-proven reduction from the worst-case to the average-case. The research community has also shown continuous optimization and improvements on the efficiency and practicality of cryptographic schemes based on these lattice-based hard problems.

To enable anonymous payments, ABE employs a mechanism similar to CryptoNote. It is an interactive protocol between sender and receiver, allowing the latter to derive a random-looking one-time key pair for a signature scheme. The mechanism can be realized from lattices, via key exchange Kyber and signature scheme Dilithium, one of the prominent submissions to the NIST. The security of these schemes is based on Module-LWE and Module-SIS, respectively. Here is the high-level idea.

1. The receiver possesses a long-term Dilithium key-pair:

2. Both parties run Kyber to jointly generate

Sender, knowing

computes and publishes

which looks random.

3. Only the intended receiver can recognize t, and can compute the corresponding

Note that

Hence, the receiver obtains a one-time Dilithium key pair, which can be used for later transactions by the receiver.

In addition to generating a random-looking one-time key pair for signature that can be used by the receiver for later transactions, hence, to break the link between transactions, ABE also applies the additively homomorphic commitment scheme with a companion zero-knowledge proof, which can be used to securely send coins to multiple wallets while ensuring that there is no over-spending. By additively homomorphic commitment, we mean

In the process, one divides a commitment to

into commitments to

and proves in zero-knowledge that this is done honestly. In this way, the transaction amount can also be hidden while overspending can be prevented.

If we apply the commitment scheme and its companion zero-knowledge proofs by del Pino, et al. (CCS’17) and Baum, et al. (SCN’18), respectively, the commitment size will be around 8KB and the zero-knowledge proof size will be around 7.5KB, and the security will be based on Module-LWE and Module-SIS, respectively.

To prevent users from cheating, for example, by working with negative amounts and sending a larger number of coins than they actually have, ABE relies on zero-knowledge range proofs. For instance, to prove in zero-knowledge that integer m committed in c = Com(m;r) belongs to the range

we can apply some lattice-based techniques such as Libert-Ling-Nguyen-Wang (CRYPTO’18). The range proof size is in the order of a few hundreds of KB, but proving that m was committed in c is costly (> 2MB). We can also apply the OR-proofs, for example, the scheme due to del Pino, et al. (CCS’17), where proving that m was committed in c is practical, and the range proof will contain 64 OR-proofs for each bit of m, and the size would be over 1MB.

Ring signatures, first proposed by Rivest, Shamir and Tauman (AC’01) allows a user to sign on messages anonymously with a central authority. Linkable ring signature introduced by Liu, Wei and Wong (ACISP’04) further requires that if the same user generates two signatures on the same message, then the user can be identified with the anonymity of both signatures being compromised. A linkable ring signature can be generically derived from an ordinary ring signature. Some potential technical approaches for building such a lattice-based ring signature scheme for ABE include

· Merkle trees with zero-knowledge proofs, for example, based on the results of Libert-Ling-Nguyen-Wang (EC’16).

· Commitments and one-out-of-many zero-knowledge proofs, that can be adapted from the discrete-log based construction in Groth-Kohlweiss (EC’15).

· Chameleon hash functions with signatures, for example, the Brakerski-Tauman Kalai ’10, or Raptor ’18, both are available at ePrint.

For achieving accountability, ABE formalizes an approach based on verifiable encryption. The user encrypts some crucial information, such as the values of consumed coins, the identity of sender or receiver, under an authority’s pk, and proves in zero-knowledge that he honestly does so, that is, the ciphertext is well-formed. Should the need arises, the authority can use his secret decryption key to recover the encryption information. The first suite of lattice-based verifiable encryption schemes was given by Ling-Nguyen-Wang (PKC’15) with the zero-knowledge proof size great than 5MB. A recent work by Lyubashevsky-Neven (EC’17) made both the ciphertext size and proof size be less than 10KB.

Closing Thoughts

As we have seen above, there are quite a number of approaches which can be taken for building an efficient and quantum-safe privacy coin as ABE is pursuing. One of the key contributions in particular from ABE is that it is pursuing a practical and scalable solution and at the same time, ensuring that the scheme is supported by rigorous proofs of post-quantum security with models for provable security. For details, please refer to the whitepaper at abelianfoundation.org.

Acknowledgements: the author would like to particularly thank Prof. Huaxiong Wang and Dr. Khoa Nguyen as part of this article is inspired by Prof. Wang’s recent talk at Inscrypt 2018.