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

91–100 of 161 posts

Re: Breaking RSA with a quantum computer?

#91

Post by gambiting »

idiotsecant wrote: post #14
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…

Yes, we simply change to one time pad encryption and ... distribute pre-share keys to every user on earth for every service that modern civilization relies on? The failure of RSA in a significant way would mean the end of modern commerce, military balance of power, and the sharing of information. It would be a history-altering event in the best case and devolve into existential war in the worst case. OTPs would do ex…

>>OTPs would do exactly zero to prevent any of that.

So if it was literally the only remaining unbroken type of encryption on the planet, it would have no effect? How so, exactly? We would just go with no encryption whatsoever rather than bear the inconvenience of distributing OTP keys?

Re: Breaking RSA with a quantum computer?

#92

Post by riffraff »

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

And it's a great movie!

Re: Breaking RSA with a quantum computer?

#93

Post by andrewla »

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

If this roadmap is accurate for the present, the types of qbits here are NISQ qubits, so not useful for any sort of generalized computation no matter how many they have.

Which is to say that Osprey has 433 qubits, so should be capable of 86 fault tolerant error corrected qubits, so they should be able to factor (not bothering with the math) AT LEAST ONE NUMBER using Shor's algorithm, and yet they cannot.

Re: Breaking RSA with a quantum computer?

#94

Post by brobinson »

spydum wrote: post #52
advisedwang wrote: post #8

Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.

I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.

AES-128 is effectively AES-64 when quantum computers exist which can run Grover's algorithm. That's not a huge exponent.

Re: Breaking RSA with a quantum computer?

#95

Post by px43 »

miga wrote: post #87
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.…

It is fair to say, that in security assessment you estimate lower bound on complexity of hacking. Schor proved upper bound.

There are two cryptographers being discussed here. Peter Shor, and (Claus) Peter Schnorr.

Neither are Schor.

Re: Breaking RSA with a quantum computer?

#96

Post by adgjlsfhk1 »

TacticalCoder wrote: post #86
jokoon wrote: post #51

so just increase to 4096 or 8192 bits or beyond?

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).

Because it isn't. This paper (alegedly) uses sublinear qbits (that's the whole point).

Re: Breaking RSA with a quantum computer?

#97

Post by adgjlsfhk1 »

brobinson wrote: post #94
spydum wrote: post #52

Earlier quoted context omitted.

I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.

AES-128 is effectively AES-64 when quantum computers exist which can run Grover's algorithm. That's not a huge exponent.

for the time being it's fine (we're a long way away from having fast quantum computers where 2^64 is a significant problem), and AES-256 is already widely used

Re: Breaking RSA with a quantum computer?

#98

Post by TillE »

TacticalCoder wrote: post #89

> A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. If a quantum computer can break 2048-bit RSA, what about elliptic curves?

Elliptic curves are also vulnerable to Shor's algorithm. However, there are several new algorithms for asymmetric cryptography, such as Google's NewHope:

https://en.wikipedia.org/wiki/Post-quantum_cryptography

https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...

Re: Breaking RSA with a quantum computer?

#99

Post by molticrystal »

Who was the guy and what was the flawed and retracted paper mentioned in the below quote from Schneier's article?

>In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.

Re: Breaking RSA with a quantum computer?

#100

Post by [deleted] »

molticrystal wrote: post #99

Who was the guy and what was the flawed and retracted paper mentioned in the below quote from Schneier's article? >In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.

[deleted]
Post reply on HN