Cryptanalysis of Multi-Prime Φ-Hiding Assumption.
Jun Xu, Lei Hu, Santanu Sarkar, Xiaona Zhang, Zhangjie Huang, Liqiang Peng · IACR Cryptology ePrint Archive · 2016
In Crypto 2010, Kiltz, O’Neill and Smith used m-prime RSA modulus N with m ≥ 3 for constructing lossy RSA. The security of the proposal is based on the Multi-Prime Φ-Hiding Assumption. In this paper, we propose a heuristic algorithm based on the HerrmannMay lattice method (Asiacrypt 2008) to solve the Multi-Prime Φ-Hiding Problem when prime e > N 2 3m . Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime e > N 2 3m − 1 4m2 . These two results are verified by our experiments. Our bounds are better than the existing works.