What is a Quantum computer?
Computing is pervasive in modern life, but did you know there’s an entirely new category of computer, called Quantum computers, that are being actively developed by some of the world's leading computer scientists at places like Google and IBM?
Quantum computers differ from classical computers in that they utilize Quantum Mechanics (exotic Physics) in order to achieve an exponential leap in processing power, by exploiting “Quantum parallelism”.
How does Quantum Computing challenge cryptography?
Thanks to Quantum parallelism, Quantum computers may efficiently solve the mathematical problems we currently use to provide us with cryptographic security. More specifically, modern cryptographic algorithms rely on assumptions that certain mathematical problems are simply too hard for a classical computer to solve in a reasonable amount of time. Mathematical problems such as factoring large numbers, or solving a discrete logarithm.
Quickly solving these types of problems is what Quantum computers do best! So, they pose an existential threat to many of the current cryptographic standards in general and to blockchain in particular. Although exactly when the Quantum advent will occur is a topic of much debate, we need to act now in order to be prepared to deal with this emergent threat.
Falcon to the rescue!
To counter the emergence of Quantum computers, NIST (the US Institute of Standards and Technology) ran a global competition to entice the brightest minds in the field to develop cryptographic algorithms that are secure against Quantum attacks.
The competition was fierce. Over 50 different algorithms were entered as candidates by cryptographers and scientists around the world. After nearly 6 years of rigorous cryptanalysis, inspection and testing, a handful of algorithms were selected as winners of this competition, and were announced recently, meaning we finally have cryptographic standards which should be Quantum secure!
Before the NIST announcement, Algorand had already selected Falcon as its choice to provide Quantum security to the Algorand blockchain. Indeed, the Algorand team had previously played a pioneering role in the technological history that led to Falcon and felt confident in its strength.
Falcon’s characteristics
As one might expect, the process of designing and implementing a cryptographic algorithm is highly technical work, and it becomes even more challenging when building an algorithm that needs to be Quantum secure! Characteristics that one may take for granted with classical cryptographic algorithms are sometimes an order of magnitude more difficult to achieve in a Quantum context! This forces typical Quantum-secure schemes to trade efficiency for security. Not an easy choice!
Ideally, a Quantum secure algorithm should enjoy characteristics such as:
- Having a small key and signature size, whilst still remaining secure
- Being fast enough for classical computers to both use and verify, even on a phone!
- Being flexible so that an algorithm enjoys longevity
These are the very characteristics enjoyed by Falcon, and, are in fact, the reasons which Falcon emerged victorious in the NIST competition.
Falcon’s history
Falcon is a technological work of art designed by Fouque et. al. As its designers state, their solution is based on Trapdoors for Hard Lattices and New Cryptographic Constructions, the pioneering work of (GPV) Gentry (prior member of the Algorand Foundation), Peikert (head of cryptography at Algorand Inc) and Vaikuntanathan (MIT and Scientific Advisor to Algorand Inc).
With lattice-based signatures, every message has many possible valid signatures, and a signing algorithm must ultimately choose only one of them. Unfortunately, the methods used by prior proposals 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 uses, is a rigorous method of selecting a valid signature in a way that reveals no information about the secret signing key. Using this method, one can safely sign a huge number of messages. Moreover, GPV showed that it’s 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!
Falcon’s use within Algorand
Every blockchain would benefit from a quantum-safe digital signature scheme, and we are proud to have it on our blockchain. In addition, Algorand will use Falcon signatures in a variety of applications. In particular, they underlie State Proofs, the latest technological achievement of the Algorand blockchain.
State Proofs enable the Algorand blockchain to interoperate in a decentralized way with other blockchains, and prevent Quantum computers, whenever they may emerge, from retroactively forking the chain.
