News for hackers. Stuff that matters.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by elephantum on Tuesday March 23, 2021 @08:34AM (#26554257)
Do I understand correctly, that largest quantum computer that exists today contains less than 100 qubits?

Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers....

They hit the wall in 2017.

We should be safe for now :)

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by CodesInChaos on Tuesday March 23, 2021 @08:49AM (#26554373)
Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012.

There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography.

https://crypto.stackexchange.com/questions/59795/largest-int...

A 2019 paper manged to factor 21 on a 16 qubit ibmqx5, but failed to go up to 35:

> the algorithm fails to factor N=35. This is due to the cumulative errors coming from the increasing number of two-qubits gates necessary to implement the more complex MEF needed for this case

https://arxiv.org/abs/1903.00768

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by graderjs on Tuesday March 23, 2021 @09:19AM (#26554611)
Jennifer and Peter Shor wrote a limerick that seems relevant:

   If computers that you build are quantum,
   Then spies of all factions will want 'em.
   Our codes will all fail,
   And they'll read our email,
   Till we've crypto that's quantum, and daunt 'em.
And Volker Strassen responded at a conference:

   To read our E-mail, how mean
   of the spies and their quantum machine;
   Be comforted though,
   they do not yet know
   how to factorize twelve or fifteen.
Source: http://www-math.mit.edu/~shor/notapoet.html
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by CodesInChaos on Tuesday March 23, 2021 @09:59AM (#26555049)
> Till we've crypto that's quantum, and daunt 'em.

Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by _hl_ on Tuesday March 23, 2021 @10:51AM (#26555729)
"Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by CodesInChaos on Tuesday March 23, 2021 @11:01AM (#26555847)
For practically all computationally secure crypto we use "secure" for "no known attacks faster than we'd like". QCs just extend the set of efficient algorithms.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by _hl_ on Tuesday March 23, 2021 @11:22AM (#26556084)
Indeed, but there is a much longer history of people trying and failing to break the schemes, and we have come to understand the hardness assumptions in classical crypto as probably quite reasonable.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by SAI_Peregrinus on Tuesday March 23, 2021 @02:31PM (#26558465)
There's a similarly long history of people trying and failing to break code-based schemes like Niederreiter and McEliece with binary Goppa codes. Unlike lattice-based schemes they're considered quite secure, but their key sizes are enormous (like, hundreds of KiB to several MiB in size). So they're impractical for embedded security, or any situation where key transfer bandwidth is an issue (IoT, metered data plans, etc).
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by Dylan16807 on Tuesday March 23, 2021 @05:29PM (#26560630)
Does IoT need to transfer keys?

When it comes to metered data, a few megabytes to access a new site sounds like normal internet to me. And you could use a trusted proxy/VPN; there are present-day apps that more or less fill that niche already.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by SAI_Peregrinus on Wednesday March 24, 2021 @09:59AM (#26567265)
Transfer is one issue, processing is another. If you're running an IoT device on an STM32F423ZH (chosen because my employer has a cell-enabled IoT device on that MCU) you've got 320k of total RAM. Considering there's overhead for the rest of the application, there's no way to use such keys on such a device.

A trusted proxy works if ECC is secure (no quantum computers), but if quantum attacks are practical then there would be no way to verify that the trusted proxy is actually what you think it is.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by Dylan16807 on Wednesday March 24, 2021 @01:46PM (#26570581)
> Considering there's overhead for the rest of the application, there's no way to use such keys on such a device.

If you wait a small number of years you'll be able to get twice the ram at the same price. So "it would barely fit in ram if nothing else is running" doesn't seem like a significant barrier to me.

> A trusted proxy works if ECC is secure (no quantum computers), but if quantum attacks are practical then there would be no way to verify that the trusted proxy is actually what you think it is.

Your trusted proxy would be using one of the secure multi-megabyte keys, of course. Am I missing something about that arrangement? If signatures would also be enormous then we have a more significant problem to deal with than key size.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by SAI_Peregrinus on Monday March 29, 2021 @05:09PM (#26628202)
The trusted proxy in your scheme exists to avoid needing to deal with the multi-megabyte keys on a device with only a few kilobytes of RAM. It CAN'T use such keys to secure the connection with the embedded device. If it could, it wouldn't be needed.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by DebtDeflation on Tuesday March 23, 2021 @10:19AM (#26555319)
>There are claims of bigger factored numbers, but they exploited special cases

Also, my understanding is that almost all of these factorizations utilize a "compiled" version of Shor's algorithm. Meaning that you need to know the factors in advance. So it's essentially "confirming" rather than "finding" the factors.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by CodesInChaos on Tuesday March 23, 2021 @10:24AM (#26555388)
AFAIK factoring 21 is "compiled" Shor, so even that result simplifies the problem a bit.

According the first link in my post, the numbers bigger than 21 were chosen to have specific mathematical properties and attacked with algorithms even less realistic that compiled Shor.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by cameronperot on Tuesday March 23, 2021 @08:38AM (#26554296)
IBM has 1000 qubits on their roadmap by 2023 [1]. I'm interested to see how that goes, and what we can learn from it about scaling up these systems into the thousands of qubits.

Edit: for anyone interested in learning more about quantum computation, I have a list of resources on my website [2].

[1] https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadm...

[2] https://cameronperot.com/resources/#quantum-physics

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by akvadrako on Tuesday March 23, 2021 @09:02AM (#26554470)
Since I didn't see it mentioned, I assume those are 1000 noisy qubits, so they'll require error correction. I wonder how many ideal qubits they are equivalent to.
Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by DebtDeflation on Tuesday March 23, 2021 @10:36AM (#26555551)
>largest quantum computer that exists today contains less than 100 qubits

The numbers reported in the press are physical qubits not logical qubits. You need multiple physical qubits + error correction to create a single logical qubit. The main type of error correction used today is something called "surface codes". With this type of error correction it's estimated that MILLIONS of physical qubits will be required to create a SINGLE fully error corrected logical qubit.

https://www.ncbi.nlm.nih.gov/books/NBK538709/

We do not have actual quantum computers today and we don't seem to be much closer to having them than we were a decade ago. What we have are really interesting quantum science experiments that get misrepresented by the press (and a handful of companies with a commercial interest in doing so).

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by mikewave on Tuesday March 23, 2021 @03:54PM (#26559610)
The largest production quantum computer that exists today - as in, the largest you personally can get access to - has 5,436 qubits: the D-Wave Advantage system.

Admittedly, it's not a gate-model machine that can run Shor's Algorithm, but it is a quantum computer, and at more than double the number of qubits plus far higher inter-qubit connectivity than our previous D-Wave 2000Q, it definitely demonstrates tremendous progress.

If you have a moment, you can sign up to use it for free at https://cloud.dwavesys.com - we have an online IDE, Jupyter notebook training material and tons of docs, a community forum, and of course some shiny demos that submit problems to the live QPU if you want to try them out.

Re:Factoring 2048 RSA integers in 177 days with 13436 qubits... by megiddo on Tuesday March 23, 2021 @08:41AM (#26554310)
And the error rate of 10^-3 seems problematic, as well.