Post-quantum cryptography (PQC)

Post-quantum cryptography (PQC) is an active area of research that advances the use of quantum-resistant primitives in cryptographic algorithms. Its goal is to secure our digital infrastructure against both classical and quantum algorithms. An important consideration for PQC is interoperability with existing technologies so that digital infrastructure can be updated for the next wave of cryptographic standards. That is, the PQC can be executed on the modern computer, laptop, or smartphone, and the security of the PQC resists the adversary who has large-scale quantum computers.

NIST PQC competition

Post-quantum cryptography is a vital part of the response to the imminent threat of quantum computers such that in 2016 the National Institute of Standards and Technology (NIST) initiated a process to standardize a set of quantum-resistant public-key cryptographic algorithms, recognizing that current NIST approved algorithms are vulnerable to attacks from large-scale quantum computers. Since 2016, there have been 3 rounds of PQC competition, where each of them screened out the candidate algorithms for the International PQC Standards.

The First International PQC Standards

In July 2022, NIST officially announced the standardized algorithms from Round 3 of the NIST PQC competition. This is a landmark milestone as government agencies and businesses have been waiting nearly 6 years for a clear direction as to which algorithms are trustworthy. There are 3 standardized algorithms for digital signatures:

• CRYSTALS-DILITHIUM - A lattice based algorithm that is strongly secure based on the hardness of lattice problems over module lattices.
• FALCON - A lattice based algorithm based on the hard problem of short integer solutions over NTRU lattices, resulting in short signatures and fast implementations.
• SPHINCS+ - A hash based algorithm that is improved from SPHINCS signature scheme. As a simple and robust method, it has well-understood security and minimal assumptions.

Problems for blockchains transitioning to PQC

Upgrading blockchain security isn't as simple as dropping-in a PQC algorithm as a replacement for current algorithms. PQC algorithms are much more expensive than their classical counterparts in terms of size. This is particularly problematic for blockchains where each full node keeps an entire record of all activities on the blockchain. If Bitcoin and Ethereum were to adopt the newly standardized PQC algorithms today, the size of both chains would explode. Even with the most space-efficient NIST PQC signature algorithm, public-keys and digital signatures would consume 21.2x and 24.3x more space in Bitcoin and Ethereum, with the size of their respective ledgers increasing by 2.2x and 2.22x. Other NIST PQC algorithms have even worse tradeoffs between signature/ledger sizes and security. These performance issues have widespread implications, affecting transaction speed, gas prices and the decentralization of the entire network.