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 .