# Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $$f_A(s)$$=$$As$$, where $$A$$ is a fixed, randomly-chosen matrix in $$\mathbb{Z}_q^{r \times n}$$, it is hard to find elements $$s \in \mathbb{Z}_q^{n}$$ with some bounded norm $$||s||\leq B$$ s.t. $$f_A(s)$$=0 for random $$A$$.

If I modify the above definition as follows: consider a function $$f_A(\{s_i\})$$=$$\sum_{i=1}^{b} a_iAs_i$$, where $$a_i \in \mathbb{Z}_q$$ are random and $$b$$ is an integer that is no larger than $$|q|$$, it is hard to find $$\{s_i\} \in (\mathbb{Z}_q^{n})^{b}$$ with bounded norm $$||s_i||\leq B$$ s.t. $$f_A(\{s_i\})$$=0 for random $$A$$ as chosen in the original SIS problem. Intuitively there seems to be a connection between these two problems. Can I reduce the hardness of this new problem to that of the aforementioned SIS problem? Thank you in advance.

• In your modified problem, are the values $a_i$'s and $b$ known by the solver or is the linear combination secret? – Hilder Vitor Lima Pereira May 2 '19 at 7:16
• Both $a_i$ and $b$ are public and known to the solver. – user67451 May 3 '19 at 2:58

I would say that, in general, your problem is actually easier than $$SIS$$.

Let's call your problem $$LSIS_{n, q, B, m, b}$$. First of all, notice that if you can find a solution $$s$$ to $$SIS_{n, q, B, m}$$, than $$s_1 = s_2 = s_3 = ... = s_b = s$$ is a solution to $$LSIS_{n, q, B, m, b}$$, which already means that your problem cannot be harder than SIS.

Furthermore, notice that for fixed parameters $$n, q, B, m,$$ and $$b$$, there are several easy instances for $$LSIS$$. Some examples,

• if some $$a_i$$ is equal to some $$a_j$$, then $$s_i = -s_j = (1, 0, 0, ..., 0)$$ and $$s_k = 0$$ for $$k \not \in \{i, j\}$$ is a very short solution to your problem;
• if there is short pair $$a_i \ge a_j$$ such that $$B \ge a_i$$, then $$s_i = a_j\cdot (1, 0, 0, ..., 0)$$, $$s_j = -a_i\cdot (1, 0, 0, ..., 0)$$, and $$s_k = 0$$ is a solution to your problem, since $$||s_i|| \le ||s_j|| \le a_i \le B$$;
• if there is a pair $$(a_i, a_j)$$ such that $$a_i^{-1}$$ and $$a_j^{-1}$$ are small, then $$s_i = a_i^{-1}\cdot(1, 0, 0, ..., 0)$$, $$s_j = -a_j^{-1}\cdot(1, 0, 0, ..., 0)$$, and and $$s_k = 0$$ is a solution to your problem.

Notice that for $$b = 2$$, if you choose the values $$a_1$$ and $$a_2$$ uniformly at random from $$\mathbb{Z}_q$$, then that first easy case will already appear with probability $$1/q$$, which means that if $$q$$ is polynomially big in $$n$$, then a random instance of your problem can be solved trivially with non-negligible probability. But $$SIS$$ is hard in average for $$q = poly(n)$$. Therefore, at least for these parameters, you cannot reduce $$SIS$$ to an average-case version of your problem.

• Thanks a lot for your answer. I wonder what I can say about the security of the following question: $f_{a, A}(s)$=$aAs$, where $A$ are given as in SIS problem and a NON-invertible $a$ is randomly chosen from $\mathbb{Z}_q$ and public. It seems obvious if $a$ is invertible, then the hardness of this question is equal to that of SIS, since if we can find a short $s$ such that $aAs=0$, then $s$ is the solution to $As=0$ when $a^{-1}$ is left-multiplied with both sides of this equation. But this argument doesn't apply here. I wonder whether we can somehow apply the leftover hash lemma here? – user67451 May 7 '19 at 2:53
• At first glance, I would just say that it is highly dependent on the number and size of prime factors of $q$. But I don't know how to proceed with an analysis now. I suggest that you create new question to ask this, so that other users can also see it and maybe help you. – Hilder Vitor Lima Pereira May 7 '19 at 7:19
• Oh, of course, please don't forget to accept my answer if you judge it is acceptable. – Hilder Vitor Lima Pereira May 7 '19 at 7:21