<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 28, 2019 at 12:17 PM Tom Mitchell <<a href="mailto:mitch@niftyegg.com">mitch@niftyegg.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><br></div><div>On Sun, May 26, 2019 at 3:08 AM Peter Gutmann <<a href="mailto:pgut001@cs.auckland.ac.nz" target="_blank">pgut001@cs.auckland.ac.nz</a>> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Tom Mitchell <<a href="mailto:mitch@niftyegg.com" target="_blank">mitch@niftyegg.com</a>> writes:<br>
<br>
>IBM believes that commercial quantum machines will be here in about 3-5<br>
>years.   If encrypted data at rest today has value or is a liability in the<br>
>next 3-5 years quantum resistant keys seem important.<br>
<br>
Uhh, you need to read the rest of the article, which you've actually quoted:<br>
<br>
  "Starting its R&D on quantum computing as early as in 1996, IBM released a<br>
  5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit<br>
  system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing that<br>
  the company will soon launch 58-qubit quantum computers."<br>
<br>
>From that we have at least a few data points, and there's more from non-IBM<br>
sources, so we can extrapolate over time.  Technically we can't actually do<br>
that because from everything I've read it's nonlinear, the first steps are<br>
relatively easy and then it gets harder and harder [0], but let's say it's<br>
linear just for argument's sake.  Anyway, to break 1kbit RSA you need about a<br>
million qubits.  Soon we'll have a computer with 58 qubits.  Graphing things<br>
and drawing a line to where even 1kbit RSA is at risk is left as an exercise<br>
for the reader.<br>
<br>
Peter.</blockquote><div dir="auto"><br></div><div dir="auto">Found this paper:</div><div dir="auto"><br></div><div dir="auto"><div><a href="https://arxiv.org/pdf/1905.09749.pdf" target="_blank">https://arxiv.org/pdf/1905.09749.pdf</a></div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"></blockquote><div dir="auto"><div dir="auto">How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits</div><div dir="auto">Craig Gidney1 , ∗ and Martin Eker</div><div dir="auto"><br></div><div dir="auto">Near the end in Conclusions.</div><div dir="auto"><< In, Mosca poses the hypophoric question: “How many physical qubits will we need to break RSA-2048? [...]</div><div dir="auto"> </div><div dir="auto"><< Current estimates range from tens of millions to a billion physical qubits”. The upper bound of “a billion physical qubits” is likely from [9]. Our physical assumptions are more pessimistic than the physical assumptions used in that paper (see Table II), so our results can be directly compared. Doing so shows that, in the four years since 2015, the worst case estimate of how many qubits will be needed to factor 2048 bit RSA integers has dropped nearly two orders of magnitude; from a billion to twenty million.”>><br></div></div></div></div></blockquote><div><br></div><div class="gmail_default" style="font-size:small">Oh the number of Qbits needed has indeed reduced. But the optimizations that they are employing are not necessarily valid for the problem of factorizing RSA moduli. Consider for example, this special case:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><a href="https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499">https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499</a></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Pretending to factor large numbers on a quantum computer</div><div class="gmail_default" style="font-size:small"><a href="https://arxiv.org/abs/1301.7007">https://arxiv.org/abs/1301.7007</a><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Basically, Smolin and Co show that the optimizations being employed to reduce the number of QBits required to implement Shor's algorithm kinda depend on already knowing the factors of the number.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">So yes they are implementing Shor's algorithm but no, they are not developing systems that can break a deployed RSA scheme.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Oh and it gets worse (or better from my point of view). The claims being made for increasing the number of QBits don't necessarily represent an increase in processing capability. </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">It is all really murky. The bottom line is that we need to take the potential for quantum cryptanalysis seriously because it could be devastating for electronic commerce. But we certainly do not need to panic. The engineering obstacles that need to be overcome to make Quantum Cryptanalysis viable are of the same order as those required to make fusion power work.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The other point to bear in mind is that we won't know whether there is a limit to quantum entanglement until we encounter it. There is no law of physics that states we must be able to form arbitrarily complex superpositions of quantum states. That is an assumption in our current models of physics.</div><div class="gmail_default" style="font-size:small"><br></div></div></div>