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

Question

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.

Answer 1

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.