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.

  • $\begingroup$ In your modified problem, are the values $a_i$'s and $b$ known by the solver or is the linear combination secret? $\endgroup$ – Hilder Vítor Lima Pereira May 2 at 7:16
  • $\begingroup$ Both $a_i$ and $b$ are public and known to the solver. $\endgroup$ – user67451 May 3 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.

  • $\begingroup$ 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? $\endgroup$ – user67451 May 7 at 2:53
  • $\begingroup$ 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. $\endgroup$ – Hilder Vítor Lima Pereira May 7 at 7:19
  • $\begingroup$ Oh, of course, please don't forget to accept my answer if you judge it is acceptable. $\endgroup$ – Hilder Vítor Lima Pereira May 7 at 7:21

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.