Cryptanalysis of Multi-Prime $\Phi$-Hiding Assumption

Jun Xu; Lei Hu; Santanu Sarkar; Xiaona Zhang; Zhangjie Huang; Liqiang Peng

Paper 2016/155

Cryptanalysis of Multi-Prime $\Phi$-Hiding Assumption

Jun Xu, Lei Hu, Santanu Sarkar, Xiaona Zhang, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Multi-Prime $\Phi$-Hiding Assumption Multi-Prime $\Phi$-Hiding Problem lattice LLL algorithm Coppersmith's technique Gauss algorithm
Contact author(s): xujun @ iie ac cn
History: 2016-02-18: received
Short URL: https://ia.cr/2016/155
License: CC BY

BibTeX

@misc{cryptoeprint:2016/155,
      author = {Jun Xu and Lei Hu and Santanu Sarkar and Xiaona Zhang and Zhangjie Huang and Liqiang Peng},
      title = {Cryptanalysis of Multi-Prime $\Phi$-Hiding Assumption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/155},
      year = {2016},
      url = {https://eprint.iacr.org/2016/155}
}