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

21–30 of 161 posts

Re: Breaking RSA with a quantum computer?

#21

Post by flippy_flops »

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

Can a quantum computer fit in an answering machine? :) https://www.youtube.com/watch?v=F5bAa6gFvLs

Re: Breaking RSA with a quantum computer?

#22

Post by zzz345345 »

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.

> 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

Because Bitcoin is centralized, if it would get cracked tomorrow, the major miners could decide to save everyone.

Re: Breaking RSA with a quantum computer?

#23

Post by barathr »

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

It's called Impagliazzo's Worlds Paper:

https://scholar.google.com/scholar?cluster=14678868687868063...

A classic paper that explores what happens if various scenarios come to pass. Would be worth exploring some of the updated versions and fictionalizing them.

Re: Breaking RSA with a quantum computer?

#24

Post by A4ET8a8uTh0 »

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.

Re: Breaking RSA with a quantum computer?

#25

Post by rrjjww »

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

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?

Re: Breaking RSA with a quantum computer?

#28

Post by matthewdgreen »

This is not my area, but I wanted to mention this before speculation got out of control: some quick feedback from colleagues is that the analysis in this paper seems to assume Schnorr's claims from 2021 [0] without detailed supporting evidence that these claims are true for large parameters like the ones needed to factor RSA-2048. But these claims are viewed skeptically, and this paper doesn't provide much evidence to change that.

[0] https://eprint.iacr.org/2021/933

Re: Breaking RSA with a quantum computer?

#29

Post by [deleted] »

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.

[deleted]
Post reply on HN