SIS和ISIS的等價性（Inhomogeneous SIS）
我想知道這兩個問題是否等價，即：
$ 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 $ .
寫 $ 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 $ , 並使用 oracle 獲得一個短 $ e_2 $ 這樣 $ A_2e_2 = y \bmod q $ .
您的 SIS 解決方案將是 $ e = (e_1 ~~ e_2) $ .