[Cryptography] "Post-quantum RSA"

[Jerry Leichter]

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

The proposed parameters lives in a curious area somewhere between theory and practice.  It isn't "theory" because it can't exclude the possibility of incrementally faster quantum algorithms for factoring that would destroy the tradeoffs.  (Then again, the same could be said of traditional pre-quantum RSA!).  On the other hand, it's not really practical because the recommended key sizes are around a terabyte - and they estimate an encryption/decryption time of about 5 days.

Still, an interesting exploration of limits.

Oh - the authors include Daniel Bernstein and Nadia Heninger. :-)

                                                        -- Jerry