2
$\begingroup$

I would like to know whether these two problems are equivalent or not, namely:

$SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \le \alpha$.

$ISIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}, y \in \mathbb{Z}_q^{n}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = y$ and $\|e\| \le \alpha$.

I did some research and found the following Lemma 10 at second page of the document claiming that an efficient solution to $ISIS_\alpha$ implies an efficient solution to $SIS_\alpha$ but the proof is incorrect since it is not showing that $e' \neq e$.

$\endgroup$
2
  • 1
    $\begingroup$ I would guess it's just probabilistic. For example, if $q$ is prime, then the kernel of $A$ is $q^{n-m}$, so there will be that many pre-images of $y$. Hence, the ISIS solver returns a distinct pre-image of $y$ with probability $1/q^{n-m}$. If $q^{n-m}$ is small, then I think it is easy to search exhaustively for small vectors and both SIS and ISIS are easy; if $q^{n-m}$ is large, the reduction works with high probability. $\endgroup$
    – Sam Jaques
    Dec 22 '20 at 20:01
  • $\begingroup$ @SamJaques Actually, not all vectors in the kernel are solutions, because there is also a restriction on the norm... But there must be enough solutions anyway to assume that the oracle returns $e$ different from $e'$. $\endgroup$ Dec 23 '20 at 7:00
1
$\begingroup$

Write $A = [A_1 ~~ A_2]$ with $A_1 \in \mathbb{Z}_q^{n\times m'}$ and $A_2 \in \mathbb{Z}_q^{n\times (m-m')}$.

Likewise, $e = (e_1 ~~ e_2)$ with $e_1 \in \mathbb{Z}_q^{m'}$ and $e_2 \in \mathbb{Z}_q^{m-m'}$.

Then,

$$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$

So, given an instance of SIS, that is, an $n\times m$ matrix $A$, if you have an oracle to solve ISIS, then you can write $A$ per blocks as above, sample a short $e_1$, define $y := -A_1e_1 \bmod q$, and use the oracle to obtain a short $e_2$ such that $A_2e_2 = y \bmod q$.

Your SIS solution will then be $e = (e_1 ~~ e_2)$.

$\endgroup$
3
  • $\begingroup$ The reduction can be made simpler by taking the last column of the input SIS instance $$A$$ to be the ISIS target $$y$$, and the rest of the columns as the ISIS matrix $$A’$$. Then any ISIS solution $$x$$ to $$A’ x=y$$ yields an SIS solution $$(x, -1)$$ for $$A$$. $\endgroup$ Dec 23 '20 at 1:02
  • $\begingroup$ Thank you for the explanation. Does this also imply that the reverse direction(i.e. efficient SIS => efficient ISIS) is also true? $\endgroup$
    – crypton00b
    Dec 23 '20 at 11:53
  • $\begingroup$ Yes, for similar but not quite the same reasons. You can append the ISIS target column onto the ISIS matrix to get an SIS matrix, but there is no guarantee that the adversary’s SIS solution will have a -1 for that column. However, you can “guess” the position and value of a nonzero coordinate in the SIS solution, and divide the ISIS target column by that guess before inserting it at that position. This requires the modulus not to have any too-small factors. This restriction can be relaxed by assuming wlog that the SIS solution is primitive, i.e., it is not evenly divisible by any $k>1$. $\endgroup$ Dec 23 '20 at 13:12

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.