Post Quantum Cryptography: What has been done so far?
This article is an introductory article and gives a birds-eye view of cryptography, quantum computers, quantum-resistant algorithms, and why the information security community should care about post-quantum cryptography?
What is cryptography?
Cryptography is an essential component of present-day computer sciences as it lays the foundation of protocol that has been implemented in securing information across the internet.
To its core, it is a branch of mathematics that allows communication to be made securely. It allows the sender of a message to encrypt the message that can only be read by the intended recipient. In the current digital era cryptography is implemented in writing the encryption for secure communication and there are several techniques and those techniques merge in two main domains:
a. Symmetric Cryptography.
b. Asymmetric Cryptography.
In symmetric cryptography, there is one secret key that has been shared with both message entities and they can encrypt/decrypt the message by using that particular secret key, on the contrary, asymmetric cryptography uses one public and one private key to encrypt and decrypt messages.
Both of the schemes have been deployed in the internet networking system like the symmetric cryptography has been used in SSL certificates using the Advanced Encryption Standards (AES-128, AES 192, AES-256) whereas asymmetric cryptography finds its use cases in blockchain, Public Key Infrastructure (PKI) and digital signatures because of its security.
What is a quantum computer?
Quantum computation uses the phenomenon of quantum mechanics that are Superposition and Entanglement to perform and compute certain processes. It uses the physical properties of quantum physics to store data and perform computation.
How are they different from classical computers?
Quantum computers are fundamentally different from classical computers as they do not use the classical bits system rather they have a different basic memory unit that is a “Qubit”.
What is a qubit?
According to New Scientist:
“Qubits are made using physical systems, such as the spin of an electron or the orientation of a photon. These systems can be in many different arrangements all at once, a property known as quantum superposition. Qubits can also be inextricably linked together using a phenomenon called quantum entanglement. The result is that a series of qubits can represent different things simultaneously.
For instance, eight bits is enough for a classical computer to represent any number between 0 and 255. But eight qubits is enough for a quantum computer to represent every number between 0 and 255 at the same time. A few hundred entangled qubits would be enough to represent more numbers than there are atoms in the universe.”
So if having that much computational power with a smaller set of Qubits can present more numbers than there are atoms in the universe that computational power if goes into the wrong hands can create chaos in the whole internet community. And for that let me introduce to the term:
Post Quantum Cryptography
And Why is it Important?
This term was introduced by the National Institute of Standards and Technology (NIST) a department of the US government responsible for standardizing protocols in various domains of sciences. They introduced the term “Post Quantum Cryptography” after a mathematical prove buzzed the whole information security community.
That prove was an algorithm named “Shor’s Algorithm” and that algorithm if combined with quantum mechanics principles can “mathematically” factorize large numbers and major key encryption schemes like RSA, ECDSA and Diffie-Hellman have their base lying on the large numbers, for example, RSA in its core can only be decrypted if we can factor out two prime numbers (The math in this process is difficult and can be discussed in later articles). And that factorizing the prime numbers has been done theoretically and proved to be correct. The mathematical proof can be seen here.
There was research conducted at MIT that stated in the early years of last decade that it would require billions of Qubits to break Asymmetric Encryption Schemes, but a recent study conducted by Google’s Craig Gidney proved that it would only require 20 million qubits to break the RSA encryption scheme which currently is a massive number but the pace of advancement is swift that theoretically such a system can be seen in the early 2030s.
So a question must be asked here that why should we even bother about the Post Quantum Cryptography as it is still not have achieved a big Qubits number?
The answer is that the internet is a mesh of some very complex technologies and to give an overview about that let's discuss a use case of Fibre Optics that uses photons to transmit data, and their interaction limits the usage of Quantum Key Distribution (QKD)” A proposed solution for Public Key Infrastructure weakness”, based on a single photon’s transmission. After about a few hundred kilometers, the QKD generation rate will drop heavily, or rather the error rate will become substantially indistinguishable from an attacker reading the photon. This implies that, if we need to transmit farther, either we place digital repeaters that could be susceptible to attack, or quantum untrusted repeaters (which do not exist yet); either would make the QKD solution very expensive to implement.
So the buzz about the PQC is to find optimized solutions and design implementation schemes that are cost-effective and can be implemented over the current distribution of classical computers secure data transmission protocols and this leads us to the current researches that are being conducted by some honorable cryptographers among the community.
What has been done so far?
The main research is being conducted under the umbrella of NIST. And, they have finalized the list of Round 3 which can be seen here. Click Me.
And NIST issued a report for what they will be doing in the coming years that states that:
“NIST is taking the following steps to initiate a standardization effort in post-quantum cryptography. NIST plans to specify preliminary evaluation criteria for quantum-resistant public-key cryptography standards. The criteria will include security and performance requirements. The draft criteria will be released for public comments in 2016 and hopefully finalized by the end of the year. At that time NIST will begin accepting proposals for quantum-resistant public-key encryption, digital signature, and key exchange algorithms. NIST intends to select at least one algorithm providing each of these functionalities for standardization. NIST will establish a submission deadline late in 2017 for algorithms to be considered, allowing the proposals to be subject to 3 to 5 years of public scrutiny before they are standardized.
PS: NIST has finalized the list of the participants and the readers can check the theoretical explanation about the upcoming schemes by clicking here.
While this process will have many commonalities with the processes that led to the standardization of AES and SHA3, this is not a competition. NIST sees its role as managing a process of achieving community consensus in a transparent and timely manner. Ideally, several algorithms will emerge as “good choices.” NIST may pick one or more of these for standardization in each category. In this respect, NIST’s process for standardizing quantum-resistant public-key cryptography will be similar to the ongoing block cipher modes development process.
When standards for quantum-resistant public-key cryptography become available, NIST will reassess the imminence of the threat of quantum computers to existing standards and may decide to deprecate or withdraw the affected standards thereafter as a result. Agencies should therefore be prepared to transition away from these algorithms as early as 10 years from now. As the replacements for currently standardized public-key algorithms are not yet ready, a focus on maintaining crypto agility is imperative. Until new quantum-resistant algorithms are standardized, agencies should continue to use the recommended algorithms currently specified in NIST standards.”
On contrary to government sectors there have been great advancements in Quantum Computers real-world application as the Quantum Computer developed by IBM under the IBM Q branch was used in visualizing the strains of COVID-19 and thanks to the IBM they have made their Quantum Computer available for public use on the cloud.
Microsoft also has been researching this area and the recent studies showed that they have developed an “Improved Quantum Circuits for Elliptic Curve Discrete Logarithms”, the most costly component in Shor’s algorithm to compute discrete logarithms in elliptic curve groups.
In 2016, Google conducted an experiment where they implemented a post-quantum key exchange algorithm in addition to an elliptic curve key exchange algorithm.
The ultimate thing is that quantum computers are meant to be taken as the main source of computation in the coming ages and humans are meant to learn from their past learning and the current crypto community is preparing for the coming threats and the researches are being conducted to be future-ready for this technology. The main purpose of this article was to learn and explain the current hurdles and try to understand the solutions and make them understandable for the common community. I hope this little effort can be appreciated and constructive criticism comments are welcomed.