**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 ]