Lattice-Crypto
通過高斯消元法或線性方程組求解模矩陣方程（SIS 假設？）
認為 $ S \in \mathbb{Z}_q^{m \times m} $ , 和範數 $ S $ 小於上限 $ \beta $ .
此外， $ A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n} $ .
這裡， $ k \geq m>n $ ， 和 $ q $ 是一個大素數。
和 $ S $ 是未知的。
滿足以下等式
$ SA_1 = C_1 $
$ SA_2 = C_2 $
$ \vdots $
$ SA_k = C_k $
我可以通過使用高斯消元法或任何線性方程組方法來解決這個問題嗎？
請注意，我認為這個問題與晶格硬假設類似 - SIS。
我不確定這個問題是否有解決方案。
讓 $ A’ := [A_1 ~ | ~ \dots ~ | ~ A_k ] \in \mathbb{Z}_q^{m \times n k} $ 和 $ C’ := [C_1 ~ | ~ \dots ~ | ~ C_k ] \in \mathbb{Z}_q^{m \times n k} $ . 然後定義 $ A \in Z_q^{m\times m} $ 作為第一個列的矩陣 $ m $ 列 $ A’ $ . 同樣，定義 $ C $ 使用第一個 $ m $ 列 $ C’ $ .
然後， $ S $ 滿足 $ S \cdot A = C \pmod q $ ，因此，您可以通過計算找到它 $ A^{-1}\cdot C \pmod q $ .
旁注：您為什麼認為這個問題與 SIS 問題相似？請注意，SIS 問題有一個參數 $ \beta $ 這是接受解的範數的上限，高斯消元法可能會輸出範數高於其範數的解 $ \beta $ （因此，不是有效的解決方案）。