The variant of remote set problem on lattices

Wenwen Wang; Kewei Lv; Jianing Liu

doi:10.1007/978-3-319-50011-9_10

The variant of remote set problem on lattices

Wenwen Wang, Kewei Lv, Jianing Liu

Computer Science and Engineering

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

1 Scopus citations

Abstract

In 2015, Haviv proposed the Remote Set Problem (RSP) on lattices and gave a deterministic algorithm to find a set containing a point which is O(√k/n) far from the lattice in ℓ_p norm for 2 ≤ p≤∞, where n is the lattice rank and k divides n. Inspired by it, we propose the variant of Remote Set Problem on Lattices (denoted by V-RSP) that only depends on parameter γ ≤ 1. We obtain that the complexity classes that V-RSP belong to with the change of parameter γ. Using some elementary tools, we can solve V-RSP that can find a set containing a point which is O(k/n) far from the lattice in any ℓ_p norm for 1 ≤ p≤∞. Furthermore, we also study relationships between ℓ₂ distance from a point to a lattice L and covering radius (ρ^(p)(L)), where ρ^(p)(L) is defined with respect to the ℓ_p norm for 1 ≤ p ≤ ∞, here, for p = ∞, our proof does not rely on Komlòs Conjecture.

Original language	English (US)
Title of host publication	Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings
Editors	Kwok-Yan Lam, Sihan Qing, Chi-Hung Chi
Publisher	Springer Verlag
Pages	124-133
Number of pages	10
ISBN (Print)	9783319500102
DOIs	https://doi.org/10.1007/978-3-319-50011-9_10
State	Published - 2016
Event	18th International Conference on Information and Communications Security, ICICS 2016 - Singapore, Singapore Duration: Nov 29 2016 → Dec 2 2016

Publication series

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

Other

Other	18th International Conference on Information and Communications Security, ICICS 2016
Country/Territory	Singapore
City	Singapore
Period	11/29/16 → 12/2/16

Bibliographical note

Funding Information:
This work was supported by National Natural Science Foundation of China (Grant No. 61272039).

Publisher Copyright:
© Springer International Publishing AG 2016.

Keywords

Equivalent norms
Hölder’s inequality
Lattice
The variant of remote set problem

Publisher link

10.1007/978-3-319-50011-9_10

Find It

Find It at U of M Libraries

Cite this

Wang, W., Lv, K., & Liu, J. (2016). The variant of remote set problem on lattices. In K.-Y. Lam, S. Qing, & C.-H. Chi (Eds.), Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings (pp. 124-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9977 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-50011-9_10

The variant of remote set problem on lattices. / Wang, Wenwen; Lv, Kewei; Liu, Jianing.
Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings. ed. / Kwok-Yan Lam; Sihan Qing; Chi-Hung Chi. Springer Verlag, 2016. p. 124-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9977 LNCS).

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

Wang, W, Lv, K & Liu, J 2016, The variant of remote set problem on lattices. in K-Y Lam, S Qing & C-H Chi (eds), Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9977 LNCS, Springer Verlag, pp. 124-133, 18th International Conference on Information and Communications Security, ICICS 2016, Singapore, Singapore, 11/29/16. https://doi.org/10.1007/978-3-319-50011-9_10

Wang W, Lv K, Liu J. The variant of remote set problem on lattices. In Lam KY, Qing S, Chi CH, editors, Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings. Springer Verlag. 2016. p. 124-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-50011-9_10

Wang, Wenwen ; Lv, Kewei ; Liu, Jianing. / The variant of remote set problem on lattices. Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings. editor / Kwok-Yan Lam ; Sihan Qing ; Chi-Hung Chi. Springer Verlag, 2016. pp. 124-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fe34380b9217449d9899ff69c3f87156,

title = "The variant of remote set problem on lattices",

abstract = "In 2015, Haviv proposed the Remote Set Problem (RSP) on lattices and gave a deterministic algorithm to find a set containing a point which is O(√k/n) far from the lattice in ℓp norm for 2 ≤ p≤∞, where n is the lattice rank and k divides n. Inspired by it, we propose the variant of Remote Set Problem on Lattices (denoted by V-RSP) that only depends on parameter γ ≤ 1. We obtain that the complexity classes that V-RSP belong to with the change of parameter γ. Using some elementary tools, we can solve V-RSP that can find a set containing a point which is O(k/n) far from the lattice in any ℓp norm for 1 ≤ p≤∞. Furthermore, we also study relationships between ℓ2 distance from a point to a lattice L and covering radius (ρ(p)(L)), where ρ(p)(L) is defined with respect to the ℓp norm for 1 ≤ p ≤ ∞, here, for p = ∞, our proof does not rely on Koml{\`o}s Conjecture.",

keywords = "Equivalent norms, H{\"o}lder{\textquoteright}s inequality, Lattice, The variant of remote set problem",

author = "Wenwen Wang and Kewei Lv and Jianing Liu",

note = "Funding Information: This work was supported by National Natural Science Foundation of China (Grant No. 61272039). Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 18th International Conference on Information and Communications Security, ICICS 2016 ; Conference date: 29-11-2016 Through 02-12-2016",

year = "2016",

doi = "10.1007/978-3-319-50011-9_10",

language = "English (US)",

isbn = "9783319500102",

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

publisher = "Springer Verlag",

pages = "124--133",

editor = "Kwok-Yan Lam and Sihan Qing and Chi-Hung Chi",

booktitle = "Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings",

}

TY - GEN

T1 - The variant of remote set problem on lattices

AU - Wang, Wenwen

AU - Lv, Kewei

AU - Liu, Jianing

N1 - Funding Information: This work was supported by National Natural Science Foundation of China (Grant No. 61272039). Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - In 2015, Haviv proposed the Remote Set Problem (RSP) on lattices and gave a deterministic algorithm to find a set containing a point which is O(√k/n) far from the lattice in ℓp norm for 2 ≤ p≤∞, where n is the lattice rank and k divides n. Inspired by it, we propose the variant of Remote Set Problem on Lattices (denoted by V-RSP) that only depends on parameter γ ≤ 1. We obtain that the complexity classes that V-RSP belong to with the change of parameter γ. Using some elementary tools, we can solve V-RSP that can find a set containing a point which is O(k/n) far from the lattice in any ℓp norm for 1 ≤ p≤∞. Furthermore, we also study relationships between ℓ2 distance from a point to a lattice L and covering radius (ρ(p)(L)), where ρ(p)(L) is defined with respect to the ℓp norm for 1 ≤ p ≤ ∞, here, for p = ∞, our proof does not rely on Komlòs Conjecture.

AB - In 2015, Haviv proposed the Remote Set Problem (RSP) on lattices and gave a deterministic algorithm to find a set containing a point which is O(√k/n) far from the lattice in ℓp norm for 2 ≤ p≤∞, where n is the lattice rank and k divides n. Inspired by it, we propose the variant of Remote Set Problem on Lattices (denoted by V-RSP) that only depends on parameter γ ≤ 1. We obtain that the complexity classes that V-RSP belong to with the change of parameter γ. Using some elementary tools, we can solve V-RSP that can find a set containing a point which is O(k/n) far from the lattice in any ℓp norm for 1 ≤ p≤∞. Furthermore, we also study relationships between ℓ2 distance from a point to a lattice L and covering radius (ρ(p)(L)), where ρ(p)(L) is defined with respect to the ℓp norm for 1 ≤ p ≤ ∞, here, for p = ∞, our proof does not rely on Komlòs Conjecture.

KW - Equivalent norms

KW - Hölder’s inequality

KW - Lattice

KW - The variant of remote set problem

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

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

U2 - 10.1007/978-3-319-50011-9_10

DO - 10.1007/978-3-319-50011-9_10

M3 - Conference contribution

AN - SCOPUS:85005959747

SN - 9783319500102

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

SP - 124

EP - 133

BT - Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings

A2 - Lam, Kwok-Yan

A2 - Qing, Sihan

A2 - Chi, Chi-Hung

PB - Springer Verlag

T2 - 18th International Conference on Information and Communications Security, ICICS 2016

Y2 - 29 November 2016 through 2 December 2016

ER -

The variant of remote set problem on lattices

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this