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 AssumptionMulti-Prime $\Phi$-Hiding ProblemlatticeLLL algorithmCoppersmith's techniqueGauss algorithm
Contact author(s)
xujun @ iie ac cn
History
2016-02-18: received
Short URL
https://ia.cr/2016/155
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.