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
-
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}
}
