Ask HN: How long until quantum computers break 512 bit RSA/ECDSA? 1024 bit?

13 points by actinium226 ↗ HN
The more detailed your answer the better!

24 comments

[ 3.3 ms ] story [ 60.9 ms ] thread
[flagged]
Very interesting. Is anyone working on computers that handle the amplitudes directly? Are there research-level examples of such a computer or are we not there yet?
Anecdotally I only know of one team on Earth capable of doing it “properly”. They are working with Grigori Perelman on the system and it is made of cheap materials, almost intentionally, like a snub in the face of rich companies.

I know of no major research companies that have begun on the same line of research.

Do you have a source on that? Everything I've read about Perelman is that he hates the limelight. I can't imagine him running towards such a hype-riddled field.
It’s an anecdote. No source.
That makes it a rumor, not an anecdote.
Rumor would mean that I don’t have personal knowledge. I do. It is not a rumor, but rather an anecdote, and the source will remain unknown and unposted. I appreciate your reply.
You claim to have anecdotal knowledge. That may be true! But when you anonymously post that claim to the internet, it is a rumor.
I think we agree: in my personal context it is an anecdote but let’s use rumor in this context instead. :)
I thought Perelman ran off into the woods forever after winning the Fields Medal.

Nifty.

I agree with "many many years" but a good number of quantum computers use other methods (superconducting qubits from Google/Rigetti, or trapped ions from IonQ). They have much smaller numbers of qubits, are more generally applicable to problems, but have the issue of noisy readings.
Those are not quantum computers they are classical computers that have been enabled to process data matrices. Not the same as moving amplitudes directly.
No, that doesn't accurately describe either Google's nor Rigetti's quantum efforts. Google does make a classical matrix-multiplication circuit (TPU), but that's different from their quantum computing effort.
Not really. Different as in “BBQ chicken pizza” vs. “pepperoni pizza”.
On what basis do you make that statement? The hardware is literally manipulating coherent quantum states of trapped ions or transmon junctions in the cases of IonQ and IBM, respectively. Noisy and unreliable, sure, but most definitely not classical.
The annealing QCs have a lot of “qbits”, but they are far from the only people working on the problem.

Off the top of my head: Rigetti Google IBM Quantinuum Atom computing

As far as I’m aware, all are working on quantum computers with full entanglement. Definitely none are working on quantum annealing computers.

It is not possible to use entanglement states to process quantum data. More failed projects from supposed “the smartest people”— I am not impressed.

I also further disagree they are producing anything other than annealed states even if using some other methodology.

Food analogy: like saying you are making a “revolutionary new pasta” which is an egg noodle or a rice noodle as opposed to a flour noodle. Not impressive.

I'm pretty sure RSA 512 was broken a long time ago: https://arstechnica.com/information-technology/2015/10/break...
Oh wow, didn't realize 512 can already be factored. Thanks for this.
RSA-1024 is also a rather aggressive / dangerous choice, even before a quantum computer arrives: NIST SP 800-131A rev2 Table 2 and 5 forbid use of anything below 2048-bit RSA. Academic teams have actually broken up to RSA-829: https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge

Don’t roll your own crypto - just select a TLS cipher suite using Mozilla’s recommendations - but for hobby purposes, prefer Curve25519 or NIST P-256. Or play around with Kyber, post-quantum crypto is neat.

AFAIK quantum computers currently can only handle a dozen qubits or less. So we can't really extrapolate about timeframes yet, there's not enough data points to draw a curve. It could happen this year, it could never happen.
Careful with the terminology there. They do not “handle” the states but rather “access” or “read” them: moreover the qubits read are not processed along any probability vector which means they are scraping inherently junk data.

By analogy: imagine you want to make an aimbot to shoot people in an online FPS video game. You need your aimbot to calculate not only the vector to shoot at (our game has bullet drop and bullet objects, not hitscan weapons) but also to calculate for the opponent’s motion.

The way people at Google are doing it now, they look at a map of where the players are where when the game starts and try to ammo dump it… with no one there. Lol.