# 後量子密碼學 03：二維晶格密碼學的正確性
## 系統回顧
### 密鑰生成
**公共參數**： 一個大整數 $q$。
**私鑰**： 兩個小整數 $f$ 和 $g$，滿足
\begin{align}
f < \sqrt{\frac{q}{2}}\\
\sqrt{\frac{q}{4}}< g <\sqrt{\frac{q}{2}} \\
\mathrm{gcd}(f,qg)=1
\end{align}
**公鑰**：
\begin{align}
h = f^{-1}g \mod q
\end{align}
### 加密（Encryption）
傳送者 Bob 選擇明文 $m$ 與一個隨機數 $r$，並都限制在
\begin{align}
0< m < \sqrt{\frac{q}{4}}\\
0< r < \sqrt{\frac{q}{2}}
\end{align}
計算密文為
\begin{align}
e = r h + m \mod q
\end{align}
傳送 $e$ 給 Alice
### 解密（Decryption）
Alice 用私鑰進行
\begin{aligned}
a &= fe \mod q
\\
b &= f^{-1}a \mod g
\end{aligned}
則可得 $b=m$。
## 正確性證明
首先注意到因為
\begin{align}
h = f^{-1}g \mod q
\end{align}
所以解密過程中：
\begin{aligned}
a & =f e=f(r h+m)=r f h+f m \\
& =r g+f m
\end{aligned}
又根據我們對 $r, g, f, m$ 的條件：
\begin{aligned}
0< m <\sqrt{\frac{q}{4}} \\
0< r <\sqrt{\frac{q}{2}} \\
0< f <\sqrt{\frac{q}{2}} \\
\sqrt{\frac{q}{4}} < g < \sqrt{\frac{q}{2}}
\end{aligned}
於是我們知道
\begin{align}
rg+fm \leq
\sqrt{\frac{q}{2}}\sqrt{\frac{q}{2}}+\sqrt{\frac{q}{2}}\sqrt{\frac{q}{4}} < q
\end{align}
也就是說，$rg + fm$ 這個數字，從構造條件上就確保了他不會超過 $q$，因此，Alice 根據我們密碼系統所算出來的 $a = fe$ ，完完全全等於 $rg + fm$。
請注意一個決定性的差別：上面提到「在模除 $q$ 的環中」，
\begin{align}
a=r g+f m \quad \bmod q
\end{align}
這裡的等號是指說，從整數的觀點看，數字 $a$ 與 $rg + fm$ 差了整數倍的 $q$。
而因為 $rg + fm$ 根本就不會超過 $q$ ，所以我們確保 $a$ 與 $rg + fm$ 在整數上根本完完全全相等，「並不是差了整數倍的 $q$ ，而是完完全全的相等」。
此時，我們就可以寫下
\begin{align}
a=r g+f m
\end{align}
現在將這個方程式左右都取模除 $g$ （比較數學的講法是說同時投影至模除 $g$ 的整數環）得到
\begin{align}
a=r g+f m \quad \bmod g
\end{align}
那其實根本就是
\begin{align}
a=f m \quad \bmod g
\end{align}
兩邊同時乘上 $f$ 在模除 $g$ 下的反元素：
\begin{align}
b=f^{-1} a=f^{-1} f m=m \quad \bmod g
\end{align}
再次根據我們的構造條件：
\begin{align}
0< m < \sqrt{\frac{q}{4}}, \quad \sqrt{\frac{q}{4}} < g < \sqrt{\frac{q}{2}}
\end{align}
我們於是知道 $m$ 根本就是一個小於 $g$ 的數字，所以，跟剛剛一樣的理由，這裡的 $b$ 也完完全全等於 $m$ 。
## 為何是二維晶格？
觀察加密與解密的核心條件：
\begin{align}
h \equiv f^{-1} g \quad(\bmod q)
\end{align}
若想在不知 $(f, g)$ 的情況下偽造一組 $(F, G)$ 也能成功解碼，你就需要
\begin{align}
F h \equiv G \quad(\bmod q)
\end{align}
而且你還需要
\begin{align}
rG + Fm < q
\end{align}
這樣才能正確解密，但是因為你不知道 $r$ 跟 $m$ 的確切值，所以你只能希望這些 $F$ 與 $G$ 「盡量得小」
換句話說，存在某個整數 $R$ 使得
\begin{align}
F h=G+R q
\end{align}
將其轉到 $\mathbb{Z}^2$ 的向量形式，可寫作：
\begin{align}
(F, G)=F(1, h)+(-R)(0, q) .
\end{align}
且其中 $F$ 與 $G$ 盡量的小。有沒有發現這相當於「我們要找到向量 $(1, h)$ 以及 $(0, q)$ 的整係數線性組合，好讓結果 $(F, G)$ 越小越好。」。是不是變成「短向量問題了呢？」
在高維度情況下，「尋找短向量 (SVP, Shortest Vector Problem)」是公認的 NP-hard 問題。但若僅是二維，情況就非常簡單：**我們可以用高斯化約 (Gauss Reduction) 非常快速地找到那個短向量**。這也代表在二維下，系統顯示出致命安全缺陷。
相關的攻擊方式請見此[連結](https://ithelp.ithome.com.tw/articles/10351576)。
