How to estimate the hardness of SIS instances?

Question

The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}$ such that $A\mathbf{x} = \mathbf{0} \mod q$ and $\Vert \mathbf{x} \Vert_2 < \beta$. This problem is at least as hard as the Shortest Independent Vectors Problem (SIVP) with approximation factor $\tilde{O}(\beta\sqrt{n})$ in $n$-dimensional lattices. Several proposed cryptosystems rely on SIS, most notable Ajtai's function in the original paper that defined the problem (link), the SWIFFT hash function (link), and several signature schemes (link) (link) (link).

However, I am confused about estimating the security offered by these cryptosystems in terms of the computational cost of a successful attack. Very few sources actually present a hardness estimate and those that do consider the appropriate root Hermite factor $\delta$ rather than a count of arithmetic operations.

For instance, the chapter by Micciancio and Regev (link) presents the following argument: There is an optimal number of columns of $A$ to take into account when attacking the SIS problem using lattice-based algorithms (presumably BKZ 2.0). Use too few columns and short lattice points might be too difficult to find (if they exist at all); use too many and the lattice will be too large. This minimum is found for $m = \sqrt{n \log q \, / \log \delta}$; at this point the average length of lattice points that can be computed in a "reasonable amount of time" is $2^{2\sqrt{n \log q \log \delta}}$, where $\delta$ is no less than $1.01$. So by requiring that $\beta < 2^{2\sqrt{n \log q \log \delta}}$, one guarantees that the SIS instance cannot be solved in a reasonable amount of time.

A similar treatment of the hardness of SIS instances is given by Section 3.2 of Lyubashevsky's 2012 signature scheme (link), which uses $\delta = 1.007$ for setting parameters. Micciancio and Peikert's 2011 signature scheme (link) mentions that setting $\delta \leq 1.007$ corresponds to $2^{46}$ core-years of lattice-redution, which is about $2^{100}$ cycles on a 1.0 GigaHerz CPU.

I have several questions regarding this. What makes it impossible or difficult to translate the parameters $(m,n,q,\beta)$ into an attack runtime estimate, and what is the significance of the root Hermite factor $\delta$ in this context? Given that $\delta$ is a useful tool, how does one translate between $\delta$ and attack complexity (in number of bits of security)? Given a target short vector length and lattice parameters, how to estimate the time before BKZ 2.0 finds a lattice point of this length? (Or, if this is not a sensible question, why doesn't this runtime matter?)

Answer 1

The value $\delta$ characterizes, how short a vector you can expect to find using an algorithm (typically used in the context of lattice reduction).

In particular, for a vector $\mathbf{v} \in \Lambda$ (where $\Lambda$ is a lattice), the associated $\delta$ (often also denoted by $\delta_0$) is defined to be such that $\| \mathbf{v} \| = \delta^n \det(\Lambda)^{1/n}$.

For those don't know how to take the determinant of lattices, see page 4 of this introduction lecture in the course "Lattices in Computer Science" given by Oded Regev.

This was introduced in GN08 in the context for lattice reduction, because it was observed that the $\delta$ for output vectors returned by lattice reduction converges (for growing $n$) to a constant for every type and parametrization of reduction.

Generally, reduction algorithms are parameterized and allow for a trade-off between output quality (i.e. size of $\delta$) and running time. The exact trade-off is still a subject to research, especially as reduction algorithms continue to improve, but a good summary of the state-of-the-art is given in APS15 (Section 3). Roughly speaking, translating a SIS instance to a $\delta$ required to break it, is relatively easy, but translating the $\delta$ to a running time is not as straight-forward. The reason is that the behavior of lattice reduction, the most efficient approximation algorithms to date, is not very well understood and the community has not converged on a model yet.

One issue with lattice reduction is that it uses an exact SVP solver (in lower dimension). In order to instantiate these solvers there are different algorithms, some behaving better in practice and others being asymptotically more efficient. This makes it hard to analyze exactly, how long it will take to obtain a short vector of quality $\delta$.