Cryptology ePrint Archive: Report 2018/325

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 ]