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

71–80 of 161 posts

Re: Breaking RSA with a quantum computer?

#71

Post by kadoban »

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

There is more to diplomacy and war than destruction. If you can read your adversary's private messages, you can do a lot better than blowing their shit up.

Re: Breaking RSA with a quantum computer?

#72

Post by djmips »

b112 wrote: post #45
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?

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

A Whatsit. A Thingamabob. A doohickey. I remember those - people still use them I think?

Re: Breaking RSA with a quantum computer?

#73

Post by Grimburger »

gjsman-1000 wrote: post #12
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.

Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers. If you want to be safe, you might almost consider standard cryptography on one of…

> If you want to be safe

You use post-quantum with a vetted algorithm in a hybrid scheme, usually this just involves concatenation or hashing.

Re: Breaking RSA with a quantum computer?

#74

Post by Grimburger »

kmeisthax wrote: post #20
idiotsecant wrote: post #19

Earlier quoted context omitted.

It's worth noting that BTC could be quantum-resistant if enough of the network decided they wanted it to be. Unfortunately the BTC community is famously resistant to change so it wouldn't happen until it's too late, but in a rational world the problem could be fixed.

Alright. Who gets to confiscate the pre-quantum keyed Bitcoin? Miners or codebreakers?

SHA2 is not under threat from post-quantum computing. Only the signatures used.

Re: Breaking RSA with a quantum computer?

#75

Post by HWR_14 »

Strilanc wrote: post #61

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

The difference is Shor is attempting to prove something. This article is by a security researcher who cares about staying ahead of threats. That is, a 10% chance that RSA-2048 was broken means he's screaming about changing to -4096 or another standard. Because he is trying to make security systems reliable.

Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being true in what the paper is saying. In some other cases, "being right" means that the action you take is correct. Trying reading it as not a paper on "is RSA-2048 cracked" but "is RSA-2048 still safe".

Re: Breaking RSA with a quantum computer?

#76

Post by timerol »

filleokus wrote: post #62
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/

It took me a surprisingly long time to realize that I was reading fiction. The example SHA sums even do work, it's just that they only start with 40 bits set to 0 (expect to require 10^12 operations to generate each randomly - about a second on an ANTMiner) instead of 88 0 bits (multiple weeks of the full Bitcoin network to generate each randomly)

Re: Breaking RSA with a quantum computer?

#77

Post by rubberband »

Strilanc wrote: post #61

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

Let me know if you find such a betting venue... I'll take the same side.

I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.

Re: Breaking RSA with a quantum computer?

#78

Post by aburan28 »

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

Sneakers is the thriller movie you’re looking for

Re: Breaking RSA with a quantum computer?

#79

Post by Strilanc »

HWR_14 wrote: post #75
Strilanc wrote: post #61

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

The difference is Shor is attempting to prove something. This article is by a security researcher who cares about staying ahead of threats. That is, a 10% chance that RSA-2048 was broken means he's screaming about changing to -4096 or another standard. Because he is trying to make security systems reliable. Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being…

I agree that it makes sense for cryptographers to be jumpy around papers claiming improvements in quantum factoring, even if those papers are low quality and likely to be wrong. But that doesn't mean you stop calling the papers low quality and likely to be wrong.

I guess I'd also be a lot more sympathetic if the paper had a paragraph in the abstract, or at least the intro and conclusion, where they explicitly positioned the paper as a wild idea that could work but probably won't but is still worth considering because of the risks.

Re: Breaking RSA with a quantum computer?

#80

Post by Strilanc »

rubberband wrote: post #77
Strilanc wrote: post #61

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

Let me know if you find such a betting venue... I'll take the same side. I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.

For the Microsoft one I'm assuming you're referring to the retraction of the detection of Majoranas [1].

Do you have a reference for a Google quantum paper being retracted? I don't recall an instance of that (disclaimer: I am on the Google quantum team; my views do not represent them).

1: https://www.nature.com/articles/s41586-021-03373-x

Post reply on HN