The reductions for the approximating covering radius problem

Wenwen Wang; Kewei Lv

doi:10.1007/978-3-319-89500-0_5

The reductions for the approximating covering radius problem

Wenwen Wang, Kewei Lv

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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
Publisher	Springer Verlag
Pages	65-74
Number of pages	10
ISBN (Print)	9783319894997
DOIs	https://doi.org/10.1007/978-3-319-89500-0_5
State	Published - 2018
Event	19th International Conference on Information and Communications Security, ICICS 2017 - Beijing, China Duration: Dec 6 2017 → Dec 8 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10631 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	19th International Conference on Information and Communications Security, ICICS 2017
Country/Territory	China
City	Beijing
Period	12/6/17 → 12/8/17

Bibliographical note

Funding 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).

Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.

Keywords

Covering Bounded Distance Decoding Problem
Covering Radius Problem
Lattice
Polynomial time reductions

Publisher link

10.1007/978-3-319-89500-0_5

Find It

Find It at U of M Libraries

Cite this

Wang, W., & Lv, K. (2018). The reductions for the approximating covering radius problem. In S. Qing, D. Liu, C. Mitchell, & L. Chen (Eds.), Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings (pp. 65-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10631 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-89500-0_5

The reductions for the approximating covering radius problem. / Wang, Wenwen; Lv, Kewei.
Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. ed. / Sihan Qing; Dongmei Liu; Chris Mitchell; Liqun Chen. Springer Verlag, 2018. p. 65-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10631 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Wang, W & Lv, K 2018, The reductions for the approximating covering radius problem. in S Qing, D Liu, C Mitchell & L Chen (eds), Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10631 LNCS, Springer Verlag, pp. 65-74, 19th International Conference on Information and Communications Security, ICICS 2017, Beijing, China, 12/6/17. https://doi.org/10.1007/978-3-319-89500-0_5

Wang W, Lv K. The reductions for the approximating covering radius problem. In Qing S, Liu D, Mitchell C, Chen L, editors, Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. Springer Verlag. 2018. p. 65-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-89500-0_5

Wang, Wenwen ; Lv, Kewei. / The reductions for the approximating covering radius problem. Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. editor / Sihan Qing ; Dongmei Liu ; Chris Mitchell ; Liqun Chen. Springer Verlag, 2018. pp. 65-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a68c2d670c6842228d2047bc5f9b39da,

title = "The reductions for the approximating covering radius problem",

abstract = "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.",

keywords = "Covering Bounded Distance Decoding Problem, Covering Radius Problem, Lattice, Polynomial time reductions",

author = "Wenwen Wang and Kewei Lv",

note = "Funding 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). Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 19th International Conference on Information and Communications Security, ICICS 2017 ; Conference date: 06-12-2017 Through 08-12-2017",

year = "2018",

doi = "10.1007/978-3-319-89500-0_5",

language = "English (US)",

isbn = "9783319894997",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "65--74",

editor = "Sihan Qing and Dongmei Liu and Chris Mitchell and Liqun Chen",

booktitle = "Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings",

}

TY - GEN

T1 - The reductions for the approximating covering radius problem

AU - Wang, Wenwen

AU - Lv, Kewei

N1 - Funding 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). Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Covering Bounded Distance Decoding Problem

KW - Covering Radius Problem

KW - Lattice

KW - Polynomial time reductions

UR - http://www.scopus.com/inward/record.url?scp=85045967393&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045967393&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-89500-0_5

DO - 10.1007/978-3-319-89500-0_5

M3 - Conference contribution

AN - SCOPUS:85045967393

SN - 9783319894997

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 65

EP - 74

BT - Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings

A2 - Qing, Sihan

A2 - Liu, Dongmei

A2 - Mitchell, Chris

A2 - Chen, Liqun

PB - Springer Verlag

T2 - 19th International Conference on Information and Communications Security, ICICS 2017

Y2 - 6 December 2017 through 8 December 2017

ER -

The reductions for the approximating covering radius problem

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this