After a decade of heavily government-sponsored propaganda about quantum computers, we are finally discovering the truth. RSA is NOT secure, not even against normal computers.
Edited and added in 2021-2023:
The story in unfolding slowly and so far can be summarized as follows:
- For years best known factoring and lattice algorithms did not exactly work together or lattice methods could not compete. For decades this topic was a side question, neglected and not studied. It was tentatively explored, for example, in 2013 by Schnorr in an obscure Springer volume.
- In 2021 we have major paper by the same author: here is the original paperr 232 about fac-relations from Feb 2021. This paper was a vague draft and almost a joke. It was immediately very heavily criticized, both publicly and privately, by fellow academic researchers, as being inaccurate, misleading, irresponsible, published too early etc etc.
- In July 2021 the author has corrected his claims, and published a new paper 933 with the same fac-relations technique, see Fast Factoring Integers by SVP Algorithms, corrected (iacr.org). Here is a short summary:
- The author is the leading worldwide expert on these questions. This is not a joke.
- The author maintains his claim that RSA is not secure.
- However what exactly he means, only experts can tell for now. There exist countless clever strategies to find simultaneously smooth triples of integers and therefore there exist multiple variants of this attacks.
- Academics are currently engaged in some type of chaotic speculative disinformation wars, in order to gain better visibility for their research.
- Academics do not always present results in a form which allows for a correct interpretation or interpolation. This is considered low class and is typically not publishable. They prefer to play it clever and publish a few more papers…
- The bottom line is that RSA is reportedly broken, but many details are not clear, and the reportedly the attack as described does not work well, or not yet, or we are missing some additional tricks or strategies.
- For example a well-known expert on lattices and cryptanalysis, Leo Ducas has released some code here and suggests that on a normal computer this attack should be slower than some other already known attacks. But we are not sure.
- Moreover, maybe things would look differently if we also used a quantum computer?
- Many questions remain.
- In January 2023 there is a new chapter written by Chinese researchers.
- A bold attempt to find the Schnorr fac-relations and a new strategy to crack RSA-2048 with a surprisingly small quantum computer, see 2212.12372.pdf (arxiv.org).
- Unhappily this paper and ALL previous papers have some technical flaws and omissions.
- We lack anything even remotely close to an overall feasibility and cost analysis for any full attack on RSA. Authors concentrate on offering to the world a new strategy and there are numerous questions which no one can answer.
- Current work mostly concentrates on some key sub-questions.
- They never actually try to study the hardness of the problems or the existence of solutions or the non-uniformity of their sizes, or the computation cost required.
- Quantum computers also have huge questions related to errors and lack of reliability.
- Inevitably the research work is now highly fragmented and progress needs to be made on multiple fronts and it is difficult to see in advance what type of attack will come out of it. We might need many many years of research to learn more about how to break RSA.
- Here is what says Scott Aaronson , chair of computer science at The University of Texas at Austin, and director of its Quantum Information Center:
“This is one of the most actively misleading quantum computing papers I’ve seen in 25 years”.