浅析GGH加密
上一篇对于 LWE 问题的理解可把我折磨坏了，接下来再看看 GGH 加密；
GGH加密
1. 基础概念
这种加密方法是由 Goldreich、Goldwasser、Halevi 三人在 1997 年发明的，是关于 CVP 难题的算法，据说是启发于 Ajtai 在格难题上的研究；
但是遗憾的是在 1999 年就被 Nguyen 设计的算法给破解了，直接将其转化为一个简单的 CVP 问题；(°ー°〃)
基本的 GGH 选取一组 good basic B 和一个幺模矩阵 U 作为私钥，计算得到\(B_0=UB\)作为公钥；
Enc过程：
- 明文\(m=(m_1,m_2,……,m_n)\)，误差向量 e 和公钥\(B_0\)，计算\(a=m*B_0=\Sigma m_ib_{0i}\)；
- 得到\(c=a+e=mB_0+e\)；
Dec过程：
- \(cB^{-1}=(mB_0+e)B^{-1}=mUBB^{-1}+eB^{-1}=mU+eB^{-1}\)；
- 当\(eB^{-1}\)足够小时，可以通过 babai 算法来得到最近向量；
- 然后\(m=mUU^{-1}\)，结束；
2. 分析过程
在加密过程中，误差向量 e 的每一项不是 3 就是 -3 ，这给问题简化提供了条件；
我们的已知条件为 c、B，需要得到 m ；
先试着对上式模 3 运算\(c_3=m_3B_3+e_3 \ (mod \ 3)\)，考虑到 e 的数值，这里的式子就是：\(c_3=m_3B_3\ (mod\ 3)\)，因此可以得到明文 mod 3 的结果；
后来 Nguyen 分析出模 6 是一个更好的选择，先取\(s=(3,3,……,3)\)，可得 s+e 中每一项的值都是 6 或者 0，取模 6 后也 0；
式子两边都加上 s 得到：\(c+s=mB+(e+s)\)，取模后得到：\(c_6=m_6B_6\ (mod\ 6)\)，这样得到明文 mod 6 后的结果；
之后进行问题简化；
具体推导为：
\[c-m_6B=(m-m_6)B+e
\]