格中決策 SIS 與剩餘雜湊引理之間的關係
Regev密碼系統的語義安全$$ Reg05 $$基於 LWE 假設和剩餘雜湊引理。這個引理意味著因為 $ m \approx (n+1)\log q $ 足夠大，所以對於製服 $ A\in \mathbb{Z}_q^{(n+1)\times m} $ 並且均勻隨機 $ x \in {0,1 }^m $ ， 期限 $ Ax\in \mathbb{Z}_q^{n+1} $ 接近均勻。
現在，我有點困惑。我認為這個引理與決策 SIS 問題的難度之間沒有區別。我認為條件 $ m $ 也是為了能夠保證存在相應 SIS 問題的解決方案（因此擁有該問題的正確版本）。
有人可以解釋一下嗎？
剩餘的雜湊引理（LHL）說 $ (A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)} $ 非常接近於均勻隨機。特別是，這意味著對於均勻隨機 $ (A,u) $ , 存在解 $ x \in {0,1}^m $ 至 $ Ax=u $ 以非常高的機率。因為如果不是，很大一部分 $ u $ 值不會接受任何解決方案，因此分佈 $ Ax $ 不會接近制服，因為它永遠不會產生任何這些 $ u $ 價值觀。（事實上，大多數 $ u $ 通常會有很多解決方案。）
以上所有內容都是無條件的——我們不依賴任何關於問題是否困難的假設，我們只是對機率做出陳述。
“決策 SIS 問題”不是一個標準概念，因為它沒有那麼有意義。如果要定義它，問題將要求區分 $ (A,u=Ax) $ 並且均勻隨機 $ (A,u) $ . 但是通過以上我們知道這是不可能的：這兩個分佈非常接近，因此無法區分它們。
計算SIS問題（在其非均勻版本中）要求，給定均勻隨機 $ (A,u) $ ,找到一些短的（例如，二進制） $ x $ 這樣 $ Ax=u $ . 再次，選擇 $ m $ 是否存在解決方案的機率非常高；計算問題是我們是否可以有效地找到解決方案。
SIS 問題被認為是困難的，這要歸功於大量的支持證據（例如，從最壞情況的格子問題中減少）。但是，我們不能排除SIS實際上很容易的可能性，只是我們還沒有找到一個有效的算法來解決它。然而，即使 SIS 很容易，也不會與上述任何機率陳述相矛盾；這只是意味著我們可以在可能存在的幾種解決方案中有效地找到解決方案。