The variant of remote set problem on lattices

Wenwen Wang, Kewei Lv, Jianing Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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òs Conjecture.

Original languageEnglish (US)
Title of host publicationInformation and Communications Security - 18th International Conference, ICICS 2016, Proceedings
EditorsKwok-Yan Lam, Sihan Qing, Chi-Hung Chi
PublisherSpringer Verlag
Pages124-133
Number of pages10
ISBN (Print)9783319500102
DOIs
StatePublished - 2016
Event18th International Conference on Information and Communications Security, ICICS 2016 - Singapore, Singapore
Duration: Nov 29 2016Dec 2 2016

Publication series

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

Other

Other18th International Conference on Information and Communications Security, ICICS 2016
CountrySingapore
CitySingapore
Period11/29/1612/2/16

Keywords

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

Fingerprint Dive into the research topics of 'The variant of remote set problem on lattices'. Together they form a unique fingerprint.

Cite this