如何估計SIS實例的硬度？
短整數解 (SIS) 問題是在給定矩陣的情況下找到 $ A \in \mathbb{F}_q^{n \times m} $ 具有均勻隨機係數的向量 $ \mathbf{x} \in \mathbb{Z}^m \backslash {\mathbf{0}} $ 這樣 $ A\mathbf{x} = \mathbf{0} \mod q $ 和 $ \Vert \mathbf{x} \Vert_2 < \beta $ . 這個問題至少與具有近似因子的最短獨立向量問題 (SIVP) 一樣難 $ \tilde{O}(\beta\sqrt{n}) $ 在 $ n $ 維晶格。幾個提議的密碼系統依賴於 SIS，最值得注意的是 Ajtai 在原始論文中定義問題的函式 ( link )、 SWIFFT 散列函式 ( link ) 和幾個簽名方案 ( link ) ( link ) ( link )。
但是，我對根據成功攻擊的計算成本來估計這些密碼系統提供的安全性感到困惑。很少有來源實際上提供了硬度估計值，並且那些確實考慮了適當的根 Hermite 因子 $ \delta $ 而不是算術運算的計數。
例如，Miccincio 和 Regev 的章節（連結）提出了以下論點：存在最優列數 $ A $ 在使用基於格的算法（大概是 BKZ 2.0）攻擊 SIS 問題時要考慮到這一點。使用太少的列和短格點可能太難找到（如果它們存在的話）；使用太多，格子會太大。這個最小值被發現 $ m = \sqrt{n \log q , / \log \delta} $ ; 在這一點上，可以在“合理的時間內”計算的格點的平均長度是 $ 2^{2\sqrt{n \log q \log \delta}} $ ， 在哪裡 $ \delta $ 不小於 $ 1.01 $ . 所以通過要求 $ \beta < 2^{2\sqrt{n \log q \log \delta}} $ ，可以保證 SIS 實例無法在合理的時間內解決。
Lyubashevsky 的 2012 簽名方案（連結）的第 3.2 節給出了對 SIS 實例硬度的類似處理，該方案使用 $ \delta = 1.007 $ 用於設置參數。Miccincio 和 Peikert 的 2011 簽名方案（連結）提到設置 $ \delta \leq 1.007 $ 對應於 $ 2^{46} $ 晶格減少的核心年，大約是 $ 2^{100} $ 在 1.0 GigaHerz CPU 上循環。
我對此有幾個問題。是什麼導致無法或難以轉換參數 $ (m,n,q,\beta) $ 進入攻擊執行時間估計，根 Hermite 因子的意義是什麼 $ \delta $ 在這種情況下？鑑於 $ \delta $ 是一個有用的工具，如何在 $ \delta $ 和攻擊複雜性（安全位數）？給定一個目標短向量長度和點陣參數，如何估計BKZ 2.0找到這個長度的點陣點的時間？（或者，如果這不是一個明智的問題，為什麼這個執行時不重要？）
價值 $ \delta $ 表徵，您可以期望使用算法找到多短的向量（通常用於晶格縮減的上下文中）。
特別是對於一個向量 $ \mathbf{v} \in \Lambda $ （在哪裡 $ \Lambda $ 是一個格子），相關聯的 $ \delta $ （通常也表示為 $ \delta_0 $ ) 被定義為 $ | \mathbf{v} | = \delta^n \det(\Lambda)^{1/n} $ .
對於那些不知道如何獲取格的行列式的人，請參閱Oded Regev 教授的“電腦科學中的格”課程中介紹講座的第 4 頁。
這是在GN08中在晶格減少的背景下引入的，因為觀察到 $ \delta $ 對於格歸約返回的輸出向量收斂（對於增長 $ n $ ) 為每個類型和歸約參數化的常數。
通常，約簡算法是參數化的，並允許在輸出質量（即 $ \delta $ ) 和執行時間。確切的權衡仍然是研究的主題，特別是隨著約簡算法的不斷改進，但APS15（第 3 節）給出了對最新技術的一個很好的總結。粗略地說，將 SIS 實例轉換為 $ \delta $ 需要打破它，相對容易，但翻譯 $ \delta $ 到一個執行時間並不那麼直截了當。原因是格子減少的行為，迄今為止最有效的近似算法，還沒有被很好地理解，社區還沒有收斂到一個模型上。
晶格縮減的一個問題是它使用了精確的 SVP 求解器（在較低維度中）。為了實例化這些求解器，有不同的算法，一些在實踐中表現更好，而另一些則漸近更有效。這使得很難準確分析獲得一個短的質量向量需要多長時間 $ \delta $ .