# 後量子密碼學07 NTRU II
今天我們來解釋昨天介紹的「吾乃數論學家」為何是晶格密碼學？
與之前的二維晶格相似，關鍵都在解碼的正確性
## 回顧解碼正確性的證明
之所以解碼會成功，主要原因是因為
\begin{align}
a(x) = p g(x) \cdot r(x)+f(x)\cdot m(x)
\end{align}
之右手邊部分的係數可以被控制，所以我們可以還原出整數上的等號（非模除上的等號），然後再做後續的有號提升與模除 $p$ 運算。
意思是，如果我們想要偽造一個假的密鑰 $(f(x), g(x))$ ，那他只要滿足：
### 一、
\begin{align}
f(x) h(x) = g(x) \text{ in } R_{q} = \mathbb{Z}_{q}[x] / \langle x^N-1\rangle
\end{align}
其中 $h(x)$ 與 $q$ 是公鑰的內容。
### 二、
$f(x)$ 與 $g(x)$ 的係數都不大，以至於以下多項式的係數絕對值不超過 $q/2$。
\begin{align}
p g(x) \cdot r(x)+f(x)\cdot m(x)
\end{align}
這個步驟是不是與之前看到的二維晶格非常雷同？😀
## 將多項式乘法寫為矩陣乘法
為了要用向量空間討論，我們應該介紹一個用矩陣乘法來寫的多項式乘法：
考慮在 $R$ 底下的運算
\begin{align}
g(x) = f(x) h(x) \text{ in }R = \mathbb{Z}[x] / \langle x^N-1 \rangle.
\end{align}
並將係數寫好
\begin{align}
g(x) = g_{0} + g_{1}x+g_{2}x^{2}+\cdots+g_{N-1} x^{N-1}\\
f(x) = f_{0} + f_{1}x+f_{2}x^{2}+\cdots+f_{N-1} x^{N-1}\\
h(x) = h_{0} + h_{1}x+h_{2}x^{2}+\cdots+h_{N-1} x^{N-1}
\end{align}
（以下的數學看過即可，我們會用程式驗證）
那麼根據在 $R$ 底下的模除運算規則，我們知道
\begin{align}
g_{k} = \sum_{i=0}^{k} f_{i}h_{k-i} + \sum_{i=k+1}^{N-1} f_{i}h_{N+k-i}
\end{align}
為了進一步分析，我們將其寫成矩陣形式：
\begin{align}
[g_{0}, g_{1},\dots,g_{N-1}] = [f_{0}, f_{1},\dots,f_{N-1}]
\begin{bmatrix}
h_{0} & h_{1} & h_{2} & \cdots & h_{N-1}\\
h_{N-1} & h_{0} & h_{1} & \cdots & h_{N-2} \\
h_{N-2} & h_{N-1} & h_{0} & \cdots & h_{N-3}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
h_{1} & h_{2} & h_{3} & \cdots & h_{0}
\end{bmatrix}
\end{align}
簡寫為：
\begin{align}
g = f\cdot H
\end{align}
好，證明部分很無聊，我們用程式簡單驗證看看：
```python=+
N = 11
# 多項式環
R_poly = quotient(PolynomialRing(ZZ,x),x^N-1)
# 隨機生成多項式
f = R_poly([randint(-10,10) for i in range(N)])
h = R_poly([randint(-10,10) for i in range(N)])
print("f =", f)
print("h =", h)
g = f*h
print("\ng = f * h =", g)
# Ouptuts:
# f = -6*xbar^10 + xbar^8 + 10*xbar^7 - 5*xbar^6 + xbar^5 + 3*xbar^4 - 6*xbar^3 + 7*xbar^2 + 7*xbar + 9
# h = xbar^10 + 5*xbar^9 - 9*xbar^8 - 7*xbar^7 + 2*xbar^6 - 5*xbar^5 + 7*xbar^4 - 3*xbar^3 + 4*xbar^2 - 7*xbar - 6
#
# g = f * h = -xbar^10 - 45*xbar^9 - 194*xbar^8 - 101*xbar^7 + 142*xbar^6 - 44*xbar^5 + 3*xbar^4 - 69*xbar^3 + 13*xbar^2 - 239*xbar + 157
```
呼叫 Matrix 類別，建構上面的 H 矩陣，並使用他內建的矩陣乘法：
```python=+
f_coeff = f.list()
h_coeff = h.list()
g_coeff = g.list()
H = Matrix([[h_coeff[(i-j)%N] for i in range(N)] for j in range(N)])
print(H)
F = Matrix([[f_coeff[i] for i in range(N)]])
print(F)
print("\n")
print(F*H)
print(g_coeff)
# Outputs:
# [-6 -7 4 -3 7 -5 2 -7 -9 5 1]
# [ 1 -6 -7 4 -3 7 -5 2 -7 -9 5]
# [ 5 1 -6 -7 4 -3 7 -5 2 -7 -9]
# [-9 5 1 -6 -7 4 -3 7 -5 2 -7]
# [-7 -9 5 1 -6 -7 4 -3 7 -5 2]
# [ 2 -7 -9 5 1 -6 -7 4 -3 7 -5]
# [-5 2 -7 -9 5 1 -6 -7 4 -3 7]
# [ 7 -5 2 -7 -9 5 1 -6 -7 4 -3]
# [-3 7 -5 2 -7 -9 5 1 -6 -7 4]
# [ 4 -3 7 -5 2 -7 -9 5 1 -6 -7]
# [-7 4 -3 7 -5 2 -7 -9 5 1 -6]
# [ 9 7 7 -6 3 1 -5 10 1 0 -6]
#
# [ 157 -239 13 -69 3 -44 142 -101 -194 -45 -1]
# [157, -239, 13, -69, 3, -44, 142, -101, -194, -45, -1]
```
可以發現，兩個結果是一樣的，所以我們已驗證這個等式的正確性。
## 將 f(x) 與 g(x) 寫成短向量：
### 先做成向量
首先，因為 $f(x)$ 與 $g(x)$ 應滿足
\begin{align}
f(x) h(x) = g(x) \text{ in } R_{q} = \mathbb{Z}_{q}[x] / \langle x^N-1\rangle
\end{align}
所以我們可以改寫為
\begin{align}
f(x) h(x) = g(x) + qu(x) \text{ in } R = \mathbb{Z}[x] / \langle x^N-1\rangle
\end{align}
$u(x)$ 是某個在 $R$ 裡面的多項式。
因此我們可以故技重施：
\begin{align}
(f(x),g(x)) & =(f(x),0)+(0, g(x)) \\
& =(f(x),0)+(0, f(x)h(x) - qu(x)) \\
& =(f(x),0)+(0, f(x)h(x))+( 0, - qu(x)) \\
& =f(x) (1, h(x)) -u(x) (0,q)
\end{align}
現在我們嘗試將這個寫成「係數的向量」：首先對付 $f(x)(1, h(x))$
\begin{align}
f(x)(1,h(x)) = (f(x),f(x)h(x))
\end{align}
而左邊可以寫為以下矩陣乘法
\begin{align}
[f_{0}, f_{1},\dots,f_{N-1}]
\begin{bmatrix}
1 & 0 & 0 &\cdots & 0& h_{0} & h_{1} & h_{2} & \cdots & h_{N-1}\\
0 & 1 & 0 &\cdots & 0& h_{N-1} & h_{0} & h_{1} & \cdots & h_{N-2} \\
0 & 0 & 1 &\cdots & 0& h_{N-2} & h_{N-1} & h_{0} & \cdots & h_{N-3}\\
0 & 0 & 0 &\cdots & 0& \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 &\cdots & 1& h_{1} & h_{2} & h_{3} & \cdots & h_{0}
\end{bmatrix}
\end{align}
我們把它記作
\begin{align}
f \cdot \begin{bmatrix}
I & H
\end{bmatrix}
\end{align}
接著對付 $-u(x)(0, q)$
\begin{align}
[-u_{0}, -u_{1},\dots-u_{N-1}]
\begin{bmatrix}
0 & 0 & 0 &\cdots & 0 &
q & 0 & 0 &\cdots & 0\\
0 & 0 & 0 &\cdots & 0 &
0 & q & 0 &\cdots & 0\\
0 & 0 & 0 &\cdots & 0 &
0 & 0 & q &\cdots & 0\\
0 & 0 & 0 &\cdots & 0 &
0 & 0 & 0 &\cdots & 0 \\
0 & 0 & 0 &\cdots & 0 &
0 & 0 & 0 &\cdots & q
\end{bmatrix}
\end{align}
我們把它記作
\begin{align}
-u\begin{bmatrix}
O & q
\end{bmatrix}
\end{align}
因此，
\begin{align}
(f(x),g(x)) = f(x)(1,h(x)) -u(x) (0,q)
\end{align}
可以寫為
\begin{align}
[f_{0},f_{1},\dots,f_{N-1},g_{0},g_{1},\dots,g_{N-1}]
=f \cdot \begin{bmatrix}
I & H
\end{bmatrix} - u \begin{bmatrix}
O & q
\end{bmatrix}
\end{align}
或整更簡潔地
\begin{align}
(f,g) = (f,-u)\begin{bmatrix}
I & H \\
O & q
\end{bmatrix}
\end{align}
### 短向量問題
好的，接著我們來分析這個矩陣方程式
\begin{align}
(f,g) = (f,-u)\begin{bmatrix}
I & H \\
O & q
\end{bmatrix}
\end{align}
左手邊是一個 $2N$ 維度的向量，我們希望他越小越好。
右手邊可以看成是矩陣
\begin{align}
\begin{bmatrix}
I & H \\
O & q
\end{bmatrix}
\end{align}
其行向量的整係數 $(f_0, ..., f_N-1, -u_0, ..., -u_N-1)$ 線性組合
引此我們在做的其實是決定好整係數
\begin{align}
[f_{0},f_{1},\dots,f_{N-1}, -u_{0},-u_{1},\dots,-u_{N-1}]
\end{align}
好讓他的結果向量
\begin{align}
[f_{0},f_{1},\dots,f_{N-1},g_{0},g_{1},\dots,g_{N-1}]
\end{align}
儘量的小。
恭喜，這就是標準的晶格短向量問題。
