Lattice 中最短向量的長度
在Miccincio 和 Regev 的論文《基於格的密碼學》中，最短向量的長度至少為 $ \min{q, 2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}} $ . 我想問為什麼論文選擇後者作為最短向量的長度而不是 $ q $ 在考慮音樂會參數時。此外，是否 $ q $ 通常大於 $ 2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})} $ ?
請記住，我們正在考慮 $ q $ -ary 晶格，定義為
$$ \Lambda^{\perp}_q(\mathbf{A}) = { \mathbf{y} \in \mathbb{Z}^m : \mathbf{A} \mathbf{y} = \mathbf{0} \mod q }. $$ 很明顯的向量 $ (q,\mathbf{0}) $ 在這個格子中，並且有長度 $ q $ . 這是一個微不足道的、無趣的解決方案，因為它不能更好地理解晶格。
$ \min { q, 2^{2 \cdot \sqrt{(n\cdot \log{q} \cdot log{\delta})}} } $ 指的是使用（當時）最先進的晶格縮減算法可以找到的最短向量。如果您選擇參數以使加密方案安全，則您試圖確保可以找到的最短非平凡向量不是很短。如果微不足道的向量破壞了您的方案，無論如何它都會被破壞，並且再多的參數調整也無法解決它。
有一些關於格密碼學的具體參數的工作，例如：
- R. Lindner 和 C. Peikert，2010，更好的基於 LWE 的加密的密鑰大小（和攻擊）
- M. Rückert 和 M. Schneider，2010，Estimating the Security of Lattice-based Cryptosystems ( http://eprint.iacr.org/2010/137 )（在 Peikert 的作品中，這似乎是通過標題Selecting secure parameters for lattice -based cryptography，也許後來更新了新標題）
在 Rückert 和 Schneider 的論文中，他們在第 4 節和表 3 中討論了您的參考論文和建議的數字，值得一看。但是，他們還指出，這些數字是用 $ \delta \geq 1.01 $ 記住，這可能不再合適了。
但這裡是該表中的範例值（2035 年的條目，92 位安全性）：
- $ n = 512 $
- $ q = 2^{59.749} $
- $ \delta = 1.0064 $
在這種情況下，我們會得到（以 2 為底的對數）：
$$ 2^{2 \sqrt{n \log{q} \log{\delta}}} \approx 2^{33.5594} < 2^{59.749} = q $$ （如果我的簡單計算器工作正常） 這樣做的原因是， $ \delta $ 真的很接近 $ 1 $ ， 意思是 $ \log{\delta} $ 遠小於 $ 1 $ ， 相近 $ 0 $ .
最後一點，Peikert 最近對格密碼學進行了一項調查：格密碼學十年