為何格基密碼不怕 Shor演算法

🔐 格基密碼（Lattice-based cryptography）目前不怕 Shor 演算法，
因為 Shor 只對「週期結構明確的群問題」有效，而格問題本質上不是隱藏週期問題。

下面我們從數學與複雜度角度完整說明。

一、Shor 演算法在做什麼？

Shor 解的是：

在有限群中尋找元素的「階（order）」。

例如：

這屬於：

隱藏子群問題（Hidden Subgroup Problem, HSP）

對於：

整數乘法群
有限阿貝爾群

量子傅立葉轉換（QFT）可以高效率解。

二、為何 RSA、ECC 會被破？

因為它們基於：

大數分解
離散對數

這兩者都能轉化為：

阿貝爾群上的 HSP

Shor 利用：

在多項式時間內解出。

三、格基密碼的數學核心

常見格問題：

SVP（Shortest Vector Problem）
CVP（Closest Vector Problem）
LWE（Learning With Errors）

尤其現代密碼基礎是：

LWE 問題

形式：

其中：

s 是秘密
e 是小誤差（noise）

安全性來自：

噪聲使問題變成「近似幾何問題」

四、格問題本質是什麼？

格是一組：

這是一個：

幾何離散結構

核心困難是：

找最短向量（SVP）

這不是週期問題。

五、為何 Shor 無法解格問題？

Shor 成功的原因：

1️⃣ 問題能寫成群同態

2️⃣ 存在清晰週期

3️⃣ 可做傅立葉分析

格問題：

❌ 沒有自然群結構週期

❌ 不等價於 HSP

❌ 噪聲破壞傅立葉可解性

特別是 LWE：

等價於在格中加入高斯噪聲

噪聲讓量子傅立葉轉換無法聚焦。

六、量子複雜度觀點

目前已知：

分解 ∈ BQP
離散對數 ∈ BQP
LWE 未知是否 ∈ BQP

主流相信：

而且：

LWE 可歸約到：

最壞情況格問題（worst-case hardness）

這是強安全性來源。

七、重要理論基礎

格密碼安全性建立在：

Oded Regev

提出：

LWE 的平均困難性
可歸約到最壞情況格問題

這在經典與量子模型下都成立。

八、直觀比喻

RSA：

找週期 → 像找鐘擺頻率

格問題：

在高維空間找最短針
而空間充滿隨機雜訊

量子傅立葉適合「頻率問題」，

不適合「幾何噪聲問題」。

九、目前量子攻擊現況

量子電腦對格問題：

僅提供多項式加速（Grover search）
沒有指數級突破

Grover 只能：

加速，遠不如 Shor 的突破。

十、為何這是後量子標準？

NIST 選定的後量子標準如：

CRYSTALS-Kyber
Dilithium

都基於：

Module-LWE

因為目前沒有已知量子演算法可有效破解。

十一、哲學層面

這其實揭示：

量子優勢不是萬能

它依賴：

問題的對稱性
群結構
傅立葉可分解性

格問題：

困難來自高維幾何
而非代數週期

十二、核心總結

問題類型量子可解？分解

✅離散對數

✅LWE

❌（目前未知）SVP

❌（相信困難）

十三、一句話總結

Shor 打破的是「代數困難性」
格密碼建立在「幾何困難性」