SIS（短整數解）格問題何時開始變得容易（根據參數大小）？
**SIS（短整數解）問題：**給定 $ m $ 均勻隨機向量 $ a \in Z_q^n $ , 分組為矩陣的列 $ A \in Z_q^{n.m} $ , 找到一個非零整數向量 $ z \in Z^m $ 和 $ ||z|| \leq \beta \lt q $ , 這樣 $ Az = 0 \mod q $ .
關於問題的難度，有一個定理指出：對於任何 $ m = poly(n) $ , $ \beta \gt 0 $ , 求解 $ SIS $ 至少與解決其他近似問題一樣難，例如 $ GapSVP_\gamma $ （決策近似短向量問題）和 $ SIVP_\gamma $ （短獨立向量問題）在任意 n 維格上，對於某些 $ \gamma = \beta.poly(n) $ .
我的問題是：最大值是多少 $ \beta $ 和 $ m $ 相對於 $ n $ 哪些問題難以解決？例如在 $ GPV $ 他們認為的簽名 $ m = 2n\log q $ ， 和 $ \beta = 6n\log q $ . 但是我們也可以考慮 $ m = 4n\log q $ ? $ 8n\log q \dots $ ? $ n^{100} \log q $ ? $ \dots $ 同樣的事情 $ \beta $ . 問題開始變得容易的這些參數的限制是什麼？
如果$$ \beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k} $$對於一些常數 $ C $ . 這來自：
- 體積 $ q^{n} $ 為了 $ q $ -ary 格核
- Hermite 近似因子為 $ C^k $ 用於在維數格上的格縮減算法 (LLL/BKZ) $ k $
- 注意到一個人可以“忽略列”來處理一個維度的格子 $ k \leq m $
第 3 節中的更多詳細資訊
https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf
（在哪裡 $ C=\gamma_2 $ 因為我們只考慮 LLL 可證明的內容，但所有其他較小的固定常數 $ C>1 $ 也可以在多項式時間內到達）