Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta:
Post-Quantum RSA
Abstract: This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today´s computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. 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. Initial pqRSA implementation results are provided.
