為什麼近似 GCD 是一個難題？
整數方案上有許多完全同態加密，其安全性基於近似 GCD (AGCD) 問題的難處理性。
論文Algorithms for the Approximate Common Divisor Problems 調查了幾種解決 AGCD 的基於格子縮減的算法。他們都需要 $ t > \frac{\gamma - \eta} {\eta - \rho} $ 樣本來解決 $ (\gamma, \eta, \rho) $ -AGCD問題通過減少一個特定的 $ t \times t $ 格子。
在整數上的完全同態加密的第 5.2 節中，作者陳述了一個“經驗法則”，即格歸約算法作用於 $ t \times t $ 格大致需要時間 $ 2^{t/k} $ 輸出一個 $ 2^k $ 最短向量的近似。
然而，已知 LLL 晶格約簡在關於晶格維度和輸入大小的多項式時間內執行。具體來說，對於 DGHV 方案， $ (\gamma, \eta, \rho) $ ~ $ (\lambda^5, \lambda^2, \lambda) $ , 快速估計得出 $ L^2 $ 晶格減少可以及時打破DGHV $ \lambda^{25} $ 有記憶 $ \lambda^{11} $ 給定 $ \lambda^{3} $ 樣品。
那麼為什麼上述論文將 AGCD 上的格攻擊的執行時間視為指數？
TL;博士
- AGCD 問題確實需要漸近指數時間來求解。
- 一般來說，LLL不能解決AGCD問題
- 參數 $ (\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda) $ DGHV10中提出的保證（漸近）安全級別為 $ 2^{\Omega(\lambda)} $ .
AGCD問題的格攻擊
您假設可以使用 LLL 解決 AGCD 問題。當然，如果能做到，那麼 AGCD 問題就可以在多項式時間內解決。然而，這通常不是真的，因此，攻擊者必須使用大塊大小的 BKZ，這是指數時間。
粗略地說，在AGCD問題中，有一個“差距” $ \Delta := \eta - \rho $ 秘密值之間 $ p $ ，其位長為 $ \eta $ ，以及雜訊項，其位長為 $ \rho $ . 格攻擊最終試圖在“這個間隙”中找到向量，即範數大於 $ 2^\rho $ 但小於 $ 2^\eta $ ，因此，我們總是有形式的 必要條件$$ \alpha t + \frac{\gamma}{t} < \eta - \rho ~~~~~ (\text{Inequality }1) $$ 在哪裡 $ 2^\alpha $ 是格基約簡算法的根 Hermite 因子。
例如，在您連結的論文中，GGM16，第 5 頁的不等式 (4)，如果您取消該術語，則與上面的不等式 (1) 基本相同 $ \sqrt{t+1} $ 出現在兩邊並忽略常量 $ 0.47 $ 和 $ \sqrt{1 / (2\pi e)} \approx 0.242 $ 但不要忽略 LLL 的指數逼近因子。
直覺地說，這個間隙越小，就越難在這個間隙中找到一個向量。
通常，當我們實例化 AGCD 問題時 $ \lambda $ 安全位，我們設置 $ \rho = \lambda $ ，因此對雜訊項的攻擊需要超過 $ 2^\lambda $ 步驟，和 $ \eta $ 由應用程序定義（例如，它取決於要同態評估的電路的深度）。那麼，我們只需要選擇 $ \gamma $ 以獲得所需的安全級別。我們通過固定根 Hermite 因子並將其代入不等式 (1) 來做到這一點，然後求解 $ \gamma $ .
排除 LLL
為了選擇 LLL 無法解決 AGCD 問題的參數（這需要攻擊者使用 BKZ，這是一種指數時間算法），我們可以設置 LLL 的（樂觀的）根 Hermite 因子 $ 2^\alpha = 1.02 $ ，因此，在不等式 (1) 中，我們有 $$ \log(1.02) t^2 + (\rho - \eta) t + \gamma < 0. $$
但是為了讓這個不等式有一個解決方案，我們需要它的判別式是正的，因此，為了排除 LLL，我們可以選擇 $ \gamma $ 使得判別式為負，即
$$ (\eta -\rho )^2 - 4 \log(1.02) \gamma < 0 \iff \gamma > \frac{(\eta -\rho )^2}{ 4 \log(1.02) } \approx 13 \cdot (\eta -\rho )^2. $$
DGHV10 中聲稱的漸近安全性
堵塞 $ (\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda) $ 在不等式 (1) 中，我們有 $$ \alpha t + \lambda^5 / t < \lambda^2 - \lambda \approx \lambda^2, $$ 因此，我們必須選擇 $ t \approx \lambda^3 $ 對於這個術語 $ \lambda^5 / t $ 小於間隙 $ \eta - \rho $ ， 但是之後， $ \alpha t \approx \lambda^3 $ 大於差距。因此，我們沒有解決辦法。