Gaussian Heuristic
\[gh(n)=\sqrt{n/2\pi e}\]Gauss Lattice Reduction求二维最短向量（SVP）：v2减去整数倍的v1尽量使得v2变得更短。
LLL 算法可以看作是二维格上高斯约化算法在更高维数格上的扩展。LLL算法及其变种算法是目前已知在较低维度的lattice中求解SVP的最好的算法，但是在较高维度中就比较乏力。
NTRU（Number Theorists Research Unit）
\[加密：h=f^{-1}*g\mod p，c=r*h+m\mod p\\左式代入右式，c=r*(f^{-1}*g)+m\mod p\\两边同乘f：c*f=r*g+m*f\mod p\\当找到一组f，g满足，r*g+m*f小于p（m长度较小）时可用于解密，有：(c*f\%p)=r*g+m*f\ (1)\\对两边取模g：(c*f\%p)=r*0+m*f\mod g\\由于f，g可从h求得，m=(c*f\%p)*f^{-1}\%g\\f*h=g\mod p，因此，f*h-u*p=g\\构造M=\left[\begin{matrix} 1 & h\\ 0 & p\\ \end{matrix}\right]\\(f,-u)M=(f,-u)\left[\begin{matrix} 1 & h\\ 0 & p\\ \end{matrix}\right]\\=(f+(-u)*0, f*h+(-u)*p)\\=(f,g)\\因此(f,g)在格M上\\基向量长度：||(1,h)||=\sqrt{1^2+h^2}=2^{2000}，||(0,p)||=\sqrt{0^2+p^2}=2^{2048}\\根据Gaussian heurstic可知，在这个lattice中最短向量的长度大概在\sqrt{2^{2048}}=2^{1024}\\若f，g足够小，很大概率上，这个(f, g)就是这个lattice的最短向量，可通过LLL算法求解一组满足的(f,g)用于解密\]Babai’s nearest plane algorithm
\[该算法用于计算CVP问题的近似解，近似因子为\gamma = 2^{\frac{n}{2}}\]1 | |
sample：HNP（Hidden number problem），guess_number-BCTF-2018
\[给定质数p、许多t以及每一个对应(a*t\mod p)的l个最高有效位MSB_{l,p}(a*t)，求对应的a\\其中MSB_{l,p}(x)表示任一满足\lvert(x\mod p)-u\rvert \le \frac{p}{2^{l+1}}的整数u，近似为取x\mod p的l个最高有效位。\\当l\approx \log^{\frac{1}{2}}{p}时，可以将此问题转化为一个由该矩阵生成的格上的CVP问题：\\\left[ \begin{matrix} p & 0 & \dots & 0 & 0 \\ 0 & p & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & 0 & \dots & p & 0 \\ t_1 & t_2 & \dots & t_{n} & \frac{1}{2^{l+1}} \end{matrix} \right]\\需要找到在格上离u=(u_1, u_2, \dots, u_{n}, 0)最近的向量，可以采用Babai's nearest plane algorithm，\\可以得到一组向量v=(a*t_1\mod p, a*t_2\mod p, \dots, \frac{a}{2^{l+1}})，从最后一个值算出a。\]GGH Cryptosystem，Nguyen’s Attack
GGH是基于CVP的非对称加密算法，加密过程：c=m*B+e，已知c、B，求m。
- m为明文，c为密文，均为
1*n向量 - B为公钥组成的
n*n向量 - e为
1*n向量，每一项为3或者-3
Nguyen’s Attack攻击方式： \(令s=(3,3,...,3)向量，式子两边同时加上s，取模6\\c+s=m*B+(e+s)\mod 6\\s+e每一项不是6就是0，取模6之后也是0，因此有：\\c+s=m*B\mod 6\\求得m取模6的结果，记为m_6,式子两边同时减去m_6*B：\\c-m_6*B=(m-m_6)*B+e\\其中，(m-m_6)必为6的倍数，计为6*m'，上式两边同时除以6：\\\frac{c-m_6*B}{6}=\frac{(m-m_6)*B}{6}+\frac{e}{6}\\c'=\frac{c-m_6*B}{6}=m'*B+\frac{e}{6}\\c'可以计算出来，误差向量e变成了原来的1/6，这样就构建出了一个更加简单的CVP\\然后可以利用embedded\ technique，将CVP转化为SVP，再利用LLL算法求得m'，最后求得m\)
LWE（Learning With Errors）
LWE实际上跟GGH很类似，都是一个向量，经过矩阵变换后，加上了一些误差向量，得到一个结果向量；然后就很难反推回去。LWE与GGH不同的一点在于，GGH中的误差向量的选取是3或者-3，而LWE的误差向量则是一个满足正态分布的小向量。
对于s*A+e=a，A是一个格子，然后这个格子基底的线性组合b=A*s，是这个格子上的一个格点，然后这个格点b加上一个误差向量e，得到一个非格点a。LWE就是要找到离这个非格点a最近的一个格点（CVP）。
Babai’s Nearest Plane方式解
在s长度小的时候，可以采用如下构造方式（维度高了后，LWE就很难了）： $$ LWE的式子：s_0 a_{i,0} + s_1 a_{i,1} + \cdots + s_{24} a_{i,24} \equiv a_i - e_i \pmod{p}\s_0 a_{i,0} + s_1 a_{i,1} + \cdots + s_{24} a_{i,24} + k_ip + e_i = a_i\那么可以构造矩阵L：\s \times L + e = \begin{bmatrix} s_0, s_1, \cdots, s_{24}, k_0, k_1, \cdots, k_{39} \end{bmatrix}\begin{bmatrix} a_{0,0} & a_{1,0} & \cdots & a_{39, 0}\newline a_{0,1} & a_{1,1} & \cdots & a_{39, 1}\newline \vdots & \vdots & \ddots & \vdots \newline a_{0,24} & a_{1,24} & \cdots & a_{39, 24}\newline p & 0 & \cdots & 0\newline 0 & p & \ddots & 0\newline 0 & 0 & \cdots & p\newline \end{bmatrix}
-
[e_0, e_1, \cdots, e_{39}]
[a_0, a_1, \cdots, a_{39}] = a\先对矩阵L进行规约，得到一个good\ basis，再用Babai’s\ algorithm求解CVP，即可得到离a最近的格点b\然后，在模p的整数环里，求解方程A_{lwe} \cdot s = b^{T}，得到s $$