Post Quantum Cryptography refers to developing secure algorithms based on the assumption that the adversary has access to a powerful Quantum Computer. Quantum computers can be useful to break well-establishment Crypto Algorithms that are safe against classical attacks. PQC algorithms aim to ensure safety against a ‘Quantum Attack.’ Many scientists believe the remaining challenge in a powerful enough Quantum Computer is only a significant engineering challenge and overcome in the next 10 to 20 years. A good vulnerability management tool can solve these problems. When a Quantum Computer is available, it will wreak havoc on our secure network infrastructure. Threats will not cause problems if you have a good vulnerability management software.
Currently used Post Quantum Cryptographic algorithms (for example, RSA 2048 bit key) can, in principle, be broke by classical algorithms using classical computers– but they would take far too long to be of any consequence. However, Peter Shor developed an algorithm in 1994 (Shor, P.W. (1994). “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134. S2CID?15291489 ) that would break RSA-like algorithms in a matter of seconds. Fortunately, no Quantum Computer is available today to execute Post Quantum Cryptography. But this is a huge worry.
There are two approaches that have received significant attention from the scientific community. One of them is Quantum Key Distribution (QKD), and the other is PQC. QKD algorithms use the basic principles of Quantum Physics and affect the exchange of symmetric keys between two parties. Symmetric key encryption is known to be immune to Quantum speed up. In other words, Symmetric key encryption, like AES, is immune to Quantum Attacks. Furthermore, QKD infrastructure can also be used for detecting an ongoing attack. The downside of QKD is the cost and the infrastructure needed.
PQC is an alternate approach purely based on mathematical algorithms and hence easier to implement. Typical algorithmic solutions to this problem should be able to provide the assurance that they are resilient to Quantum Attacks. They invariably depend on the one-way hardness of a mathematical algorithm. Any such algorithm is only secure till a new technique threatens the safety of this algorithm. In fact, such is the case with RSA-like mechanisms. RSA was safe when research in Quantum Computing was in its infancy and was limited to laboratory experiments. But Quantum Computing is now looming large as a real possibility. What can be worse is a mathematical technique that can invalidate the underlying assumptions on which such encryption mechanisms are present.
Given that a hardware-only solution is not the only viable solution, NIST announced the beginning of the process for a replacement to RSA that would be Quantum Attack resilient in 2017 (https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/Call-for-Proposals )
This process was initiated keeping in mind two points. The first of these was that significant progress was made in the theoretical aspects of quantum computing and its experimental implementations. Secondly, replacing such a widely used algorithm would take time and effort to replace and should be available before Quantum Computers are ubiquitously available.
Quoting from the NIST website, “It is the intention that the new public-key cryptography standards will specify one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are available worldwide, and are capable of protecting sensitive government information well into the foreseeable future, including after the advent of quantum computers.” (https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization )
Detail specifications and the process are also available in the submission requirements and evaluation criteria for the Post Quantum Cryptography (https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf ).
The process of finding a new algorithm included extensive public scrutiny. After six years and four rounds of competition, NIST announced 4 successful algorithms (https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 ) :
- CRYSTALS Kyber (https://pq-crystals.org/ ) – Kyber is a key encapsulation module (KEM) whose security is based on the hardness of solving the learning with errors problem over module lattices.
- CRYSTALS Dilithium (https://pq-crystals.org/ ) – Crystals Dilithium is a lattice-based signature algorithm that uses the hardness of finding short distances in lattices. (https://eprint.iacr.org/2017/633.pdf)
- FALCON (https://falcon-sign.info/ ) – The underlying hard problem is the short integer solution problem (SIS) over NTRU (N-th degree Truncate polynomial Ring Units) lattices, for which no efficient solving algorithm is present for the general case, even with the help of quantum computers. (https://falcon-sign.info/ )
- SPHICS+ (https://sphincs.org/ ) – SPHINCS+ is a hash-based digital signature scheme. Hash-based signature schemes come with well-understood security guarantees. In addition, SPHINCS+ is stateless. SPINCS+ is lightweight and can implement in resource-constrained environments.
The process of finalizing the contenders involved algorithms that made it to the final round. But due to public scrutiny, attacks ( https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/ )compromising these algorithms in a short time with ordinary computing resources. This underlines the long-held tenet in the cryptography community that the strength of encryption should depend on the key and not on the secrecy of the algorithm. Making the algorithm public provides an opportunity for testing the true strength of the algorithm.
In closing, it is important to point out that the future of Quantum Computing is completely uncharted. While there is a lot of excitement about what Quantum Computers can do, it is important to ensure that protocols are not under threat. The most dependable security against a Quantum Attack remains the protocol that uses the power of Quantum Mechanics, namely, Quantum Key Distribution.