Paper 2016/155 Original: eprint.iacr.org/2016/155 ↗
Cryptanalysis of Multi-Prime $\Phi$-Hiding Assumption
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.
- History
- 2016-02-18: last updated
- 2016-02-18: published
- Short URL
- https://ia.cr/2016/155
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}