Goldreich – Goldwasser– Halevi (GGH) 計劃的安全性

“Public-Key Cryptosystems from Lattice Reduction Problems”一文中有一段陳述，介紹了 GGH 加密方案：

“我們的方案背後的密碼分析問題是在給定格的“非簡化”基礎的情況下近似格中的最接近向量問題 (CVP)”

另一方面，Peikert 在他的調查中說：

" 不同於 Ajtai 和 Ajtai-Dwork 的作品

$$ AD97 $$，GGH 提案沒有附帶任何最壞情況的安全保證；他們推測的安全性僅僅是啟發式的。" 他還說：“由於尚未證明基於 CVPγ 的密碼系統是安全的，因此我們在這裡沒有正式定義該問題”

哪一個是真的？

如果您查看 GGH 論文，他們明確表示它們減少為 CVP 的隨機實例。在第 2.1 節中關於 CVP 的段落末尾，它明確表示：“正如我們在第 3 節中解釋的那樣，對我們的陷門函式的攻擊相當於為某些 CVP 的隨機實例找到一個精確的解決方案。” Peikert 指的是最壞情況保證（即任何 CVP 實例的硬度），而 GGH 考慮的是平均情況問題（當實例隨機生成時）。

引用自：https://crypto.stackexchange.com/questions/90162