## 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 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 | |

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