望舒
构造更高维度的格？
寒芒
相较较简单的“青天”的格构造，我们还需要将未知元素从单个元素提升(lift)为向量乃至矩阵。
有关“青天”的格构造参见格，其中系统介绍了格、部分代数和离散数学中的重要概念，有助于快速入门格密码；本文均假定读者已经具备相关的基础知识并已理解之。
"lift"的核心无外三点：
- 矩阵的构造（线性组合）必须符合目标环的运算规则；
- 已知量嵌入格矩阵
L中，未知但已知是整数 \(k_{i}\) 的量放在左侧，未知且已知是整数 小量 的放在右侧（锚定向量）；
- 对格进行配平，令锚定向量的各维度尽可能近长。
如在NTRU中，由于其元素的运算在卷积多项式环上运行，因此将 \(h\) 应转化为 \(rot(h) = \begin{bmatrix} h_0 & h_1 & \cdots & h_n \\ h_1 & h_2 & \cdots & h_0 \\ \vdots & \vdots && \vdots \\ h_n & h_0 & \cdots & h_n-1 \end{bmatrix}\)，使其在进行乘法时符合该环的运算规则。
配平格的要点在于利用好LLL（或BKZ）的特性之一——模长“标定”。
炽羽
对CVP问题的求解是此类格构造后利用的重点。
CVP问题常见的解法有二：将目标向量“嵌入”原格中，使之提升一个维度；或使用Babai's
Nearest Plane Algorithm。
Babai
1 | def Babai(A,v): |
从上述实现中即可一窥Babai's Algorithm的核心：
- 先对之进行格基规约（注意此方法仅适用于方阵，对于非方阵应使用
IntegerLattice，具体原因似乎与 m>n 时规约的“崩塌”有关（此时因为向量间必定线性相关的特性，会让规约的最终向量失去意义）；
- 取规约矩阵正交化后的向量基，在每个 两两垂直
的投影方向上均减去这些基的
最近整数倍（因为格运算都在整数上进行，参见
.round()）。
Embedding
Babai's Embedding Technique 的核心思想非常简单：
假设存在向量 \(\mathbb{v}^{N}\) 在
\(\mathbb{L}^{M \times N}\)
所定义的格上，不妨构造
\[\mathbb{L}^{' M+1 \times N+1} =
\begin{bmatrix} \mathbb{L} \\ \mathbb{v} & -1
\end{bmatrix}\]
则该格上一定存在一个向量 \(\begin{bmatrix}
0^{N} & -1 \end{bmatrix}\)。
上述推论比较显然——因为 \(v\) 就是 \(L\) 的线性组合，其系数取 \(-1\) 通过行变换就可以构造出这个向量。
显然此时对 \(L^{'}\)
进行规约就可以得到这个向量。
更进一步地，假设存在一个偏移a.k.a.误差向量 \(\mathbb{e}^{N}\)，其近似地表征了 \(\mathbb{dist(v,L)}\)（即该向量和格之间的距离）。
令 \(\mathbb{b = v + e}\)，将 \(\mathbb{b}\) 嵌入该格中，则向量 \(\begin{bmatrix} e^{N} & -1
\end{bmatrix}\) 也在格上。
此时若 \(e\)
足够短，同时对格进行配平，通过格基规约同样有很大概率找出该向量。
得到 \(\mathbb{e}\) 后，易得CVP的解即为 \(\mathbb{b - e}\)。
1 | L = #... |
月舞
Delightful的“约减”背后，还有些什么若隐若现...
朝花夕拾
纸上得来终觉浅——实践中分析更复杂的密码系统方为正道。
LWE
简述
LWE(Learning With Errors)是机器学习领域的难题之一。
其数学表示形式为：已知 \(Z_{q}\) 下
\(A^{M \times N} \cdot s^{N \times 1} + e^{M
\times 1} = b^{M \times 1}\)，给定 \(A,b\)，还原 \(s\)。
其中 \(e\) 是一个小向量。
更形象地：
已知两个 \(N\) 维向量 \(a_{i},s\)，计算其带一定误差的点积
\(b_{i} \equiv a_{i} \cdot s + e_{i} (\bmod
q)\)，重复 \(M\) 次（\(M \geq N\)），还原 \(s\)。
绮链
若不考虑误差，上述问题显然只是普通的解 \(Z_{q}\) 下的线性方程组的问题，可以使用高斯消元法直接求解，或利用线性代数知识，进行行列变换或计算 \(Z_{q}\) 下的 \(b \cdot A^{-1}\) 即可（此处需要截断之为方阵）。
但加入误差后，求解就变得极为困难了——按上述传统思路，必须逐个爆破误差 \(e_{i}\) 后验证解，可行性极为受限。
新的方程组与格
LWE中，格的构造相较以往单元素的方程组更为“精巧”。
由于 \(A \cdot s\) 结果的每个维度对
\(q\) 取模时都可能存在不同的 \(k_{i}\)（参考上述等式： \(b_{i} = a_{i} \cdot s + e_{i} +
k_{i}q\)），因此构造时应当取一个 \(qI^{M}\)
的对角阵与之排列。换言之，我们的“理想”向量（在 \(e\) 不存在时）应该在这个格上：
\[\begin{bmatrix} qI^{M} \\ A^{T} \end{bmatrix}\]
其中 \(A\) 因为格矩阵运算（LWE中 \(s\) 是被右乘的操作数，格的线性组合要求左乘系数）而被转置。
由于 \(e\)
是小向量，因此其显然就是一个CVP问题，求解思路同样是Babai/Embedding实际上这个Embedding的常用变种之一就是以Babai命名的。
在使用Babai时，由于原矩阵不是方阵，因此需要使用IntegerLattice并在其构造函数中规约之：
1 | L = IntegerLattice(mt,lll_reduce = True) |
Babai's Embedding的构造矩阵形如：
\[\begin{bmatrix} v_{k}^{M} & s^{N} & 1 \end{bmatrix} \cdot \begin{bmatrix} qI^{M}\\ A^{T}\\ b & C_{0} \end{bmatrix} = \begin{bmatrix} e^{M} & C_{0}\end{bmatrix}\]
由目标向量可知配平系数 \(C_{0}\) 应与 \(e\) 的大小接近，取 \(2^{ebits}\) 即可。
NTRU
卷积多项式环
给定 \(N,q \in Z_{+}\)，则模 \(q\) 下的 \(N - 1\) 次卷积多项式环是一个商环(quotient ring)，记作 \(R_{q} = \frac{Z_{q}[x]}{x^{N} - 1}\)。
商环的定义为对环(Ring)上，\(\forall a \neq 0 \in R, \exists a^{-1} \in R\)，即除了加法单位元 \(0\) 外所有元素均存在逆元。
\(R_{q}\) 下的 \(n\) 次卷积多项式表示：
\[z = z_{0}x^{0} + z_{1}x^{1} + \cdots + z_{n-1}x^{n-1} = \sum_{i=0}^{n-1} z_{i}x^{i} \in R^{n}_{q}\]
设 \(f,g,h \in R^{n}_{q}\)，\(f \cdot g = h\)，乘法规则形如
\[ h = \sum_{i=0}^{n-1} h_{i}x^{i} \\ h_{i} \equiv \sum_{a,b}^{a+b \equiv i \bmod N} f_{a}g_{b} \bmod q\]
显然其与普通的多项式乘法并无差分，只是对幂数和项数的计算分别放在了 \(Z_{n}\) 和 \(Z_{q}\) 下进行。
写作 \(Z_{q}\) 下 \(n \times n\) 矩阵乘法的形式，形如：
\(\begin{bmatrix} h_0 & h_1 & \cdots & h_{n-2} & h_{n-1} \end{bmatrix} ^ {T} = \begin{bmatrix} f_0 & f_1 & \cdots & f_{n-2} & f_{n-1} \\ f_1 & f_2 & \cdots & f_{n-1} & f_0 \\ \vdots & \vdots && \vdots & \vdots \\ f_{n-1} & f_0 & \cdots & f_{n-3} & f_{n-2} \end{bmatrix} \cdot \begin{bmatrix} g_0 & g_1 & \cdots & g_{n-2} & g_{n-1} \end{bmatrix} ^ {T}\)
称其中表示 \(f\) 的系数矩阵为卷积矩阵(convolution matrix)，常记作 \(rot(f)\)，其第 \(i\) 行由 \(f\) 的系数循环右移 \(i\) 位排列而成。
若 \(q\) 比较大，为提升可读性，部分实现会将 \(f_{i}\) 转化到 \((-\frac{q}{2},\frac{q}{2}]\) 的区间内（\(Z_{q}\) 下等价）。
参数与密钥生成
NTRU的关键参数为 \((N,p,q,d)\)。其中，
- \(N,q\)
越大则格攻击构造格的维度越高，密码系统越安全，但运算效率会大幅下降；一般选择
\(N \in [250,2500]\)。
- \(p,d\) 均为整数，要求 \(gcd(p,q) = 1\) 且 \(gcd(q,N) = 1\)，\(q > (6d + 1)p\)。
NIST对NTRU的强度-推荐参数组合如下：
| 强度 | N | p | q |
|---|---|---|---|
| 标准 | 251 | 3 | 128 |
| 高 | 347 | 3 | 128 |
| 最高 | 503 | 3 | 256 |
参数 \(d\) 可在满足 \(q > (6d + 1)p\) 下自行决定，一般选择 \(d \approx \frac{N}{3}\) 来达到较好的安全性。
定义函数 \(T(d_{1},d_{2}) (d_{1} + d_{2} < q)\) 表示系数 \(\{1,-1\}\) 计数分别为 \(\{d_{1},d_{2}\}\) 的多项式 \(f\) 的集合。
如，\(f = x^{6} + x^{3} - x^{2} + x - 1 \in T(3,2)\)。
选择两个多项式 \[f = \sum_{i=0}^{N-1} f_{i}x^{i} \in T(d+1,d)，g = \sum_{i=0}^{N-1} g_{i}x^{i} \in T(d,d)\]
再计算 \(h \equiv f^{-1}g (\bmod
q)\)，随后将 \(g\)
的记录销毁。
公钥为 \(h\)，私钥为 \(R_{p}\) 和 \(R_{q}\) 下的 \(f^{-1}\)（由于 \(p,q\) 是既定参数，可以认为私钥就是 \(f\)）。
\(g\) 不是公钥或私钥，但知道 \(g\) 就可以攻破NTRU，其地位类似于RSA中 \(N\) 的因数分解，故不应保留之。
加/解密与正确性证明
先将明文编码为一个 \(n\) 次多项式 \(m \in \{-1,0,1\}^{N}\)。
加密时，另随机生成一个多项式 \(r \in \{-1,0,1\}^{N}\)，计算 \(c \equiv ph \cdot r + m (\bmod q)\)，输出密文 \(c\)。
解密时，计算 \(m \equiv f^{-1} \cdot (f \cdot c (\bmod q)) (\bmod p)\)，输出明文 \(m\)。
注意其中涉及到了“换环”，即现在 \(R_{q}\) 下计算 \(f \cdot c\)，将结果转到 \(R_{p}\) 下后再与该环下的 \(f^{-1}\) 相乘。
正确性证明：
先在 \(R_{q}\) 下计算， \(f \cdot c = pr \cdot hf + mf \Rightarrow f \cdot c
= prg + mf\)
随后换环到 \(R_{p}\) 上，显然 \(prg \equiv 0 (\bmod p)\)，因此 \(R_{p}\) 下 \((fc
\bmod q) \equiv fm\)
进而 \(fm \cdot f^{-1} = m\)
解密正确性得证。
攻击
从公钥推导私钥
作为公钥密码算法，NTRU所依赖的数学难题是格上的SVP问题。
给定公钥 \(h\) ，若维度参数 \(N\)
选择过小，则通过格基规约获得SVP问题的近似解是可行的。
以Sage梳理攻击过程：
1 | #sage |
关键等式为 \(Z_{q}\) 下， \(f \cdot h \equiv g\)；将之抬升(lift)至 \(Z\) 下，则有 \(f \cdot h + q \cdot z = g\)，其中 \(z\) 是 \(Z^{N}\) 下的某个“制衡”向量( carry-on vector )。
矩阵运算如下：
\[\begin{bmatrix} f & z \end{bmatrix} \cdot \begin{bmatrix} I^{N} & rot(h) \\ & qI^{N} \end{bmatrix} = \begin{bmatrix} f & g \end{bmatrix}\]
对构造格进行规约，其预期最短向量就是 \(\begin{bmatrix} f & g
\end{bmatrix}\)，注意 \(f\) 和
\(g\) 都是 \(Z^{1 \times N}\) 的向量。
由于 \(f,g\) 每一维度的取值都在 \(\{-1,0,1\}\) 中（等价地，\(p=3\) 时的 \(Z_{p}）\)，其模显然在格中是极短的。
构造矩阵以分块矩阵的方式表述（实际上单个元素可被视为1*1的分块矩阵的“特例”），对矩阵的幺元操作在格中体现为单位矩阵，此时锚定向量实际上也是分块矩阵“拼凑”的结果。
由上述分析，显然规约矩阵的最短向量的前 \(N\)、后 \(N\) 个维度即分别为 \(f^{'}\)、\(g^{'}\)。由于运算时的卷积操作，严格地，此处解出的私钥
\(f^{'}\) 实际应为 \(x^{-i}f (i \in (-N,N))\)，\(g^{'}\) 同理。
欲破译原私钥 \(f\) ，则必须对 \(f,g\) 的卷积系数分别进行爆破。
但若目标只是解密数据，参考上述NTRU的解密过程， \(f\) 的卷积结果 \(f^{'}\)
依然可以对密文进行解密（因为解密用到的 \(f^{'-1} = x^{-i}f^{-1}\) ）。
春滋
方程的潇潇暮雨。
“短格”的精华
先考虑整数环 \(Z\) 下一个较简单的方程：
\[ax + by = c \]
在给定 \(a,b,c\)
时其只是一个平凡的一元二次不定方程；若移去 \(c\)，则一般而言无法得出 \(x,y\) 的解。
但若已知 \(x,y,c\)
都是较小的整数，则可以使用格攻击来获得方程的解：
\[\begin{bmatrix} x & y \end{bmatrix} \cdot \begin{bmatrix} C & a \\ & b \end{bmatrix} = \begin{bmatrix} Cx & c \end{bmatrix}\]
其中若目标向量的模长足够小（已知 \(c << a,b\) 且配平系数 \(C\) 选择得当），则或可通过格基规约得到目标向量。
上述放长还可以推广至多变量的情况传说中的多元Coppersmith青春版，只看一次项：
\[a_1x_1 + a_2x_2 + \cdots + a_nx_n = c\]
\[\begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix} \begin{bmatrix} C_1 &&& a_1 \\ &C_2 && a_2 \\ && \ddots & \vdots \\ &&& a_n \end{bmatrix} = \begin{bmatrix} C_1x_1 & C_2x_2 & \cdots & c \end{bmatrix}\]
可以注意到，这个“更一般的”方程在 \(c\) 已知时就是HLCP(Hidden Linear
Combination Problem，隐藏线性组合问题)。
实际上HLCP也可以“移进”至上述这个方程的形式，并且可以拓展到和sum含有一定误差的情况，即将
\(c\)
移至等号左侧，右侧以一小量（不一定是0）代替。