Post-quantum RSA
THIS PAPER IS:<p>a nice, thought-provoking paper that is nevertheless <i>purely speculative</i>, and also more than a little tongue-in-cheek in parts. (Note that one of the keywords is &quot;Make RSA Great Again&quot;.) It&#x27;s basically pointing out that there is a small gap between the costs of legitimately using RSA and factoring via Shor&#x27;s algorithm. With truly massive keys, this gap can be exploited to provide concrete security guarantees for RSA even in the presence of fast quantum computers.<p>THIS PAPER IS NOT:<p>a revolutionary new quantum factoring algorithm. They show how to apply quantum Grover search to a particular step of a known factorization algorithm based on elliptic curves.<p>QUANTUM COMPUTING DOES:<p>break public-key cryptosystems based on the hardness of factoring and finding discrete logarithms. Additionally,
it gives a quadratic speedup in generic search problems (via Grover search) which effectively halves the key size of symmetric encryption schemes and yields faster algorithms for things like finding collisions in hash functions.<p>QUANTUM COMPUTING (PROBABLY) DOES NOT:<p>break all asymmetric cryptography. There is no known proof of this, but it&#x27;s widely believed that asymmetric cryptosystems based on different hardness assumptions are not vulnerable to (non-generic) attacks by quantum computers.