We establish the direct connection between CRP (Covering Radius Problem) and other lattice problems. We first prove that there is a polynomial-time rank-preserving reduction from approximating CRP to BDD ρ (Covering Bounded Distance Decoding Problem). Furthermore, we show that there are polynomial-time reductions from BDD ρ to approximating CVP (Closest Vector Problem) and SIVP (Shortest Independent Vector Problem), respectively. Hence, CRP reduces to CVP and SIVP under deterministic polynomial-time reductions.
|Original language||English (US)|
|Title of host publication||Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings|
|Editors||Sihan Qing, Dongmei Liu, Chris Mitchell, Liqun Chen|
|Number of pages||10|
|State||Published - 2018|
|Event||19th International Conference on Information and Communications Security, ICICS 2017 - Beijing, China|
Duration: Dec 6 2017 → Dec 8 2017
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||19th International Conference on Information and Communications Security, ICICS 2017|
|Period||12/6/17 → 12/8/17|
Bibliographical noteFunding Information:
Acknowledgements. This work was supported by National Natural Key R&D Program of China (Grant No. 2017YFB0802502), the Science and Technology Plan Projects of University of Jinan (Grant No. XKY1714), the Doctoral Initial Foundation of the University of Jinan (Grant No. XBS160100335), the Social Science Program of the University of Jinan (Grant No. 17YB01).
© Springer International Publishing AG, part of Springer Nature 2018.
- Covering Bounded Distance Decoding Problem
- Covering Radius Problem
- Polynomial time reductions