SIS与ISIS(非均匀SIS)的等价性

Question

我想知道这两个问题是否等同，即：

SIS_\alpha：给定A \in \mathbb{Z}_q^{n\times m}，查找e \in \mathbb{Z}_q^{m}，使Ae = 0和和\|e\| \le \alpha。

ISIS_\alpha：给定A \in \mathbb{Z}_q^{n\times m}, y \in \mathbb{Z}_q^{n}，找到e \in \mathbb{Z}_q^{m}，使得Ae = y和\|e\| \le \alpha。

我做了一些研究，并在文档的第二页找到了下面的引理10，声称对ISIS_\alpha的有效解决方案意味着对SIS_\alpha的有效解决方案，但是证据是不正确的，因为它没有显示出e' \neq e。

Answer 1

用A = [A_1 ~~ A_2]和A_1 \in \mathbb{Z}_q^{n\times m'}编写A_2 \in \mathbb{Z}_q^{n\times (m-m')}。

同样，e = (e_1 ~~ e_2)与e_1 \in \mathbb{Z}_q^{m'}和e_2 \in \mathbb{Z}_q^{m-m'}。

然后,

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

因此，给出SIS的一个实例，即n\times m矩阵A，如果您有一个甲骨文来解决ISIS，那么您可以按照上面的步骤编写A，示例一个简短的e_1，定义y := -A_1e_1 \bmod q，并使用甲骨文获得一个短的A_2e_2 = y \bmod q。

您的SIS解决方案将是e = (e_1 ~~ e_2)。