Reading Time: 6 minutes
Category: Post-Quantum Cryptography
And when you look along the way we’ve come, there are spirals of vultures wheeling.
— Bruce Chatwin, The Songlines (2012)
THE NEED FOR SECURITY
Sometimes we need a gentle reminder of harsh realities. Security isn’t a luxury item; security is a basic precondition for survival. At the very basis of the pyramid formed by Maslow’s hierarchy of human needs we find physiological needs; directly layered on top of that, safety needs. Without security there’s nothing safeguarding physiological needs. And if our means of existence are threatened, then so are we. The same holds if there’s nothing keeping us out of harm’s way.
Security is a broad term. It entails availability, certainly. We need food and water. We also need integrity; our water must be potable, our food edible. If there’s nothing to stop them being poisoned, we’re not secure.
Being humans, a planning, scheming, plotting herd animal rather than a solitary hunter, we increase our collective might by cooperating in groups. This involves exchanging signals (communication), and it can be vital for that communication to be confidential. If compromised, our coordination may run afoul, hindering establishment of our collective goals. In adversary conditions, competing other groups may successfully deploy countertactics
when confidentiality is broken. In communication both integrity and confidentiality matter. Cryptography’s the game we’ve been playing because we do need to communicate, and we do need to do it reliably and privately. Integrity, and confidentiality. It’s a survival thing.
SO, HOW ARE WE DOING?
Being clever symbol-manipulators, we’ve been making use of a few mathematic problems that have been considered to be hard to solve. Say, prime factorization[0]. If you multiply two large prime numbers (say p and q), you get a very large number n that’s divisible by p and q only. Looking at n, with no further knowledge, it’s extremely time-consuming to derive (this is called: factor) p and q. Yet if you are aware of p (or q), however, it’s trivial to compute q (resp. p). This is the basis of the Rivest-Shamir-Adleman (RSA) cryptographic scheme. It’s been in use as of 1977 and will stay with us in the foreseeable future.
(Note, RSA’s not the only game in town. Other cryptographic schemes exist; RSA is just a typical, representative example.)
How hard is it to get to factor p and q from n? That depends of the length of n, which of course depends on the lengths of p and q. That length is expressed in the number of the binary representation of n. Smaller is easier, larger is harder. Factoring the number 9 isn’t that hard, right? How about 143? Now do 16016003. If you got that, try 4097280091 next. Still with us? How about 250112012543? It gets hard fast. The last one uses 20-bit numbers. Petty stuff, but nevertheless challenging already.
We’ve been doing fine, so far. An expensive body of cryptanalysis has revealed no viable attacks against cryptography using sufficiently large key sizes. Brute force doesn’t cut it; the largest RSA key known to be cracked
was RSA-250, which uses a key size of 829 bits. That took 2700 ‘core-years’ of compute[1]. 2048-bit RSA keys have been the low bar in best practices for a long time now, 1024-bit RSA having been deprecated in 2013.
OH REALLY?
How good of you to ask! Venture capital is being raised, investors are in cahoots, and the subsequent FOMO-frenzy in the tech investor universe has been running red hot. Why? Well, there’ve been a few theoretical results in quantum algorithmics.
Shor’s and Grover’s Algorithms
In 1994 Peter Shor showed [2] that a quantum computer could be used to factor a number n in polynomial time, thus effectively breaking RSA.
Additionally, in 1996 Lov Grover published [3] a generic search algorithm using quantum superposition, which allows for multiple possibilities to be searched simultaneously and as a result achieves a quadratic speed up.
Impressive theoretical results indeed. But is that enough to kill classic cryptography?
Q DAY
To run Shor’s algorithm, a quantum computer is needed with a number of cubits that has a relation to the key size. Breaking a 2048-bit RSA key in the span of 8 hours requires a minimum slightly over (roughly) 6000 logical qubits (assuming a base noise error of 0.001).
That’s a lot of qubits. The biggest quantum computers out there, currently, are IBM’s Condor and Atom’s Atomic Array, with both slightly over 1000 qubits[4]. So the question becomes: when (if ever) will we witness the arrival of quantum computers of the next order of magnitude?
And when (if ever) that happens, what part of our current cryptography architecture will collapse, and which parts will still stand?
And that’s why we’re here
We don’t have a crystal ball (sorry). As Niels Bohr put it: “prediction is very difficult, especially of the future.”
What we do know is that things take time, dedication, and money. We can ask ourselves what drives development. Mere curiosity is rarely funded magnanimously, so realistic (or at least perceived-to-be-realistic) use cases need to be presented. There’s been a dearth of these; next to weakening a part of old-school cryptography, little to nothing has been put forward there. This begs the question of feasibility of actual process. If breaking current crypto would be the only use case to build quantum computers, why would any be built once cryptography has been quantum-proofed? Despite claims to the contrary, no compelling, concrete real-world use cases have been fielded.
Someday — and that day may never come — I’ll call upon you to do a service for me.
— Marlon Brando as Don Corleone in The Godfather (1972)
We can, regardless of the if and when of big, powerful quantum computers arriving on the scene, flesh out consequences of their arrival and plan for it. Given Q-day and an analysis of the cryptography under threat, ramifications can be made as to the requirements to state for data stored now that still needs to be protected on Q-day. Plans can be made, approaches defined, transitions executed.
We’re here. That’s what we’re doing.
REFERENCES
0. Though it should be noted that it has not been proven that prime factorization is intractable (superpolynomial), see [1]
1. Integer factorization Wikipedia (March 30, 2025) https://en.wikipedia.org/wiki/Integer_factorization
2. Shor’s Algorithm Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-26. Doi: http://dx.doi.org/10.1137/S0097539795293172
3. Grover’s Algorithm Grover, Lov K. (1996-07-01). “A fast quantum mechanical algorithm for database search”. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing – STOC ‘96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery. pp. 212–219. arXiv:quant-ph/9605043. Bibcode:1996quant.ph..5043G. doi:10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID 207198067
4. SpinQ, ‘Discover the World’s Largest Quantum Computer in 2025′
https://www.spinquanta.com/news-detail/discover-the-worlds-largest-quantum-computer-in20250106092507
