Leading on post-quantum technology 

The threat of quantum computing

A quantum computers is a new type of computer that is able to tackle certain classes of problems (such as integer factorization and the discrete log problem) in novel, more efficient ways than classical computers. A regular computer uses bits, like tiny switches with binary states that are either on (1) or off (0), to process information. Quantum computers use qubits, which can be in a superposition of the two basis states: on, off, or some probability of both (such as 30%/70% or 51%/49%).

The threat is that quantum computers, once they have enough error-correcting qubits and sufficient processing power, will be able to crack the commonly used encryption and digital signature schemes that protect sensitive information (passwords, credit card details, private communication, etc.) and allow us to prove our identities online. Google has been experimenting with post-quantum security since 2016 and Apple announced its PQ3 cryptographic security upgrade to iMessage in February 2024.

More specifically, quantum computing poses a threat to asymmetric cryptography used in blockchains, particularly in the areas of key agreement and signature schemes. The security of these schemes relies on certain mathematical problems that are simply too hard for a classical computer to solve in a reasonable amount of time. For example, elliptic-curve cryptography (ECC), which underpins most blockchains, relies on the difficulty of solving the discrete log problem. Unfortunately, quickly solving these types of problems is what quantum computers do best. 

Using a technique called Shor’s algorithm, a quantum computer could break cryptographic algorithms, potentially compromising the integrity of the blockchain, and leading to disrupted transactions and the derivation of private keys from their public key counterparts—on a massive scale. For this reason, the development and implementation of post-quantum cryptography (PQC) is crucial for safeguarding blockchains. 

What is post-quantum readiness?

Post-quantum readiness refers to a blockchain's ability to withstand the security threats posed by future advancements in quantum computing. A blockchain may be considered "quantum ready" if it can mitigate quantum attacks. It requires a post-quantum secure signature scheme and a post-quantum consensus mechanism. Crucially, existing blockchains will need to transition from classical security to post-quantum security. This process must also ensure the security of the entire chain's history, even the portion recorded before the upgrade, to prevent tampering with the past.

Algorand’s path to post-quantum readiness

Algorand’s first step to post-quantum readiness was to secure its history. In 2022, Algorand introduced State Proofs, a post-quantum secure compact certificate that attests to and compresses the ledger's state changes happening every 256 rounds. Algorand State Proofs are signed using FALCON, a post-quantum secure digital signature scheme.

Specifically, a State Proof contains a Merkle tree attesting to the last 256 block headers. It is signed by Algorand node runners composing a supermajority of the stake. Rather than using normal ECC-based signatures, however, they use FALCON signatures. The node runners’ signatures are themselves committed to a Merkle tree using the SumHash512 hash function, a member of the subset-sum compression function family which offers ZK-SNARK friendliness over the SHA-2 family. For more information on State Proofs, please refer to the 2020 paper Compact Certificates of Collective Knowledge by Silvio Micali et al.

Algorand has also integrated an experimental Algorand Virtual Machine (AVM) opcode (a new “CPU” instruction) that will allow the AVM to verify FALCON signatures. (Note: This opcode is not yet live on mainnet.) With FALCON verification being part of the AVM, Algorand is taking a step towards creating accounts that are post-quantum secure.

Algorand already possesses the necessary cryptography tools, namely FALCON, to further quantum-proof the chain. It can support address and signature verifications that rely on Ed25519-based systems alongside FALCON cryptography. This would necessitate a consensus mechanism update and ultimately lead to enhanced security and robustness in the Algorand cryptographic framework.

Algorand’s consensus mechanism relies on the Verified Randomness Function (VRF), introduced by Silvio Micali et al. in 1999. As with other ECC-based primitives, it is vulnerable to quantum computers and will eventually need to be replaced with a post-quantum secure version. The search for viable post-quantum VRF methods is an active area of research that has already produced viable results, such as Zengpeng Li et al’s ZKBoo ZKB++ method and Maxime Buser et al’s XMSS method. When the time comes, Algorand will be able to swap out its current VRF for the most suitable post-quantum VRF, securing consensus from quantum adversaries.

Ultimately, incorporating FALCON into the Algorand framework has laid the groundwork for enhancing the resilience of Algorand's ecosystem against potential quantum threats.

Core characteristics of FALCON

• Compact efficiency: FALCON remains post-quantum secure while possessing relatively small key and signature sizes—meaning there is less data to store and manage, making it compatible with resource-constrained devices, like smartphones and security chips in IoT devices.
• Classical compatibility: While FALCON is designed to be secure against quantum computers, it still needs to remain performant on the classical computers that we use today. This means signing a message with your private key and verifying a signature with a public key should be fast enough for practical use, even on devices with less processing power, like mobile phones.
• Endurance: FALCON can potentially be tweaked or integrated with other algorithms as the cryptography field evolves, ensuring its continued relevance even as new threats or solutions emerge.

Deeper dive into FALCON 

A former Algorand Technologies (FKA Algorand Inc.) cryptography engineer Dr. Zhenfei Zhang, along with fellow collaborators, submitted two proposals to the National Institute of Standards and Technology (NIST) competition to establish new standards for post-quantum cryptography in 2016. These were NTRU, a public key encryption scheme, and FALCON, a digital signature scheme. Out of over 80 submissions from the world's top universities, researchers, and cryptographers, FALCON was ultimately selected as one of the NIST-endorsed digital signature algorithms in 2020. 

FALCON is based on Trapdoors for Hard Lattices and New Cryptographic Constructions, the pioneering group public verification (GPV) work of Craig Gentry (former Algorand Foundation research fellow), Chris Peikert (Head of Cryptography at Algorand Technologies), and Vinod Vaikuntanathan (MIT professor). 

In a GPV scheme and, in this case, lattice-based signatures, every message has many possible valid signatures, and a signing algorithm must ultimately choose only one of them. This proof can then be verified using a public key, without revealing any information about the individual secret keys used to create the original signatures. Traditional methods for choosing a single valid signature from many made it possible to recover the signing key from just a small number of signed messages, even using a classical computer.

The crucial innovation of the GPV work, which FALCON signatures use, is a rigorous method of selecting a valid signature in a way that reveals no information about the secret signing key. Using this method, it’s possible to safely sign a huge number of messages. Moreover, GPV showed that it is not possible to break the signature scheme without solving the lattice problem, which should be hard to solve for all computers, both classical and quantum.