# SIS without the modulus

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.

• I would be very careful with an assumption like this, namely because LWE without the modulus is easy.
– Mark
Jul 9 '21 at 6:22
• 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.
– AAA
Jul 9 '21 at 16:12
• 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.
– Mark
Jul 9 '21 at 21:34
• 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. Jul 11 '21 at 16:53
• @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
– AAA
Jul 12 '21 at 5:44

## 1 Answer

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.