Paper 2016/155

Cryptanalysis of Multi-Prime Φ-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 m3 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 Herrmann-May lattice method (Asiacrypt 2008) to solve the Multi-Prime Φ-Hiding Problem when prime e>N23m. Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime e>N23m14m2. 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 -Hiding AssumptionMulti-Prime -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.