Paper 2016/847
On the smallest ratio problem of lattice bases
Jianwei Li
Abstract
Let $(\mathbf{b}_1, \ldots, \mathbf{b}_{n})$ be a lattice basis with GramSchmidt 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 NPhard 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 DadushRegevStephensDavidowitz (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)$.
Note: This is the full version of the work appeared in Proceedings of ISSAC ’21.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision.ISSAC 2021
 Keywords
 lattice reductionlattice enumeration algorithmssmallest ratio problem
 Contact author(s)
 lijianweisk @ sina com
 History
 20220318: last of 3 revisions
 20160907: received
 See all versions
 Short URL
 https://ia.cr/2016/847
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/847, author = {Jianwei Li}, title = {On the smallest ratio problem of lattice bases}, howpublished = {Cryptology ePrint Archive, Paper 2016/847}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/847}}, url = {https://eprint.iacr.org/2016/847} }