密码学数学基础之格基础

格的基本概念

数学研究：Lagrange，Gauss，Hermite等研究二二次型理论，开普勒猜想等，Minkowski提出了数的几何理论（几何数论）。

算法研究：Lagrange-Gauss算法，LLL算法等。
密码分析：分析背包问题，小指数RSA问题等。
密码设计：NTRU方案，Ajtai-Dwork方案，抗量子密码体制。

内积的定义

定义：设R是实数集， $R^{m}$ 是m维欧氏空间， $R^{m}$ 中的元素用列向量表示。定义 $R^{m}$ 中的内积

此内积定义了 $R^{m}$ 中向量的长度 $||\cdot||$ ，即对 $\forall x\in R^{m}$ ， $||x||=\sqrt{x^{T}x}$ 。

格的定义

定义：设 $b_{1},b_{2},...,b_{n}$ 是 $R^{m}$ 中n个线性无关的向量(m≥n)，Z为整数集，称

$L(b_{1},b_{2},...,b_{n})=\{\sum_{i=1}^{n}{x_{i}b_{i}}|x_{i} \in Z\}$

为 $R^{m}$ 中的一个格，简记为L，称 $b_{1},b_{2},...,b_{n}$ 为格L的一组基，m为格L的维数，n为格L的秩。

例：

一维的情况： $L_{1}=Z,L_{2}=3Z=\{3z|z \in Z\}$ ，

二维的情况： $L_{3}=L\{(1,0)^{T},(0,1)^{T}\}=Z^{2}$ ， $L_{4}=L\{(1,100)^{T},(1,101)^{T}\}$ 。

格的另外一种定义

定义：格L是 $R^{m}$ 中秩为n的离散加法子群。

注：离散是指对任意的 $v\in L$ ，存在 $v$ 的一个邻域 $U$ ，使得 $U\cap L=\{v\}$ ，可以验证格的两种定义是等价的。

Gram-Schmidt正交化

输入： $R^{m}$ 中的一组线性无关的向量 $b_{1},b_{2},...,b_{n}$

输出：一组正交向量 $b_{1}^{*},b_{2}^{*},...,b_{n}^{*}$ 。

1. $b_{1}^{*}=b_{1}$ ，

2. for i=2,3,...,n do

$b_{i}^{*}=b_{i}-\sum_{j=1}^{i-1}{\mu_{i,j}b_{j}^{*}}$ ，其中 $\mu_{i,j}=\frac{<b_{i},b_{j}^{*}>}{<b_{j}^{*},b_{j}^{*}>}$ ， $1\leq j \leq i\leq n$ 。

注记

$b_{1}^{*},b_{2}^{*},...,b_{n}^{*}$ 通常不一定是格L的基。

存在关系式：

$(b_{1},b_{2},...,b_{n})=(b_{1}^{*},b_{2}^{*},...,b_{n}^{*}) \left[ \begin{matrix} 0 & \mu_{2,1} & ... & \mu_{n,1}\\ 0 & 1 & ... & \mu_{n,2}\\ ... & ... & ... & ...\\ 0 & 0 & ... & 1\\ \end{matrix} \right]$

特别地，格L的行列式满足：

$det(L)=\prod_{1\leq i\leq n} ||b_{i}^{*}||$ ， $det(L)\leq \prod_{1\leq i\leq n} ||b_{i}||$ 。

格上的最短向量问题

最短向量问题定义

给定格基 $B\in Z^{m\times n}$ 定义的格L。格中最短非零向量的长度记为 $\lambda_{1}(L)$ 。格上的最短向量问题（Shortest Vector Problem，简称SVP）有如下的变体：

求解SVP：求解格点 $v\in L$ 使得 $|v|=\lambda_{1}(L)$ 。

优化SVP：计算 $\lambda_{1}(L)$ 。

判定SVP：给定一个有理数r，判断是否满足 $\lambda_{1}(L) \leq r$ 。

注记

上述三个版本的问题是多项式时间等价的。
SVP问题在随机归约下被证明是NP-困难问题。

近似SVP问题：给定逼近因子 $\gamma \geq 1$ ，上述问题中的入1替换成 $\gamma \lambda_{1}$ 。

后量子密码学

1994年，基于量子计算机模型，Shor提出了概率多项式时间算法求解因子分解问题和离散对数问题。
后量子密码学建立在能抵抗量子攻击的困难问题上，格上的些困难问题（例如SVP问题）是潜在的候选对象。

Blichfeld定理

问题：一般情况下能否在理论上给出 $\lambda_{1}$ 的一个上界?

定理：设L是 $R^{n}$ 中的满秩格。如果可测集满足 $vol(S) > det(L)$ ，那么存在两个不同的向量 $z_{1},z_{2}\in S$ ，使得 $z_{1}-z_{2}\in L$ 。

例：

Minkowski凸体定理

定理：设L是 $R^{n}$ 中的满秩格，S是 $R^{n}$ 中一个可测的关于原点对称（即 $a\in S\Rightarrow -a\in S$ ）的凸集（即 $a,β\in S\Rightarrow \frac{1}{2}(\alpha+\beta)\in S$ ），若S的体积 $vol(S) > 2^{n}det(L)$ ，则 $S\cap L$ 中有非零向量。

证明：考察 $S'=\frac{1}{2}S$ ，有 $vol(S')=\frac{1}{2^{n}}vol(S) > det(L)$ 。根据Blichfeld定理，存在 $v'_{1}=\frac{1}{2}v_{1},v'_{2}=\frac{1}{2}v_{2},v_{1}\ne v_{2}\in S$ 使得 $v=v'_{1}-v'_{2}=\frac{1}{2}v_{1}-\frac{1}{2}v_{2} \in L$ 。

因为 $v_{1},-v_{2}\in S$ ，并且S是凸体，所以 $v \in S$ 。

Minkowski第一定理

定理：设L是 $R^{n}$ 中的满秩格， $V_{n}$ 是n维空间中半径为1的单位球的体积，那么 $\lambda_{1}\leq \frac{2}{V_{n}^{1/n}} det(L)^{1/n} \leq \sqrt{n} det(L)^{\frac{1}{n}}$ 。

证明：设 $S=B(0,\lambda_{1}(L))$ 是以原点为中心，以 $\lambda_{1}(L)$ 为半径的开球。一方面，根据 $\lambda_{1}(L)$ 的定义，推出：

$vol(S)=\lambda_{1}^{n}V_{n} \leq 2^{n}det(L)$ 。另一方面，因为S中包含一个n维的边长为 $(\frac{2\lambda_{1}(L)}{\sqrt{n}})^{n} \leq \lambda_{1}^{n}V_{n}$ 。

综合上面两个不等式推出定理成立。

应用举例：平方和表示

定理
设素数 $p\equiv1(mod4)$ ，则存在整数a，b使得 $p=a^{2}+b^{2}$ 。

证明

因为素数 $p\equiv1(mod4)$ ，所以存在e使得 $e^{2}\equiv-1(modp)$ 。考虑由向量 $(1,e)$ ， $(0,p)$ 生成的格L。计算可知 $det(4)=p$ 。根据Minkowski第一定理，存在非零格点 $(a,b)= (x,xe+yp)$ 使得：

$0<a^{2}+b^{2}<\frac{4p}{\pi}<2p$ 。

又因为： $a^{2}+b^{2}=x^{2}(1+e^{2})+2xyep+y^{2}p^{2}\equiv0(modp)$ ，所以 $p=a^{2}+b^{2}$ 。

求解格的最短向量

Minkowski第一定理给出了格中最短向量长度的一个上界。
问题：如何构造出具体的短向量（或者近似的短向量）？如何构造出一组较好的格基（约化基）？

1维：辗转约化

考虑1维满秩格 $L=\{15x+6y|x,y\in Z\}$ 。

2维的例子：投影+辗转约化

高维的情形：LLL算法

1982年，A. K. Lenstra，H. W. Lenstra和L. Lovasz提出了一种格基约化算法能构造性地求出格L的一组LLL-约化基，他们的算法被称为LLL算法。LLL算法能够在多项式时间内求解近似因子为 $(\frac{2}{\sqrt{3}})^{n}$ 的短向量，具有广泛的应用。

存在非多项式时间算法可以找到n维格中长度更短的向量（或最短向量）。

投影映射

定义：给定 $R^{n}$ 中一组向量 $b_{1},b_{2},...,b_{n}$ 。定义投影映射 $\pi_{i}$ 为

$\pi_{i}:R^{n}\rightarrow Span(b_{1},...,b_{i-1})^{\bot}$

$x\rightarrow \sum_{j=i}^{n}{\frac{<x,b_{j}^{*}>}{<b_{j}^{*},b_{j}^{*}>}}b_{j}^{*}$

注：

对任意 $x\in R^{n}$ ， $π_{i}(x)$ 是向量x的与 $b_{1},b_{2},...,b_{i-1}$ 都正交的分量。

特别地， $\pi_{i}(b_{i})=b_{i}^{*}$ ， $\pi_{i}(b_{i+1})=\mu_{i+1,i}b_{i}^{*}+b_{i+1}^{*}$ 。

LLL约化基

定义：给定实数 $\delta$ ，一组基 $b_{1},b_{2},...,b_{n}$ 称为 $\delta-LLL$ 约化的，如果满足

1. $|\mu_{i,j}|\leq \frac{1}{2},1<j<i\leq n$ ;

2. $\delta||\pi_{i}(b_{i})||^{2} \leq ||\pi_{i}(b_{i+1})||^{2},1\leq i <n$ 。

注：

如果 $\frac{1}{4}<\delta<1$ ，LLL算法可以在多项式时间内计算 $\delta-LLL$ 约化基。
第一个条件称为长度约化条件。

注记：

第二个条件称为Lovasz条件。由于 $\pi_{i}(b_{i})=b_{i}^{*}$ ， $\pi_{i}(b_{i+1})=b_{i+1}^{*}+\mu_{i+1,i}b_{i}^{*}$ ，上述条件又可写成：

$||b_{i+1}^{*}||^{2} \geq (\delta - \mu_{i+1,i}^{2})||b_{i}^{*}||^{2} \geq (\delta - \frac{1}{4})||b_{i}^{*}||^{2}$ 。

因此Lovasz条件保证了 $b_{i+1}^{*}$ 的长度不会比 $b_{i}^{*}$ 的长度短太多。

注记

$(b_{1},b_{2},...,b_{n})$ 可以由 $(b_{1}^{*},b_{2}^{*},...,b_{n}^{*})$ 给出的单位正交基表示：

$(b_{1},b_{2},...,b_{n})=(\frac{b_{1}^{*}}{||b_{1}^{*}||},\frac{b_{2}^{*}}{||b_{2}^{*}||},...,\frac{b_{n}^{*}}{||b_{n}^{*}||})T$ ，其中

$T=\left[ \begin{matrix} ||b_{1}^{*}|| & \mu_{2,1}||b_{1}^{*}|| & ... & \mu_{n,1}||b_{1}^{*}||\\ 0 & ||b_{2}^{*}|| & ... & \mu_{n,2}||b_{2}^{*}||\\ ... & ... & ... & ...\\ 0 & 0 & ... & ||b_{n}^{*}||\\ \end{matrix} \right]$

根据约化基定，义中的长度约化条件，T中的参数满足 $|\mu_{i,j}|\leq \frac{1}{2}$ 。考虑T中的子矩阵 $\left( \begin{matrix} ||b_{i}^{*}|| & \mu_{i+1,i}||b_{i}^{*}|| \\ 0 & ||b_{i+1}^{*}|| \\ \end{matrix} \right)$ 。根据约化基定义中的Lovasz条件，这个子矩阵第二列的向量的长度和第一列向量的长度是差不多的。

LLL约化基的性质

定理：设 $b_{1},b_{2},...,b_{n}$ 是n维格L的一组 $\frac{3}{4}-LLL$ 约化基，那么

1. $det(L)\leq \prod_{i=1}^{n}||b_{i}||≤2^{\frac{n(n-1)}{4}}det(L)$ ;

2. $||b_{j}||\leq 2^{\frac{i-1}{2}}||b_{i}^{*}||,1\leq j<i\leq n$ ；

3. $||b_{1}|| \leq 2^{\frac{n-1}{4}}det(L)^{\frac{1}{n}}$ ；

4. 对L中任一线性无关向量组 $x_{1}, x_{2},...,x_{t}$ ，一定有 $||b_{j}||\leq 2^{\frac{n-1}{2}}max\{||x_{1}||,||x_{2}||,...,||x_{t}||\},1\leq j\leq t$ 。

特别地，对L中的任意向量x，有 $||b_{1}||\leq 2^{\frac{n-1}{2}}||x||$ 。

2维的一一般情况：Lagrange-Gauss算法

1. 约化步： $b_{2}\leftarrow b_{2}-cb_{1}$ ，此处 $c=[\frac{<b_{2},b_{1}>}{<b_{1},b_{1}>}+\frac{1}{2}]$ ；

2. 交换步：若 $||b_{1}|| > ||b_{2}||$ ，则交换 $b_{1} \Leftrightarrow b_{2}$ ；如果 $(b_{1},b_{2})$ 不是约化基，重复上述步骤。

注：

约化步是在投影方向上进行最大的整数倍约化，满足Gram- Schmidt正交化中的 $|μ_{2,1}|\leq 1/2$ 。
交换步是进行辗转约化。

LLL算法

LLL算法的正确性分析

算法的约化步是为了使得LLL-约化基的第一条性质成立。
算法的交换步是为了保证LLL-约化基的第二条性质成立。
因此，LLL算法停止时输出的是一组LLL-约化基。

LLL算法时间复杂度分析

定理：
若输入的基为 $b_{1},...,b_{n}$ ，设 $M=max\{||b_{1}||^{2},...,||b_{n}||^{2}\}$ ，则LLL算法的时间复杂度是 $O(n^{6}log^{3}M)$ 。

注：

证明中的一个重要技巧是定义 $D_{B}=\prod_{i[=1}^{n}(||b_{1}^{*}||||b_{2}^{*}||...||b_{i}^{*}||)$ ，然后考虑 $D_{B}$ 的变化情况。

SageMath示例

LLL算法的应用举例

多项式时间分解有理系数多项式。
当变量个数为常数时,多项式时间求解整数规划问题。
分析基于背包问题的密码体制。
求同余方程的小整数解。
分析特殊参数下的RSA密码体制。

注
基本方法：针对不同的问题，构造合适的格，将相应的问题转化为求解格中短向量问题。

问题1：背包问题

问题
背包问题（也称为子集合问题）是指给定集合 $A=\{a_{1},a_{2},...,a_{n}\}$ 和目标元素s，求解 $e_{1},e_{2},...,e_{n} \in \{0,1\}$ 使得 $\sum_{i=1}^{n}{e_{i}a_{i}}=s$ 。

背包问题被证明是NP-完全问题。
可以基于某些背包问题参数设计密码体制，例如Merkle-Hellman体制.
很多基于背包问题的密码体制是不安全的。

背包问题的初步分析

固定大整数 $N>\sqrt{n}$ ，构造格L

$\left( \begin{matrix} 1 & 0 & ... & 0 & \frac{1}{2} \\ 0 & 1 & ... & 0 & \frac{1}{2} \\ ... & ... & ... & ... & ... \\ 0 & 0 & ... & 1 & \frac{1}{2} \\ Na_{1} & Na_{2} & ... & Na_{n} & Ns \\ \end{matrix} \right)$

如果子集合问题有解，那么 $\pm (e_{1}-\frac{1}{2},e_{2}-\frac{1}{2},...,e_{n}-\frac{1}{2},0)$ 是格L中的短向量。

例：

给定集合 $A=\{10,12,17, 23\}$ 和目标元素 $s=39$ ，求解对应的背包问题。

选取N=1000，得到组合系数为 $(1,1,1,0)$ 。

问题2：同余方程的小整数解

给定次数为d的整系数多项式 $f=a_{d}x^{d}+...+a_{1}x+a_{0}$ 和因子分解未知的大模数N，求不超过一定上界的 $x_{0}\in Z$ 满足 $f(x_{0})\equiv 0(modN)$ 。

如果知道N的因子分解，应用孙子定理可以快速求解上述问题。

如果N的因子分解未知，Coppersmith提出了一种应用LLL算法的求解方法。

基本思路：应用LLL算法构造另外一个整系数多项式g(x)满足 $g(x_{0})=0$ ，而求解整系数多项式的整数根有高效的算法。

问题初步分析

考虑多项式的向量表示：

$f(x)=a_{d}x^{d}+...+a_{1}x+a_{0} \Leftrightarrow (a_{0},a_{1},...,a_{d})$

多项式的向量表示构成格：给定多项式 $f_{1}(x),...,f_{k}(x) \in Z[x]$ ，定义格 $L=\{\sum_{i=1}^{k}{c_{i}f_{i}(x)}|c_{i} \in Z\}$ 。

如果对任意 $1\leq i\leq k$ ，都有 $f_{i}(x_{0})\equiv 0(mod N)$ ，那么对任意 $g(x) \in L, g(x_{0})\equiv 0(mod N)$ 。

模方程的转化

定理（Howgrave-Graham）

设 $g(x)\in Z[x]$ 是一个至多有w个单项式的多项式，h是正整数，如果：

1. $g(x_{0})\equiv 0 (mod N^{h})$ ，这里 $|x_{0}|<X$ ，

2. $||g(xX)||<\frac{N^{h}}{\sqrt{w}}$ 。

那么 $g(x_{0})=0$ 。

证明：验证 $|g(x_{0})|=|g(X\cdot \frac{x_{0}}{X})|\leq \Sigma|a_{i}X^{i}|\cdot |(\frac{x_{0}}{X})^{i}|<\frac{N^{h}}{\sqrt{w}}\cdot \sqrt{w}=N^{h}$ ，因为 $N^{h}|g(x_{0})$ ，所以 $g(x_{0})=0$ 。

Coppersmith算法框架

1. 构造合适的格。构造多项式 $f_{i,j}(x)=N^{h-j}x^{i}(f(x))^{j}$ ，这里 $0\leq i<d,0\leq j\leq h$ ，满足性质： $f_{i,j}(x_{0})\equiv 0(mod N^{h})$

2. 求解短向量。考虑格 $L=\left\{ \sum_{i,j}{c_{i,j}f_{i,j}(xX)|c_{i,j}}\in Z \right\}$ ，求格中的一个短向量对应的多项式 $g(xX)$ 。

3. 模方程转化。验证如果Howgrave-Graham定理的条件成立，求解方程 $g(x)=0$ 。

Coppersmith定理

设N是一个未知因子分解的整数， $b≥N^{β}$ 是N的一个因子， $f_{b}(x)$ 是一个单变量首一的次数为 $\delta$ 的多项式，那么可以找到方程 $f_{b}(x)\equiv0(modb)$ 的满足条件： $|x_{0}| \leq \frac{1}{2}N^{\frac{\beta^{2}}{\delta}-\varepsilon}$ 的解，算法的时间复杂度是 $O(\delta^{6}\varepsilon^{-7}log^{3}N)$ ，这里 $\varepsilon$ 是一个任意小的正数。

注记

Coppersmith还设计了利用LLL算法求解二元模多项式方程小整数解的算法。
相关的求模多项式方程小整数解算法在RSA密码算法的分析中有很多应用。
例如假设RSA模数N=pq。其中p，q是比特长度相同的素数，如果知道p的 $\frac{1}{4}log_{2}N$ 高位（或低位）比特值，那么可以在多项式时间内分解N。