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. 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)$.

Note: This is the full version of the work appeared in Proceedings of ISSAC ’21.

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
2022-03-18: last of 3 revisions
See all versions
Short URL
https://ia.cr/2016/847

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

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.