Quantum Computing: The Demise of Traditional Cryptography
In today’s digital world, our secrets and data stay safe thanks to powerful codes that take supercomputers millions of years to crack. But there’s a new kind of computer on the horizon — quantum computers. These super-fast machines could break those codes much quicker than we ever thought possible. Imagine your secret messages being unlocked not in millions of years, but in just a blink of an eye. That’s the threat we face with quantum computing, and it’s something we need to figure out how to deal with, fast.
Quantum Computing in a nutshell
Quantum computing is a new kind of computing that uses quantum bits, or qubits, which can exist in multiple states at once thanks to a property called superposition. Unlike classical computers, which use bits that are either 0 or 1, qubits can be 0, 1, or both simultaneously. Therefore, with n qubits, the quantum system can represent and process 2^n different states simultaneously. This exponential scaling is what allows quantum computers to handle a massive amount of information and perform computations at an unprecedented speed for certain types of problems.
However, running a traditional algorithm designed for classical computers on a supercomputer doesn’t automatically make it faster. There are quantum-algorithms specifically designed to harness the ability of quantum computers.
Quantum Computing vs Traditional Encryption
Asymmetric Cryptography
The power of RSA algorithm relies on the complexity of factoring large numbers, making it hard for traditional computers to reverse-engineer the encryption key from the public key.
But compared to conventional supercomputers, the Shor’s Factoring technique factors large prime numbers exponentially faster by combining Euclid’s technique with the Quantum Fourier Transform [1]. Researchers [2] have shown that RSA2048 may be broken in 8 hours by a quantum computer with 20 million Qbits, whereas a conventional supercomputer would take millions of years to solve.
The Shor’s algorithm also can be used to break algorithms such as DH, DSA, ECDH and ECDSA which are based on discrete logarithms.
Hashing and Symmetric Encryption
The power of hashing algorithms comes with one-way functions where it is impossible to reverse the process and retrieve the original input from the output hash.
Since symmetric encryption algorithms use the same private key for encryption and decryption, the only way to decrypt the message without the key is through a brute force attack, attempting various key combinations until the correct one is found.
Grover’s technique [3] can theoretically use a brute-force approach to find the AES-128 key with only 2⁶⁴ executions, when the classical brute-force would need 2¹²⁷ attempts to reverse the hash function. However, Grover’s algorithm does not parallelise well [4], therefore abillion quantum computers that could execute a billion noiseless quantum gates per second, would still take 500 years to crack it.
The threat of Store Now — Decrypt Later
While these algorithms can theoretically be solved by a quantum computer, creating a quantum computer powerful enough to accomplish this task is years away.
However, hackers can keep encrypted data now and decrypt it later when quantum computers get strong enough, even if they are currently unable to decrypt using conventional algorithms.
In order to protect the integrity of stored data and ensure that it is secure against upcoming quantum-based decryption attempts, it is vital that encryption standards be strengthened proactively.
Before It’s Too Late
On December 2022, President Biden signed the Quantum Computing Cybersecurity Preparedness Act, calling agencies should begin moving toward implementing the NIST-approved cryptographic algorithms. Notably, The National Security Agency (NSA) [5], and European Telecommunications Standards Institute (ETSI) [6] has given recommendations to face the issue.
Moreover, there’s ongoing research in quantum-resistant algorithms, and tech companies like AWS [7], Microsoft [8], and Google [9] are also actively engaged in quantum-resistant research.
Quantum-Resistant Cryptography
The US Department of Commerce’s National Institute of Standards and Technology (NIST) has chosen four encryption algorithms for its post-quantum cryptographic standard [10].
For general encryption
- CRYSTALS-Kyber (FIPS 203)
For digital signatures
- CRYSTALS-Dilithium (FIPS 204)
- FALCON (No Draft Standard Released Yet)
- SPHINCS+ (FIPS 205)
Additionally, projects like Open Quantum Safe (OQS) [11] have started implementing Quantum-resistant cryptographic algorithms aiming to fortify our digital defences against the future threats posed by quantum computing.
Conclusion
In the face of quantum computing’s imminent arrival, fortifying our encryption is urgent. Initiatives like the Quantum Computing Cybersecurity Preparedness Act and projects such as Open Quantum Safe pave the way for stronger defenses. Proactive measures now will secure our data against quantum threats, ensuring a safer digital future.
References
[1] Yan, Bao, et al. “Factoring integers with sublinear resources on a superconducting quantum processor.” arXiv preprint arXiv:2212.12372 (2022).
[2] Gidney, Craig, and Martin Ekerå. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5 (2021): 433.
[3] Grassl, Markus, et al. “Applying Grover’s algorithm to AES: quantum resource estimates.” International Workshop on Post-Quantum Cryptography. Cham: Springer International Publishing, 2016.
[4] Zalka, Christof. “Grover’s quantum searching algorithm is optimal.” Physical Review A 60.4 (1999): 2746.
[6] https://www.etsi.org/technologies/quantum-safe-cryptography
[7] https://aws.amazon.com/security/post-quantum-cryptography/
[8] https://www.microsoft.com/en-us/research/project/post-quantum-cryptography/
