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

101–110 of 146 posts

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

#101

Post by m3kw9 »

mabbo wrote: post #93
gjm11 wrote: post #74

Earlier quoted context omitted.

Imagine that you find Satoshi's private key and start trying to sell his million bitcoins. Approximately one minute after you start this process, someone will figure out that either (1) bitcoins no longer securely belong to anyone or (2) Satoshi thinks selling off all his bitcoin is a good idea. Approximately two minutes after you start this process, the price of bitcoin will plummet. Sorry, you will not be taking ho…

You're not thinking big enough. Anyone can sell bitcoins and make money. But if you have the power to destroy bitcoin, well then you can short the entire bitcoin market and clean up. Frankly, I would just walk into the door of a large hedge fund and sell them to the key for $5B. They'll do far better than I ever could, and $5B is more money than I can possibly use in my lifetime, while being a tiny cost of business f…

Following the progress of computations, even if there is a whiff of it getting close (1year) away, Bitcoin would have suffered runs based on theory possibly becoming reality alone

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

#102

Post by robocat »

dcow wrote: post #97
Strilanc wrote: post #88

Earlier quoted context omitted.

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.

CPU cost is not dominated by the cache size is the problem, I think.

But I think that cache is roughly 50% of marginal production cost of the silicon chip die by mm2.

https://cdn.wccftech.com/wp-content/uploads/2020/11/AMD-Ryze...

https://images.anandtech.com/doci/16214/Zen3_arch_19.jpg

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

#103

Post by gautamcgoel »

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

I thought bitcoin was based off EC crypto, not RSA.

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

#104

Post by bcaa7f3a8bbc »

upofadown wrote: post #96
hk1337 wrote: post #18

Earlier quoted context omitted.

So, then I am definitely good using 4096 RSA?

Sure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size: * https://www.schneier.com/blog/archives/2017/05/post-quantum_...

That pqRSA paper by DJB is a joke, but it's mathematically correct and an interesting thought experiment - RSA really becomes post-quantum when you use a 1 TB key because it outgrows what Shor's algorithm can scale at that point. The paper is actually better, it proposed an original algorithm, GEECM, that's faster than Shor's algorithm for numbers with many small factors, then also showed pqRSA is safe from GEECM. He even submitted the algorithm to the NIST Post-Quantum Competition for review (among his more practical algorithms like Classic McEliece), it's just hilarious.

> DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!"

https://crypto.stackexchange.com/questions/59591/why-is-pqrs...

Here's his explanation of the idea:

https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-...

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

#105

Post by jsmith99 »

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

Assuming nothing has been spent previously from the wallet, you would have to break SHA256 before you could even find the public key you needed to factor. Bitcoin addresses are based on hashes of the public key and SHA256 appears quantum resistant.

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

#106

Post by f6v »

syrrim wrote: post #79
_hl_ wrote: post #66

Earlier quoted context omitted.

The hope is that quantum computers will give us an exponential speed up on some problems, which could (again, hopefully) allow us to solve some NP hard problems. This can be extremely useful for scientific computing (e.g. protein folding) and engineering, where computers have to solve complex NP-hard optimisation problems. It could also be possible to use the technology developed for the precise control and measureme…

>which will allow us to solve some NP hard problems No it won't

Could you elaborate?

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

#107

Post by SAI_Peregrinus »

bcaa7f3a8bbc wrote: post #104
upofadown wrote: post #96

Earlier quoted context omitted.

Sure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size: * https://www.schneier.com/blog/archives/2017/05/post-quantum_...

That pqRSA paper by DJB is a joke, but it's mathematically correct and an interesting thought experiment - RSA really becomes post-quantum when you use a 1 TB key because it outgrows what Shor's algorithm can scale at that point. The paper is actually better, it proposed an original algorithm, GEECM, that's faster than Shor's algorithm for numbers with many small factors, then also showed pqRSA is safe from GEECM. He…

Given the number of Star Wars references in the various NIST Post-Quantum Competition scheme names (CRYSTALS-KYBER, SABER, NewHope) I'm rather sad he didn't call it "Post Quantum RSA - The Phantom Menace".

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

#108

Post by SAI_Peregrinus »

gautamcgoel wrote: post #103
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).

I thought bitcoin was based off EC crypto, not RSA.

EC crypto is just as vulnerable to Shor's algorithm as RSA is.

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

#110

Post by marius_k »

BelenusMordred wrote: post #42
isolli wrote: post #31

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real…

I think Grover's algorithm could be used to find hashes with quadratic speedup. But that should not be an issue as quadratic slowdown could be achieved by doubling the problem size.
Post reply on HN