Welcome to the resource topic for 2016/847
Title:
On the smallest ratio problem of lattice bases
Authors: Jianwei Li
Abstract:Let (\mathbf{b}_1, \ldots, \mathbf{b}_{n}) be a lattice basis with Gram-Schmidt orthogonalization (\mathbf{b}_1^{\ast}, \ldots, \mathbf{b}_{n}^{\ast}), the quantities \|\mathbf{b}_{1}\|/\|\mathbf{b}_{i}^{\ast}\| for i = 1, \ldots, n play important roles in analyzing lattice reduction algorithms and lattice enumeration algorithms. In this paper, we study the problem of minimizing the quantity \|\mathbf{b}_{1}\|/\|\mathbf{b}_{n}^{\ast}\| over all bases (\mathbf{b}_{1}, \ldots, \mathbf{b}_{n}) of a given n-dimensional lattice. We first prove that there exists a basis (\mathbf{b}_{1}, \ldots, \mathbf{b}_{n}) for any lattice L of dimension n such that \|\mathbf{b}_1\| = \min_{\mathbf{v} \in L\backslash\{\mathbf{0}\}} \|\mathbf{v}\|, \|\mathbf{b}_{1}\|/\|\mathbf{b}_{i}^{\ast}\| \leq i and \|\mathbf{b}_{i}\|/\|\mathbf{b}_{i}^{\ast}\| \leq i^{1.5} for 1 \leq i \leq n. This leads us to introduce a new NP-hard computational problem, that is, the smallest ratio problem (SRP): given an n-dimensional lattice L, find a basis (\mathbf{b}_{1}, \ldots, \mathbf{b}_{n}) of L such that \|\mathbf{b}_{1}\|/\|\mathbf{b}_{n}^{\ast}\| is minimal. The problem inspires the new lattice invariant \mu_{n}(L) = \min\{\|\mathbf{b}_1\|/\|\mathbf{b}_n^{\ast}\|: (\mathbf{b}_1, \ldots, \mathbf{b}_n) \textrm{ is a basis of } L\} and new lattice constant \mu_{n} = \max \mu_{n}(L) over all n-dimensional lattices L: both the minimum and maximum are justified. The properties of \mu_{n}(L) and \mu_{n} are discussed. We also present an exact algorithm and an approximation algorithm for SRP. This is the first sound study of SRP. Our work is a tiny step towards solving an open problem proposed by Dadush-Regev-Stephens-Davidowitz (CCC '14) for tackling the closest vector problem with preprocessing, that is, whether there exists a basis (\mathbf{b}_{1}, \ldots, \mathbf{b}_{n}) for any n-rank lattice such that \max_{1 \le i \le j \le n} \|\vec{b}_{i}^{\ast}\|/\vec{b}_{j}^{\ast}\| \le \textrm{poly}(n).
ePrint: https://eprint.iacr.org/2016/847
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .