Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
The Variant of Remote Set Problem on Lattices
verfasst von : Wenwen Wang, Kewei Lv, Jianing Liu
Erschienen in: Information and Communications Security
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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(\sqrt{k/n})\) far from the lattice in \(\ell _{p}\) norm for \(2\le p\le \infty \), 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 \(\gamma \le 1\). We obtain that the complexity classes that \(V-RSP \) belong to with the change of parameter \(\gamma \). 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 \(\ell _{p}\) norm for \(1\le p\le \infty \). Furthermore, we also study relationships between \(\ell _{2}\) distance from a point to a lattice \(\varvec{\mathcal {L}}\) and covering radius (\(\rho ^{(p)}(\varvec{\mathcal {L}})\)), where \(\rho ^{(p)}(\varvec{\mathcal {L}})\) is defined with respect to the \(\ell _{p}\) norm for \(1\le p\le \infty \), here, for \(p=\infty \), our proof does not rely on Komlós Conjecture.