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

Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

arxiv.org

Post reply on HN
Print view View original

131–140 of 146 posts

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#131

Post by Moodles »

mikeodds wrote: post #125
TheRealPomax wrote: post #120

Earlier quoted context omitted.

except we already use qubits in the real world, and we already use entangled pairs in banking, so it's not really all that bullshit anymore. Quantum computers with a significant number (e.g thousands, but really, millions) of qubits, however, are still quite a ways away. But clearly not in the realm of bullshit anymore.

Is this referencing quantum cryptography being used in banking? Any good sources for more info on this, it sounds really interesting.

I'm no expert in quantum computation but my understanding is that using qubits for quantum computing is totally different to using qubits to exchange secrets as in cryptographic key exchange. The latter is using the property that observing the quantum state changes the state, thus an eavesdropper can't interfere when you send qubits over the wire to exchange a secret. That seems very different to arranging large amounts of qubits in a particular way to do useful calculations.

Even in the key exchange case, I'm personally pretty skeptical of its real-world usefulness because it's not really solving a problem we actually have: public key cryptography (even slower post-quantum variants) work just fine and seem a bit more practical than building some quantum infrastructure to send entangled qubits over to augment a secret that's already exchanged.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#132

Post by X6S1x6Okd1st »

jakozaur wrote: post #70

One day you can start calculating private keys based on public keys. This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle. This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).

IIRC public keys are only revealed on bitcoin once you authorize an out going transaction. There are large bitcoin addresses that have never revealed their corresponding public key such as https://www.blockchain.com/btc/address/37XuVSEpWW4trkfmvWzeg...

As long as you never reuse an address bitcoin would continue to be resistant to quantum attacks even if you can factor private keys from public keys, you still need to invert a hash function to go from address to public key.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#133

Post by haltingproblem »

Moodles wrote: post #131
mikeodds wrote: post #125

Earlier quoted context omitted.

Is this referencing quantum cryptography being used in banking? Any good sources for more info on this, it sounds really interesting.

I'm no expert in quantum computation but my understanding is that using qubits for quantum computing is totally different to using qubits to exchange secrets as in cryptographic key exchange. The latter is using the property that observing the quantum state changes the state, thus an eavesdropper can't interfere when you send qubits over the wire to exchange a secret. That seems very different to arranging large amou…

That was my initial reaction - quantum entanglement for crypto is not same as quantum computing and furthermore a hammer in search of a problem that does not exist (yet).

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#134

Post by Dylan16807 »

Strilanc wrote: post #88
thesz wrote: post #82

Earlier quoted context omitted.

You are off by orders of magnitude. The difference in memory density between DRAM and SRAM (register file) is not 100 times, more like 10x. Standalone "registers" - memory elements of pipelines, state machines etc, - are again not more than ten times less denser than SRAM. After DRAM goes SSD and after SSD goes disk. The difference in price per GB for SSD and disk is about four (4x) times, I looked for that numbers r…

Are you sure? I was just going off a quick search of Amazon, where 1 GB of ram cost ~30$, 1 TB of disk cost ~50$, and a CPU with ~1MB of L2 cache cost ~200$. Based on that I actually thought 100x was a comfortable underestimate, not an overestimate.

https://en.wikipedia.org/wiki/EDRAM

If the price/density difference was anywhere near that much you'd see a lot more chips with fat onboard DRAM caches.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#135

Post by mirekrusin »

reikonomusha wrote: post #83
fractionalhare wrote: post #81

Earlier quoted context omitted.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved. It might not look that way because there's a lot of (relatively) m…

I think it’s reasonable to be more optimistic than you put it. Qubit counts and qubit fidelity have been increasing at a remarkable rate. Just five years ago we could barely eek out a handful of qubits, and when we did, they’d be bad. Google’s quantum supremacy result is a testament to that. (At this stage, whether they actually demonstrated the “supreme” part of supremacy is, imho, irrelevant. They’ve demonstrated a…

The argument here is that reducing error rate/supporting error correction may be exponentially difficult, a bit like increasing clock frequency is now in classical computers.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#136

Post by sushisource »

haltingproblem wrote: post #119

I fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article: When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically pos…

Obviously this isn't the strongest argument in the world, but, if the whole field is so bullshit why has anyone bothered putting effort into post-quantum encryption? What's the point if quantum computers will never materialize?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#137

Post by alexw91 »

sushisource wrote: post #136
haltingproblem wrote: post #119

I fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article: When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically pos…

Obviously this isn't the strongest argument in the world, but, if the whole field is so bullshit why has anyone bothered putting effort into post-quantum encryption? What's the point if quantum computers will never materialize?

It's theoretically possible for someone to record encrypted traffic today, keep a copy of it for a decade or two until quantum computers are available, and then decrypt it in the future using the quantum computer. If you have data today, that needs to be secure for more than a few decades, you may want to move to post quantum crypto soon to stop that potential leak.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#138

Post by haltingproblem »

sushisource wrote: post #136
haltingproblem wrote: post #119

I fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article: When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically pos…

Obviously this isn't the strongest argument in the world, but, if the whole field is so bullshit why has anyone bothered putting effort into post-quantum encryption? What's the point if quantum computers will never materialize?

Lets rephrase it in terms of product-market fit - what problem is post-quantum encryption going to solve for people to put effort into it?

BTW, the term post-quantum encryption is delicious because we had never had the quantum encryption era. Like the post-high speed era rail in the US ;)

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#139

Post by grumple »

CodesInChaos wrote: post #30
PeterisP wrote: post #19

Earlier quoted context omitted.

I.e. you can solve it by rotating your keys/certificates every 90 days, like the expiry term given by Letsencrypt.

Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.

Do these attacks take the same amount of time for one round of encryption vs multiple?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#140

Post by caf »

haltingproblem wrote: post #138
sushisource wrote: post #136

Earlier quoted context omitted.

Obviously this isn't the strongest argument in the world, but, if the whole field is so bullshit why has anyone bothered putting effort into post-quantum encryption? What's the point if quantum computers will never materialize?

Lets rephrase it in terms of product-market fit - what problem is post-quantum encryption going to solve for people to put effort into it? BTW, the term post-quantum encryption is delicious because we had never had the quantum encryption era. Like the post-high speed era rail in the US ;)

The sense this term is using 'quantum' is as a shorthand for a point in time, where attacking cryptosystems using quantum computers becomes feasible.

So you can talk ante-quantum and post-quantum in this sense, but it makes little sense to talk about just 'quantum', in exactly the same way that we schedule a lot of things AM and PM but very little for precisely noon.

Post reply on HN