Quantum computers mark a paradigm shift in computing technology. They are able to solve problems (albeit only theoretically at the time of writing), that are deemed infeasible by classical computers. In particular, a large-scale quantum computer can efficiently factor integers and solve other similar problems, such as discrete logarithms, due to Shor’s algorithm. This poses a threat to many existing cryptographic algorithms, as they fundamentally rely on the hardness of these problems. The quantum computers of today are not yet large enough to pose a threat, but someday it may be possible to build large enough quantum computers to break some algorithms.

As with most systems on the internet, the Hedera network relies heavily on cryptography, such as digital signatures for authorizing transactions, hashes for state integrity checks, and TLS channels between nodes on the network.

A particular threat from quantum computers is to public-key cryptosystems (based on classical assumptions) — for instance, the ed25519 digital signature scheme is completely broken if a quantum computer solves the underlying discrete logarithm problem. In contrast, symmetric-key cryptosystems, such as AES block ciphers, do not rely on any such hard problems and are therefore safe from Shor’s algorithm. Nevertheless, due to Grover’s algorithm, any symmetric-key cryptosystem would incur a significant security loss, but this can be mitigated rather easily, for example, by simply doubling the key-length. To that end, Hedera follows the CNSA standard, which is what the US government uses to protect its own Top Secret information. The CNSA standard requires at least 256 bit AES keys (used in our TLS connections) and 384-bit SHA-2 hashes. With these larger key sizes, both AES and SHA-2 are generally considered to be safe from future quantum computers, even if they can be built very large. Hedera’s security does not rely on TLS, but it is likely that TLS key agreement will at some point be upgraded to be post quantum.

This leaves us with finding viable post-quantum alternatives for digital signature schemes. For over a decade now, a large group of researchers has been developing novel public-key cryptosystems, including digital signature schemes, that do not depend on classical assumptions and are widely believed to be secure even against very large quantum computers. Several standardization bodies have been drafting standards for various post-quantum cryptographic algorithms. Among them, the most prominent contest is being run by NIST. In the past, NIST successfully executed several such competitions to standardize hash functions (SHA), encryption scheme (AES) etc., and those algorithms are now considered to be the primary standards for enterprise-grade cryptography.

The NIST post-quantum cryptography competition commenced in 2017, with the first round of submissions, among them around 70 algorithms were shortlisted in the first standardization workshop (attended by Pratyay Mukherjee, cryptography researcher at Swirlds Labs). After several rounds of screenings, NIST has recently announced, on July 5, 2022, four candidate algorithms: CRYSTALS-Kyber for public-key encryption / key encapsulation and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures. NIST will refine these over the next two years, until it has finished the final standard. During those two years, they encourage researchers to explore those algorithms, but not to implement them in production yet, because they may still change before the standard is finalized. This two-year horizon is considered to be very short compared to when the first large-scale quantum computers are likely to be built that pose a threat to the current CNSA algorithms. So progress is continuing at a very good pace.

We are genuinely excited about this development and appreciate the rigorous effort by NIST and all the contributors. Now, given the nature of this competition, it is all but over at this point. Arguably with the exception of the Sphincs signature scheme, the cryptographic security of the announced winners are based on complex mathematical hard problems which are (relatively) less understood than more traditional hard problems such as factoring or discrete logarithms. In fact, the final round candidates were chosen to diversify the pool of hard problems, and many of them suffered fatal attacks. It may not be a complete surprise if improved cryptanalysis discovers attacks to these chosen algorithms.

This announcement is a milestone for the cryptographic community. Over the next two years, the algorithms and their parameters will be refined until they are ready to be used in practice. The Falcon signature algorithm is particularly interesting, and it will be interesting to watch the ongoing research into both possible attacks on it, and possible ways to make the signatures smaller. Hedera will watch these developments with great interest, and may implement one of these signature algorithms when the standard is completed.