[Resource Topic] 2018/325: Multi-power Post-quantum RSA

Welcome to the resource topic for 2018/325

Multi-power Post-quantum RSA

Authors: John M. Schanck


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.

ePrint: https://eprint.iacr.org/2018/325

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .