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

41–50 of 161 posts

Re: Breaking RSA with a quantum computer?

#41

Post by Strilanc »

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 qubits per logical qubit and for a trillion operations you'd need around 1500 physical qubits per logical qubit. So, way more than 5.

(A major practical obstacle to using almost-anything-that-isn't-the-surface-code is that the surface code has forgiving connectivity and maximum-allowed-physical-noise requirements.)

Re: Breaking RSA with a quantum computer?

#42

Post by erik »

rrjjww wrote: post #25
claytongulick wrote: post #17

Earlier quoted context omitted.

All that would need to happen for this exact scenario to occur would be for anyone, anywhere to find a case where P == NP. [1] P !== NP is a theory that has never been proven, so it very well could happen in reality. This is one of those things that keeps me awake, like Carrington events [2]. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem [2] https://en.wikipedia.org/wiki/Carrington_Event

As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem? To rephrase if this is not the case - what value does solving P = NP provide?

If P == NP, then it could be possible that a proof would show that an algorithm must exist without providing such an algorithm. But that approach wouldn't be necessary, actually showing an algorithm would of course also be a proof.

> To rephrase if this is not the case - what value does solving P = NP provide?

P vs NP is a question of enormous practical interest. But it's also a very interesting question of pure mathematics. A proof that P != NP, or a proof of P == NP that didn't provide an algorithm would still be a huge deal in the math and computer science world.

Re: Breaking RSA with a quantum computer?

#43

Post by b112 »

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

And people wonder why I don't upgrade my 1996-1998 webpages to https.

In the end, as the world burns, I will helpfully explain how I was right.

Re: Breaking RSA with a quantum computer?

#44

Post by advisedwang »

A4ET8a8uTh0 wrote: post #24
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 will admit that I have no idea how that would look like. If quantum computer can be as capable as one envisioned in Jormungand, I am not sure if anything short of declaring them a weapon is needed.

Quantum computers aren't magic, they have specific capabilities that can be planned around. Google 'post-quantum cryptography' for current work on quantum resistent algorithms, some of which are already being deployed to production.

Re: Breaking RSA with a quantum computer?

#45

Post by b112 »

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?

I remeber in the very early 2000s, a guy had a stopwatch sized whos-it, and it kept flashing numbers on it. Updated every 5 minutes.

Apparently, some cesium based list of numbers, again, was 20 years ago.

Point is, it was a one time pad...

Re: Breaking RSA with a quantum computer?

#46

Post by reikonomusha »

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

A 5-qubit code corrects against single qubit errors. You could say a factor of 5 is a lower bound. In more technical terms, this scheme fixes all weight-1 errors.

More realistically [1], you'd have a factor of around 1,600 for a distance-27 code.

[1] https://arxiv.org/pdf/1905.09749.pdf

Re: Breaking RSA with a quantum computer?

#47

Post by johncessna »

emptybits wrote: post #26

"And there’s the nagging question of why the Chinese government didn’t classify this research" Would like to hear informed thoughts on any state's pros and cons of sharing such obviously weaponizable discoveries.

As a guess, if you're the only one who knows about this, it's one hell of a zero day. Once used though, the cat is out of the bag and industry will race to patch it. Yes, it'll take time.

If I were a country who could easily just drop bombs on people to cause destruction, then I'd rather leak something that I have no defense against in the hopes it gets patched rather than save it as a tool to use.

Re: Breaking RSA with a quantum computer?

#48

Post by orthecreedence »

alberth wrote: post #7
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...

Agreed. But how would the movie end?

Cloudflare and Meta team up to invent a proprietary crypto algorithm that fixes everything but routes all traffic through their servers, centralizing the internet completely. All speech is controlled and monitored by this new entity, which receives a national security letter thereby merging it with the US government for all intents and purposes, but, like, you know, for our safety.

Nobody notices or cares what has happened, and critics are met with "well it dOesN'T mATteR because they aren't using the information for anything bad."

Re: Breaking RSA with a quantum computer?

#49

Post by reikonomusha »

meltyness wrote: post #9

A note to cast further suspicion on the immediate risk severity: The researchers indicate use of a computer built with superconducting qubits in the abstract, to that, superconducting qubits present barriers such as - limited coherence time due to common atmospheric muon events, and resulting phonons - limited topological connectivity, further increasing needed coherence time.

Limited coherence time is not explained as simply as "atmospheric muon events". There are a variety of reasons, some environmental, others a result of imperfect fabrication, etc. that contribute to decoherence, gate error, etc.

Re: Breaking RSA with a quantum computer?

#50

Post by advisedwang »

version_five wrote: post #35
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.

No practical quantum supremacy or anything like it has been demonstrated has it? Is it sort of expected that will co-occur with QC breaking encryption? I'm just trying to gauge how "almost here" this actually is, or if it's still talk

Cloudflare estimates 15-40 years[1]. Cloudflare, Google [2], Amazon [3] and others are all at various phases of moving to post-quantum algorithms.

My own lesson from the Snowden revelations is that if we're close enough to a security break that the possibility is well understood, there's a very high chance someone is already doing it.

[1] https://blog.cloudflare.com/post-quantum-for-all/

[2] https://cloud.google.com/blog/products/identity-security/why...

[3] https://www.amazon.science/blog/preparing-today-for-a-post-q...

Post reply on HN