I am worried about the following part from the paper <<a href="https://cr.yp.to/papers/pqrsa-20170419.pdf>" rel="nofollow">https://cr.yp.to/papers/pqrsa-20170419.pdf></a><p>"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."<p>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.
There are post-quantum public key algorithms which are much more efficient than terabit-size RSA.<p><a href="https://en.wikipedia.org/wiki/Post-quantum_cryptography" rel="nofollow">https://en.wikipedia.org/wiki/Post-quantum_cryptography</a>
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.<p>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.<p>As others here have noted: the paper we're talking about is not entirely serious.
TLDR; RSA keys can be generated large enough (1TB was the example in the article) that it would still take an inordinate amount of time to brute force, in spite of the potential speed advantages available to the quantum computer.
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.<p>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.
> 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.<p>This seems like the real point of this paper, no? The rest seems like a joke.
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?
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.<p>I don't know if quantum computers exist, but I'm sure once they do, the people who build them will keep them secret.
My question is: how practical would it be to use a 1TB RSA key for average users? I assume that the size of cipher text would be somewhat depended on secret size.<p>The storage space and network bandwidth is not free.