Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Breaking RSA with a quantum computer?

schneier.com

Post reply on HN
Print view View original

141–150 of 161 posts

Re: Breaking RSA with a quantum computer?

#141

Post by XorNot »

Strilanc wrote: post #41
gronky_ wrote: post #33

You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap

The amount of error correction you need is more than what the five qubit code provides. A more typical estimate is that you'd need 1000 physical qubits per logical qubit. For example, using the surface code, a back of the envelope estimate would be that you need a code distance of d = ln(number_of_operations). Each logical qubit will use 2d^2 physical qubits. So for a million operations you'd need around 400 physical…

The other issue when you start talking about very large numbers of qubits is that they're not independent. Building more qubits influences your noise environment substantially.

Expectations of a Moore's law type improvement rate are going to be left wanting.

Re: Breaking RSA with a quantum computer?

#142

Post by jackmott42 »

Strilanc wrote: post #61

I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work.…

I think you are right that this paper may not amount to anything but it should also be a big wakeup call that maybe we need to switch or enhance our public key crypto starting now rather than later, in case similar ideas can work, or in case quantum computers get a little bit better faster than we thought, etc.

Re: Breaking RSA with a quantum computer?

#143

Post by nunez »

greggarious wrote: post #37
gronky_ wrote: post #33

You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap

What practical things can be done once RSA is broken?

isn't most stuff elliptic curve now?

Re: Breaking RSA with a quantum computer?

#144

Post by yuhong »

matthewdgreen wrote: post #28

This is not my area, but I wanted to mention this before speculation got out of control: some quick feedback from colleagues is that the analysis in this paper seems to assume Schnorr's claims from 2021 [0] without detailed supporting evidence that these claims are true for large parameters like the ones needed to factor RSA-2048. But these claims are viewed skeptically, and this paper doesn't provide much evidence t…

[dead]

Re: Breaking RSA with a quantum computer?

#145

Post by jeandejean »

krastanov wrote: post #129
TacticalCoder wrote: post #86

Earlier quoted context omitted.

Why is this downvoted? Ain't it exponentially harder to break RSA using qubits each time you double the key length? Until we switch to quantum resistant algorithms, we can keep doubling the key length for some time no? 8192 bits should still be acceptable speed wise (if we consider that 2048 bits is broken, then I'll take slower operations over broken keys any day of the week).

No, if you have a scalable quantum computer (which no one has yet), then doubling the key size just requires doubling the number of logical qubits. That is for asymmetric encryption that uses "hidden subgroup problems", like RSA. We have newer asymmetric algorithms that are resistant to quantum attacks, they are just not well tested yet.

Judging by the current difficulties of building a quantum computer with bigger number of qbits, I'd assume scaling linearly isn't trivial at all. So increasing key size should definitely increase security, if not exponentially, at least buying a lot of time?

Re: Breaking RSA with a quantum computer?

#146

Post by pelasaco »

I remember that some small countries, running DPI in their up-link were just storing their whole encrypted traffic to - when this day comes - be able to decrypt the traffic and see who was conspiring against the government back in the days and then start the witch hunt. Maybe this day is coming. Maybe its already there for some degree.

Re: Breaking RSA with a quantum computer?

#147

Post by jwilk »

aburan28 wrote: post #78
gjsman-1000 wrote: post #5

I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...

Sneakers is the thriller movie you’re looking for

This one?

https://www.imdb.com/title/tt0105435/

Re: Breaking RSA with a quantum computer?

#148

Post by esjeon »

gfaster wrote: post #15
itcrowd wrote: post #2

Huge, if true. However, many such claims have surfaced before and turned out to be dudds. For now, I am taking it with a spoon of salt but with an interest of any follow-ups and peer review.

In an update on the article, it reveals that it relies on an algorithm that breaks down with larger N for an unknown reason. It seems like we're safe for now.

Even when it worked, QC itself is not massively deployable right now. Agencies will be sucking their thumbs while everyone migrates to something stronger or even quantum-proof algorithms. No drama.

Re: Breaking RSA with a quantum computer?

#149

Post by armb »

gleenn wrote: post #13
gambiting wrote: post #6

Earlier quoted context omitted.

In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetche…

Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?

Quantum Key Distribution. You can prove that the key hasn't been intercepted. But since that means you need a direct point to point connection with no routers, switches, hubs, amplifiers/repeaters etc., it only works for a tiny fraction of cases. https://en.wikipedia.org/wiki/Quantum_key_distribution

Re: Breaking RSA with a quantum computer?

#150

Post by gambiting »

bee_rider wrote: post #112
gambiting wrote: post #66

Earlier quoted context omitted.

Well no, that's not true - a bank could issue you with a one-time-pad long enough to encrypt the next 10000 messages with you, and use that over the years - they just need to tell you which line of the key is needed to decrypt your message. In that scenario you only need to guarantee security for the first time the key is distributed(for example a file sent to you when the account is opened).

You’d have to guarantee security every time a key is distributed, right? I guess practically it would look like going to the bank every few years… or maybe only once per account, you can fit a lot of bank statements in a couple gigabytes. Actually this could be a nice service to offer now. We might worry that someday public key crypto will be broken, and we wouldn’t want all our old bank statements to become public a…

I mean, years ago my local bank had an online banking system, where your PC had to dial-up their local server for any operations - and the authentication key was on a floppy. Which meant that yes, you needed to visit their branch once every year for a new key distributed on this physical medium.

Yes, it was inconvenient, but hardly an impossible thing to do. Banks manage to communicate the PIN for your card safely every time you open an account, I'm sure this could be done as well.

Post reply on HN