SIS 沒有模數
考慮以下對短整數解 (SIS) 問題的修改：
讓 $ n $ 是一個整數並且 $ \alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha) $ 成為的函式 $ n $ . 試穿制服 $ A\gets[-\alpha,\alpha]^{n\times m} $ . 任務是計算“短”向量 $ e\in\mathbb{Z}^m $ 在核心中 $ A $ . 那是：
- $ |e| < \beta $ .
- $ A.e=0^n $ . 在這裡，等式適用於整數
SIS 的通常版本與上述相同，除了 $ A.e=0^n $ 持有模組 $ q $ ， 和 $ q=2\alpha+1 $ （以便 $ A $ 是均勻的 $ \mathbb{Z}_q^{n\times m} $ ）。此變體刪除了模數。
**問題：**這個版本的 SIS 是否有任何不平凡的難易程度結果？哪些參數設置很容易，哪些（如果有的話）可以根據更壞的格子問題證明是困難的，就像在通常版本的 SIS 中一樣？
**瑣碎攻擊：**在以下情況下存在瑣碎算法 $ \beta $ 很大。您可以通過取矩陣的小數來計算整數上的核向量 $ A $ . 這些未成年人，因此核心向量，可以很容易地上限為 $ (\alpha n)^{O(n)} $ . 所以在政權 $ \beta= (\alpha n)^{O(n)} $ ，有一個微不足道的攻擊。
我最好奇的是 $ \alpha,\beta $ 是多項式在 $ n $ . 這裡有沒有攻擊，或者有什麼硬度可以表現出來？
我選擇了分佈 $ A $ 上面給出一個具體的問題。但我也對其他發行版感興趣 $ A $ . 例如，如果 $ A $ 是離散高斯等？
也可以考慮這種 SIS 變體的非同質版本，其中 $ A.e=u $ , 對於某個向量 $ u $ （同樣，沒有模數）。我們必須小心，雖然對於大 $ u $ 不會有解決辦法。也許我們限制為隨機 $ u\in{0,1} $ ，或在 $ [-\gamma,\gamma]^n $ . 除了直接改編來自上面的瑣碎攻擊之外，我也很感興趣是否可以對這個問題說些什麼。
事實證明，某些版本的問題實際上與 SIS 一樣難。具體來說，我聲稱版本 $ A $ 是一個隨機二進制矩陣，並且 $ \beta $ 是多項式將是困難的，假設 SIS 很難選擇適當的參數。
讓 $ q=2^\ell $ 是 2 的冪，它足夠大於 $ \beta $ . 讓 $ n’=n/\ell $ （我們猜測 $ n $ 可被 $ \ell $ 為簡單起見）。然後考慮一個帶參數的SIS實例 $ n’,m,q,\beta $ : 給定一個隨機矩陣 $ A\in\mathbb{Z}_q^{n’\times m} $ ，目標是找到一個非零向量 $ e\in\mathbb{Z}^m $ 這樣 $ A\cdot e\equiv 0\pmod q $ 和 $ |e|<\beta $ .
我們將其簡化為如下所述的無模問題。讓 $ A_i\in{0,1}^{n’\times m} $ 是我們替換每個條目的矩陣 $ A $ 由 $ i $ 該條目的第 th 位。然後讓 $ A’\in{0,1}^{n\times m} $ 是通過堆疊所有的矩陣 $ A_i $ 在彼此之上。
如果我們可以解決無模 SIS $ A’ $ ，這會給我們一個向量 $ e\neq 0 $ 這樣 $ A’\cdot e=0 $ （在整數上）和 $ |e|<\beta $ . 但後來我聲稱 $ A\cdot e = 0 $ . 確實，每個條目 $ A $ 只是對應列中條目的線性組合 $ A’ $ . 因此，每個條目 $ A\cdot e $ 只是中條目的線性組合 $ A’\cdot e $ ，因此為 0。