矩陣 A 與 SIS 中的格空間 L 有什麼關係？
是矩陣 $ A= (b_1|,…,|b_m) $ 其中B = $ (b_1,…,b_m) $ 是格子空間的基礎， $ L $ （乙）？不確定答案是否微不足道，但是當 SIS 的定義似乎不包含格子時，我很難看到 SIS 是如何成為格子難題的。
在此之後，對向量的限制 $ x $ $ \leq \beta $ . 在哪裡做 $ \beta $ 來自？我理解通過限制 $ \beta $ 你增加了問題的難度，但它在什麼時候被定義？
關於基礎
如另一個答案所述，與 SIS 直接相關的晶格實際上是 $ q $ -ary 晶格定義為
$$ \mathcal{L}_q^\bot(A) := { u \in \mathbb{Z}^n : Au = 0 \mod q }. $$
它的基礎不是矩陣 $ A $ . 為了建構這個格的基礎，人們通常假設 $ A $ 有 $ n $ 線性獨立的列（比如說，第一個 $ n $ ） 和寫 $ A = [A_1 \quad A_2] $ 和 $ A_1 $ 作為一個 $ n\times n $ 矩陣可逆 $ \mathbb{Z}_q $ , 那麼下面的矩陣 $ B $ 是一個基礎：
$$ B = \begin{pmatrix} ~q\cdot I_n~ & -A_1^{-1}A_2 \ ~\vec 0~ & I_{m-n} \end{pmatrix} \in \mathbb{Z}^{m \times m} $$
關於硬度
實際上，無論它與晶格問題的聯繫如何，它都可能是一個難題。但它以多種方式連接到晶格。首先，很明顯，在 $ \mathcal{L}_q^\bot(A) $ 為我們提供 SIS 的解決方案。此外，已經證明，如果一個人能在多項式時間內平均解決 SIS，那麼一個人就可以解決硬格問題。
粗略地說：如果您有一個算法可以以不可忽略的機率解決 SIS（例如，您的算法可以在一百萬分之一中工作），那麼您將有一個算法來解決GapSVP和SIVP的近似版本）。
關於價值 $ \beta $
價值 $ \beta $ 是問題的一個參數。很容易找到 $ u $ 這樣 $ Au = 0 \mod q $ （只需使用高斯消元法），可能很難找到滿足該方程的短向量。但是你如何定義短？使用 $ \beta $ 作為長度的上限。
這些是標準事實：如果 $ \beta \ge q $ ， 然後 $ u = (q, 0, 0,…, 0) $ 是一個有效的解決方案，因此，SIS 對於這樣的值是微不足道的 $ \beta $ . 如果 $ \beta $ 太小，那麼可能沒有有效的解決方案。如果 $ \beta \ge \sqrt{m} $ 和 $ m \ge n\log q $ ，則保證存在至少一個有效解。
如果您正在求解 SIS 實例 $ As = 0 $ 超過 $ \mathbb{Z}_q $ 那麼這可以看作是從晶格中找到一個短的非零向量 $ {z \in \mathbb{Z}^m \ \mid Az = 0 \in \mathbb{Z}_q^n} \supset q \mathbb{Z}^m $ . 因此，它與您的不一樣 $ L(B) $ .
另一方面，表明 SIS 與某些晶格問題一樣困難並不明顯，並且可以從這項工作和一系列工作中得出關於 SIS 硬度的逐漸更強的結果。您可以在本調查中找到一些一般資訊。