**On the smallest ratio problem of lattice bases**

*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.

To the best of our knowledge, this is the first sound study of SRP. Our work provides a new perspective on both the quality limits of lattice reduction algorithms and complexity estimates of enumeration algorithms.

**Category / Keywords: **lattice reduction, lattice enumeration algorithms, smallest ratio problem

**Date: **received 29 Aug 2016, last revised 6 Sep 2016

**Contact author: **lijianwei2015 at amss ac cn

**Available format(s): **PDF | BibTeX Citation

**Note: **The paper was submitted to Information and Computation.

**Version: **20160907:140220 (All versions of this report)

**Short URL: **ia.cr/2016/847

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]