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

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptography
Contact author(s)
jschanck @ uwaterloo ca
History
Short URL
https://ia.cr/2018/325

CC BY

BibTeX

@misc{cryptoeprint:2018/325,
author = {John M.  Schanck},
title = {Multi-power Post-quantum RSA},
howpublished = {Cryptology ePrint Archive, Paper 2018/325},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/325}},
url = {https://eprint.iacr.org/2018/325}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.