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

61–70 of 161 posts

Re: Breaking RSA with a quantum computer?

#61

Post by Strilanc »

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. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2].

The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA".

How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them.

Is there somewhere where I can bet money that this doesn't amount to anything?

1: https://arxiv.org/abs/quant-ph/9508027

2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2...

3: https://arxiv.org/abs/2212.12372

Re: Breaking RSA with a quantum computer?

#62

Post by filleokus »

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

Not exactly that but: https://suricrasia.online/unfiction/basilisk/

Re: Breaking RSA with a quantum computer?

#63

Post by tptacek »

shockeychap wrote: post #57

> Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. Yeah, that alone is impressive. Schneier led a group that wrote Twofish, which was one of the AES finalists before losing Rijndael.

It's not in fact that impressive. The math for all sorts of cryptography goes over Schneier's head (as he sort of infamously implied with elliptic curve, over a decade ago). That's normal! Cryptographers specialize. Having a really careful, fine-grained, up-to-date intuition for differential cryptanalysis is crucial for designing hashes and ciphers, but less so for a key exchange.

Not writing this to dunk on Schneier so much as to relate that cryptography is specialized, and that generally there aren't a lot of people that you'd expect to be ultra up on PQ key exchanges and modern block cryptography.

Re: Breaking RSA with a quantum computer?

#64

Post by gronky_ »

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…

So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?

Re: Breaking RSA with a quantum computer?

#65

Post by itcrowd »

fragmede wrote: post #56
gleenn wrote: post #13

Earlier quoted context omitted.

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?

so print it via pressure into the inside of a sealed envelope? that's how they send me my PIN.

(not sure if replying to troll..)

The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?

Re: Breaking RSA with a quantum computer?

#66

Post by gambiting »

itcrowd wrote: post #65
fragmede wrote: post #56

Earlier quoted context omitted.

so print it via pressure into the inside of a sealed envelope? that's how they send me my PIN.

(not sure if replying to troll..) The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?

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

Re: Breaking RSA with a quantum computer?

#67

Post by Strilanc »

gronky_ wrote: post #64
Strilanc wrote: post #41

Earlier quoted context omitted.

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…

So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?

If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction.

Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower.

...but don't forget that "if the paper is correct" bit.

Re: Breaking RSA with a quantum computer?

#68

Post by myself248 »

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

Isn't that basically implied by the ending of Sneakers (1992)?

It would be fun fodder for a sequel, but I feel like it'd come across as histrionic disaster-porn.

Re: Breaking RSA with a quantum computer?

#69

Post by gambiting »

codethief wrote: post #11
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…

> we just switch to the one time pad encryption "just". So how do you do the key exchange?

Depends on the security of the service you want to use - I'd expect my bank or my email provider to send me my encryption keys by a recorded letter. Hacker news can probably email me their key instead.

Again, we're talking about some "world ending" scenario that OP mentioned - where all "normal" forms of encryption are already broken. If OTP is the only unbreakable encryption around, them I'm sure we'd find a way to distribute keys.

Re: Breaking RSA with a quantum computer?

#70

Post by itcrowd »

gambiting wrote: post #66
itcrowd wrote: post #65

Earlier quoted context omitted.

(not sure if replying to troll..) The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?

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

Concur. I should have stated "an argument" not "the argument".
Post reply on HN