Cryptology ePrint Archive: Report 2016/155
Cryptanalysis of Multi-Prime $\Phi$-Hiding Assumption
Jun Xu and Lei Hu and Santanu Sarkar and Xiaona Zhang and Zhangjie Huang and Liqiang Peng
Abstract: In Crypto 2010, Kiltz, O'Neill and Smith used $m$-prime RSA modulus $N$ with $m\geq 3$ for constructing lossy RSA. The security of the proposal
is based on the Multi-Prime $\Phi$-Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lattice method (Asiacrypt 2008) to solve the Multi-Prime $\Phi$-Hiding Problem when prime $e>N^{\frac{2}{3m}}$. Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime $e>N^{\frac{2}{3m}-\frac{1}{4m^2}}$. These two results are verified by our experiments. Our bounds are better than the existing works.
Category / Keywords: public-key cryptography / Multi-Prime $\Phi$-Hiding Assumption, Multi-Prime $\Phi$-Hiding Problem, lattice, LLL algorithm, Coppersmith's technique, Gauss algorithm
Date: received 17 Feb 2016
Contact author: xujun at iie ac cn
Available format(s): PDF | BibTeX Citation
Version: 20160218:220809 (All versions of this report)
Short URL: ia.cr/2016/155
[ Cryptology ePrint archive ]