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