[Cryptography] The race to Quantum machines.

[Phillip Hallam-Baker]

On Tue, May 28, 2019 at 12:17 PM Tom Mitchell <mitch at niftyegg.com> wrote:

>
> On Sun, May 26, 2019 at 3:08 AM Peter Gutmann <pgut001 at cs.auckland.ac.nz>
> wrote:
>
>> Tom Mitchell <mitch at niftyegg.com> writes:
>>
>> >IBM believes that commercial quantum machines will be here in about 3-5
>> >years.   If encrypted data at rest today has value or is a liability in
>> the
>> >next 3-5 years quantum resistant keys seem important.
>>
>> Uhh, you need to read the rest of the article, which you've actually
>> quoted:
>>
>>   "Starting its R&D on quantum computing as early as in 1996, IBM
>> released a
>>   5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit
>>   system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing
>> that
>>   the company will soon launch 58-qubit quantum computers."
>>
>> From that we have at least a few data points, and there's more from
>> non-IBM
>> sources, so we can extrapolate over time.  Technically we can't actually
>> do
>> that because from everything I've read it's nonlinear, the first steps are
>> relatively easy and then it gets harder and harder [0], but let's say it's
>> linear just for argument's sake.  Anyway, to break 1kbit RSA you need
>> about a
>> million qubits.  Soon we'll have a computer with 58 qubits.  Graphing
>> things
>> and drawing a line to where even 1kbit RSA is at risk is left as an
>> exercise
>> for the reader.
>>
>> Peter.
>
>
> Found this paper:
>
> https://arxiv.org/pdf/1905.09749.pdf
>
> How to factor 2048 bit RSA integers in 8 hours using 20 million noisy
> qubits
> Craig Gidney1 , ∗ and Martin Eker
>
> Near the end in Conclusions.
> << In, Mosca poses the hypophoric question: “How many physical qubits will
> we need to break RSA-2048? [...]
>
> << 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.”>>
>

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:

https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499

Pretending to factor large numbers on a quantum computer
https://arxiv.org/abs/1301.7007

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.

So yes they are implementing Shor's algorithm but no, they are not
developing systems that can break a deployed RSA scheme.


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.

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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190528/2fdd09a5/attachment.html>