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