3
$\begingroup$

Consider the following modification to the Short Integer Solution (SIS) problem:

Let $n$ be an integer and $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ be functions of $n$. Sample a uniform $A\gets[-\alpha,\alpha]^{n\times m}$. The task is to compute "short" vector $e\in\mathbb{Z}^m$ in the kernel of $A$. That is:

  1. $|e| < \beta$.
  2. $A.e=0^n$. Here, equality holds over the integers

The usual version of SIS is the same as above, except where $A.e=0^n$ holds mod $q$, and $q=2\alpha+1$ (so that $A$ is uniform in $\mathbb{Z}_q^{n\times m}$). This variant removes the modulus.

Question: Are there any non-trivial hardness/easiness results for this version of SIS? What settings of parameters are easy, and which (if any) can be proved hard based on worse-case lattice problems, as in the usual version of SIS?

Trivial attack: There is an trivial algorithm in the case where $\beta$ is huge. You can compute a kernel vector over the integers by taking minors of the matrix $A$. These minors, and hence the kernel vector, can be easily upper bounded by $(\alpha n)^{O(n)}$. So in the regime $\beta= (\alpha n)^{O(n)}$, there is a trivial attack.

What I'm most curious about is the case where $\alpha,\beta$ are polynomial in $n$. Are there any attacks here, or can any hardness be shown?


I picked the distribution for $A$ above to give a concrete problem. But I'd also be interested in other distributions on $A$. For example, what if the entries of $A$ are discrete Gaussians, etc?


One can also consider an inhomogeneous version of this SIS variant, where $A.e=u$, for some vector $u$ (again, without a modulus). We have to be careful, though as for large $u$ there won't be a solution. Maybe we restrict to random $u\in\{0,1\}$, or in $[-\gamma,\gamma]^n$. I'd also be interested if anything can be said about this problem as well, besides the straightforward adaptation of the trivial attack from above.

$\endgroup$
5
  • $\begingroup$ I would be very careful with an assumption like this, namely because LWE without the modulus is easy. $\endgroup$
    – Mark
    Jul 9 at 6:22
  • $\begingroup$ I certainly agree that it would be dangerous to assume hardness without any formal justification. At the same time, I'm not aware of any actual attacks, besides the trivial attack mentioned. $\endgroup$
    – AAA
    Jul 9 at 16:12
  • $\begingroup$ I have linked to an attack on a closely related problem in the same setting. It would not be surprising to me if one could potentially extend the attack to SIS, which is why I linked you the paper. $\endgroup$
    – Mark
    Jul 9 at 21:34
  • $\begingroup$ The LWE hardness reduction constrains the modulus as $q \le 2^{O(n)}$, whereas the SIS reduction constrains it as $q \ge \beta \cdot O(n)$. Sufficiently large $q$ will be equivalent to the problem over the integers, I imagine. $\endgroup$ Jul 11 at 16:53
  • $\begingroup$ @Samuel Neves: the problem is that SIS is usually defined where the matrix is random over $\mathbb{Z}_q$. So as $q$ scales up, so do the entries of $A$. This means $A.e$ will almost certainly have wrap-around mod $q$. So I don't immediately see how to use this for my problem $\endgroup$
    – AAA
    Jul 12 at 5:44
1
$\begingroup$

It turns out some version of the problem is actually as hard as SIS. Concretely, I claim that the version where $A$ is a random binary matrix and $\beta$ is polynomial will be hard, assuming SIS is hard for an appropriate choice of parameters.

Let $q=2^\ell$ be a power of 2 that is sufficiently larger than $\beta$. Let $n'=n/\ell$ (we assume $n$ divisible by $\ell$ for simplicity). Then consider a SIS instance with parameters $n',m,q,\beta$: given a random matrix $A\in\mathbb{Z}_q^{n'\times m}$, the goal is to find a non-zero vector $e\in\mathbb{Z}^m$ such that $A\cdot e\equiv 0\pmod q$ and $|e|<\beta$.

We reduce to the stated modulus-free problem as follows. Let $A_i\in\{0,1\}^{n'\times m}$ be the matrix where we replace each entry in $A$ by the $i$th bit of that entry. Then let $A'\in\{0,1\}^{n\times m}$ be the matrix obtained by stacking all of the $A_i$ on top of each other.

If we could solve modulus-free SIS for $A'$, this would give us a vector $e\neq 0$ such that $A'\cdot e=0$ (over the integers) and $|e|<\beta$. But then I claim that $A\cdot e = 0$. Indeed, each entry of $A$ is just a linear combination of entries in the corresponding column of $A'$. Therefore, each entry of $A\cdot e$ is just a linear combination of the entries in $A'\cdot e$, and is therefore 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.