Incremental Algorithms for Lattice Problems

This paper describes the formal verification of NP-hardness reduction functions of two key problems relevant in algebraic lattice theory: the closest vector problem and the shortest vector problem, both in the infinity norm. The formalization uncovered a number of problems with the existing proofs in the literature. The paper describes how these problems were corrected in the formalization. The work was carried out in the proof assistant Isabelle.

We give short and simple proofs of what seem to be folklore results: * the maximum cardinality of the intersection of a lattice cube with an affine subspace; * the minimum number of affine subspaces needed to cover a lattice cube.

It is shown that, given any $k$-dimensional lattice $\Lambda$, there is a lattice sequence $\Lambda_w$, $w\in \mathbb Z$, with sub-orthogonal lattice $\Lambda_o \subset \Lambda$, converging to $\Lambda$ (unless equivalence), also we discuss the conditions for faster convergence.

The Korkine-Zolotareff (KZ) reduction is one of the often used reduction strategies for lattice decoding. In this paper, we first investigate some important properties of KZ reduced matrices. Specifically, we present a linear upper bound on the Hermit constant which is around $\frac{7}{8}$ times of the existing sharpest linear upper bound, and an upper bound on the KZ constant which is {\em polynomially} smaller than the existing sharpest one. We also propose upper bounds on ...

We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $\delta$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq \delta \leq n^{O(1)}$. This is the range of approximation factors most relevant for cryptography.

In this paper we review the technique to solve the CVP based on dual HKZ-bases by J. Bloemer. The technique is based on the transference theorems given by Banaszczyk which imply some necessary conditions on the coefficients of the closest vectors with respect to a basis whose dual is HKZ reduced. Recursively, starting with the last coefficient, intervals of length i can be derived for the i-th coefficient of any closest vector. This leads to n! candidates for closest vectors....

Many challenging Graver bases computations, like for multi-way tables in statistics, have a highly symmetric problem structure that is not exploited so far computationally. In this paper we present a Graver basis algorithm for sublattices of $\Z^n$ that exploits existing symmetry.

Lattice data structures are space efficient and cache-suitable data structures. The basic searching, insertion, and deletion operations are of time complexity $O(\sqrt{N})$. We give a jump searching algorithm of time complexity $O(J(L)\log(N))$, where $J(L)$ is the jump factor of the lattice. $J(L)$ approaches $4$ when the degree of sortedness of the lattice approaches $\sqrt{N}$. A sorting procedure of time complexity $O(\sqrt{N})$ that can be used, during the system idle ti...

Lattices defined as modules over algebraic rings or orders have garnered interest recently, particularly in the fields of cryptography and coding theory. Whilst there exist many attempts to generalise the conditions for LLL reduction to such lattices, there do not seem to be any attempts so far to generalise stronger notions of reduction such as Minkowski, HKZ and BKZ reduction. Moreover, most lattice reduction methods for modules over algebraic rings involve applying traditi...

A lattice in the Euclidean space is standard if it has a basis consisting vectors whose norms equal to the length in its successive minima. In this paper, it is shown that with the $L^2$ norm all lattices of dimension $n$ are standard if and only if $n\leqslant 4$. It is also proved that with an arbitrary norm, every lattice of dimensions 1 and 2 is standard. An example of non-standard lattice of dimension $n\geqslant 3$ is given when the lattice is with the $L^1$ norm.