**Multi-power Post-quantum RSA**

*John M. Schanck*

**Abstract: **Special purpose factoring algorithms have discouraged the adoption of multi-power RSA, even in a post-quantum setting. We revisit the known attacks and find that a general recommendation against repeated factors is unwarranted. We find that one-terabyte RSA keys of the form $n = p_1^2p_2^3p_3^5p_4^7\cdots p_i^{\pi_i}\cdots p_{20044}^{225287}$ are competitive with one-terabyte RSA keys of the form $n = p_1p_2p_3p_4\cdots p_i\cdots p_{2^{31}}$. Prime generation can be made to be a factor of 100000 times faster at a loss of at least $1$ but not more than $17$ bits of security against known attacks. The range depends on the relative cost of bit and qubit operations under the assumption that qubit operations cost $2^c$ bit operations for some constant $c$.

**Category / Keywords: **public-key cryptography / post-quantum cryptography

**Date: **received 6 Apr 2018

**Contact author: **jschanck at uwaterloo ca

**Available format(s): **PDF | BibTeX Citation

**Version: **20180409:121526 (All versions of this report)

**Short URL: **ia.cr/2018/325

[ Cryptology ePrint archive ]