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

Why Quantum Computers Might Not Break Cryptography

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 26 posts

Re: Why Quantum Computers Might Not Break Cryptography

#11

Post by 2bluesc »

timthelion wrote: post #7

If I had a quantum computer that was capable of breaking RSA, I wouldn't tell anyone. The whole point is to be able to spy on people, and you wouldn't be able to do that if everyone knew that RSA was broken. I don't know if quantum computers exist, but I'm sure once they do, the people who build them will keep them secret.

> I don't know if quantum computers exist, but I'm sure once they do, the people who build them will keep them secret.

Probably right. UNLESS it's a private company and it's losing bids from government agencies that would otherwise pay for silence. And in this case, you could assume two quantum computer designs exist and the loser is now looking for new markets/customers.

Re: Why Quantum Computers Might Not Break Cryptography

#13

Post by snakeanus »

I am worried about the following part from the paper " rel="nofollow">https://cr.yp.to/papers/pqrsa-20170419.pdf>

"Our batch prime-generation algorithm suggests that, to help reduce energy consumption and protect the environment, all users of RSA — including users of traditional pre-quantum RSA — should delegate their key-generation computations to NIST or anohter trusted third party. This speed improvement would also allow users to generate new RSA keys and erase old RSA keys more frequently, limiting the damage of key theft."

If you told me this was a parody of NSA disinfo, I'd believe it. But apparently, it's a serious paper by djb and Heninger. What happened? Did they finally crack djb, maybe after tying him to the Appelbaum mess? I had hopes for him because ``Keeping crypto insecure'' was talking about stuff TLAs certainly didn't want to see in the spotlight, but this is incredibly disappointing. When I read this passage for the first time I actually laughed for five minutes straight because it was so ridiculous.

Re: Why Quantum Computers Might Not Break Cryptography

#14

Post by snakeanus »

mtgx wrote: post #6
exabrial wrote: post #2

That is an interesting argument... Today we assume RSA is "Safe" because we can guess the maximum computational power of an attacker, and using a key size that makes cracking the key an unfavorable avenue for attack. He's merely suggesting the same thing: use a really large key (terabit size), and since quantum computers are quite exotic, it will be an unfavorable avenue of attack.

We can't even get people off SHA1 to SHA2 "because of lower performance." Somehow I doubt the "1 terrabit RSA key" would go over well with them. I think there's a much better chance we move off to still slower, but not as slow, quantum-resistant crypto algorithms, than just much larger RSA keys.

GPG even disabled the generation of RSA keys over 4kib.

Re: Why Quantum Computers Might Not Break Cryptography

#15

Post by snakeanus »

gitpusher wrote: post #8

So... what is the argument exactly? That quantum computers won't be fast enough to break a key that's larger than most people's hard drives and would be utterly useless in practice?

The argument is that it is possible to use RSA that is post-quantum safe in the real world.

Not every research needs to produce a result that is ready-to-use in everyone's home.

Re: Why Quantum Computers Might Not Break Cryptography

#16

Post by tptacek »

This seems pretty academic: even if RSA can be kept alive at some enormous key size, the reason we use RSA and not lattices or isogenies is that RSA is more practical.

That equation flips if quantum computing becomes a real threat, and the numbers in the paper don't appear to change that at all: the key sizes theorized here are, for instance, far bigger than the keys we use in RLWE schemes.

As others here have noted: the paper we're talking about is not entirely serious.

Re: Why Quantum Computers Might Not Break Cryptography

#17

Post by tptacek »

snakeanus wrote: post #13

I am worried about the following part from the paper " rel="nofollow">https://cr.yp.to/papers/pqrsa-20170419.pdf> "Our batch prime-generation algorithm suggests that, to help reduce energy consumption and protect the environment, all users of RSA — including users of traditional pre-quantum RSA — should delegate their key-generation computations to NIST or anohter trusted third party. This speed improvement would als…

Pretty sure not serious.

Re: Why Quantum Computers Might Not Break Cryptography

#18

Post by jcranmer »

snakeanus wrote: post #13

I am worried about the following part from the paper " rel="nofollow">https://cr.yp.to/papers/pqrsa-20170419.pdf> "Our batch prime-generation algorithm suggests that, to help reduce energy consumption and protect the environment, all users of RSA — including users of traditional pre-quantum RSA — should delegate their key-generation computations to NIST or anohter trusted third party. This speed improvement would als…

I read the paper, and it's not clearly so incriminating in context. You've left out the critical immediate following sentence:

"However, all trusted-third-party protocols raise security questions (see, e.g., [19] and [24]), and there are significant costs to all known techniques to securely distribute or delegate RSA computations. The challenge here is to show that secure multi-user RSA key generation can be carried out more efficiently than one-user-at-a-time RSA key generation."

The point is that post-quantum RSA relies on massive keysizes that make generating single keys extremely expensive in comparison to today's state-of-the-art, and that it's possible to speed it up by making many keys at the same time. The comment about delegating to NIST was probably meant as a joke, not as any serious consideration.

Re: Why Quantum Computers Might Not Break Cryptography

#19

Post by darawk »

> As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor’s algorithm and much faster than pre-quantum factorization algorithms.

This seems like the real point of this paper, no? The rest seems like a joke.

Re: Why Quantum Computers Might Not Break Cryptography

#20

Post by blacksmythe »

mtgx wrote: post #6
exabrial wrote: post #2

That is an interesting argument... Today we assume RSA is "Safe" because we can guess the maximum computational power of an attacker, and using a key size that makes cracking the key an unfavorable avenue for attack. He's merely suggesting the same thing: use a really large key (terabit size), and since quantum computers are quite exotic, it will be an unfavorable avenue of attack.

We can't even get people off SHA1 to SHA2 "because of lower performance." Somehow I doubt the "1 terrabit RSA key" would go over well with them. I think there's a much better chance we move off to still slower, but not as slow, quantum-resistant crypto algorithms, than just much larger RSA keys.

  >> We can't even get people off SHA1 to SHA2 "because of lower performance." Somehow I doubt the "1 terrabit RSA key" would go over well with them.
So apparently we are going to need quantum processors to generate encryption that is resistant to quantum processors.
Post reply on HN