单就讲讲对称的全同态加密。也不能叫对称吧，反正就是 cipher，加密解密都是同一个密钥。叫私钥加密又容易误解。反正懂的都懂，HE 的典中典了。
反正也可以用常规手段变为非对称公钥加密方案：一般做法是上文的人可以用加解密的私钥对很多 0 进行加密作为公钥，另一个想要用这个公钥进行加密的人先将这些加密后的 0 线性组合，再将它与想要加密的消息相加。这样无法得知消息，也无法得知加密公钥的私钥，因为是同态的最终也可以用私钥进行解密。感觉不是 0 也可以，还是看的太少
简单起见只看 2bit 的消息 $m\in\qty{0,1,2,3}$，用 $q$ 阶随机格 $\Lambda_{q}(\mathbf{A})$，其中 $q=n^4$，$n$ 是 2 的幂，所以 $q$ 也是 2 的幂。记法上用 $\pqty{\mathbf{A,B}}$ 表示这俩矩阵的垂直堆叠，$\bqty{\mathbf{A,B}}$ 表示矩阵的水平连接。所以 $(x_1,\ldots,x_n)$ 表示列向量，$[x_1,\ldots,x_n]$ 则是行向量。
咋用 $\mathrm{LWE}$ 加密
从
\[\mathbf{A}\stackrel{\$}{\gets}\mathbb{Z}^{n\times m}_q,\\ \mathbf{s}\stackrel{\$}{\gets}\mathbb{Z}^{n}_q,\mathbf{e}\stackrel{\chi}{\gets}\mathbb{Z}^{m}_q,\\ \mathbf{b}=\mathbf{A}^T\mathbf{s+e}\]恢复出 $s$。也可以表示成从
\[\bar{\mathbf{A}}=\pqty{\mathbf{A}, \mathbf{b}^{T}}\in\mathbb{Z}^{(n+1)\times m}\]恢复出 $s$。这就是 $\mathrm{LWE}$ 问题，是一个在 $q$ 阶随机格
\[\Lambda_{q}(\mathbf{A})=\qty{\mathbf{A}^{T} \mathbf{x} \mid \mathbf{x} \in \mathbb{Z}_{q}^{n}}+q \mathbb{Z}^{m}\]里的 $\mathrm{BDD}$ 问题的平均情况版本。目标向量是 $\mathbf{b}$。这个式子也算是随机格同余定义另一种表达形式吧。在适当的 $\mathbf{e}$ 分布下(离散高斯分布？)，这个问题已知与 n 维格上的各种近似格计算问题的最坏情况复杂度相当，也已知如果 $\mathrm{LWE}$ 困难，则其伪随机，i.e.，分辨均匀随机的 $\mathbb{Z}^{(n+1)\times m}$ 与 $\bar{\mathbf{A}}$ 计算不可行。
这里咱不用特定性质的误差向量分布，只把他看成能吐出无限范式比 $q$ 小很多的短向量 $\norm{\mathbf{e}}_{\infty} \leq \beta$，且关于原点对称，i.e.，$\chi$ 和 $-\chi$ 是相同的分布。通常 $\beta=\sqrt{n}$，这也是这个理论成立的最小值。
全同态之前先整个简单 $\mathrm{LWE}$ 密文加密开开胃。总体思想是因为 $\bar{\mathbf{A}}$ 是伪随机的，咱可以把他当成一个一次性密码本。定义加密为：
\[\mathbf{C}=\bar{\mathbf{A}}^{T}+m \mathbf{G}^{T}=\bqty{\mathbf{A}^{T}, \mathbf{A}^{T} \mathbf{s}+\mathbf{e}}+m \mathbf{G}^{T}\]确实就是一次性密码本的用法。$\mathbf{G}\in\mathbb{Z}^{(n+1)\times m}_ q$ 是一个精挑细选的能编码消息 $m$ 的矩阵。按照这个加密方法，$\mathrm{LWE}$ 的安全性紧随所使用的 $\mathrm{LWE}$ 矩阵的伪随机性。如果 $\bar{\mathbf{A}}$ 完全均匀随机，则密文和明文统计学独立。
$\bar{\mathbf{A}}=\pqty{\mathbf{A}, \mathbf{b}^{T}}$ 也可以看成是一个特定格 $\Lambda_ q\pqty{\bar{A}}$。咱知道如果 $\bar{A}_ q$ 均匀随机的选择，那么 $\Lambda_ q\pqty{\bar{A}}$ 似乎不会含有任何长度比 Minkowski 定理短很多的向量，但 $\Lambda\pqty{A_ q}$ 有：
\[\bar{\mathbf{A}}^{T}\pqty{-\mathbf{s}, 1}=\bqty{\mathbf{A}^{T}, \mathbf{b}}\pqty{-\mathbf{s}, 1}=\mathbf{b}-\mathbf{A}^{T} \mathbf{s}=\mathbf{e} \enspace(\bmod q)\]那就可以把这样的向量
\[\bar{\mathbf{s}}=\pqty{-s,1}\]当成 $\Lambda_ q\pqty{\bar{A}}$ 对应的密钥。解密就像这样用 $\bar{\mathbf{s}}$ 对密文向量线性组合，就得到了：
\[\mathbf{C} \bar{\mathbf{s}}=\pqty{\bar{\mathbf{A}}^{T}+m \mathbf{G}^{T}} \bar{\mathbf{s}}=\mathbf{e}+m \mathbf{G}^{T} \bar{\mathbf{s}} \approx m \mathbf{G}^{T} \bar{\mathbf{s}} \enspace(\bmod q)\]咱发现这个约等号成立的条件是消息 $m$ 最终需要能够从 $\mathbf{e}+m \mathbf{G}^{T} \bar{\mathbf{s}}$ 中恢复出来。$\mathrm{LWE}$ 密文加密方案简单的选取 $\mathbf{G}$ 为单一一个向量：
\[\mathbf{g}=\pqty{0, \ldots, 0, q / 4} \in \mathbb{Z}_{q}^{n+1}\]相似的，$\mathbf{A}=\mathbf{a} \in \mathbb{Z}_{q}^{n}$ 也只是一个向量，$\mathbf{e}=e\in\mathbb{Z}_q$则是一个标量。按照这些个简单约束可以搞一个加密方案，密文空间还是上文说的 $\qty{0,1,2,3}$。
定义 1 明文空间为 $\qty{0,1,2,3}$ 的 $\mathrm{LWE}$ 密文加密方案这么搞：
- 密钥 $\mathbf{s}\stackrel{$}{\gets}\mathbb{Z}^{n}_q$.
- 加密算法输入 $\mathbf{s}$ 和 $m\in\qty{0,1,2,3}$，选 $\mathbf{a}\stackrel{$}{\gets}\mathbb{Z}^{n}_q,e\gets \chi$，输出密文
- 解密算法输入密钥 $\mathbf{s}$ 和密文 $\mathbf{c}^T=\bqty{\mathbf{a},b}$，上文的解密流程就给密文乘个 $\bar{\mathbf{s}}$，这里对应所指定的 $\mathbf{G}$，$e$ 在特定分布下则解密成功，等同于对 $m$ 加上 $e$ 相关参数并向下取整，输出：
因为 $q=n^4$ 所以 $q/8$ 也是个整数，并且 $v=q / 8+\mathbf{c}^{T} \bar{\mathbf{s}} \in \mathbb{Z}_{q}$ 的值计算的时候也要 mod q。最终输出的 $\lfloor 4 v / q\rfloor$ 取决于 $v$ 的两个bit的值。很容易能知道
定理 2 如果 $\abs{e}<q / 8$ 那么解密算法能正确恢复出 $m$。，i.e.，
\[\operatorname{LWE}_{\mathbf{s}}^{-1}\left(\operatorname{LWE}_{\mathbf{s}}(m)\right)=m\]证明： 解密算法输出
\[\left\lfloor(4 / q)\left((q / 8)+\mathbf{c}^{T} \bar{\mathbf{s}}\right)\right\rfloor=\lfloor(4 / q)((q / 8)+e+m q / 4)\rfloor=\lfloor(1 / 2)+4 e / q+m\rfloor=m\]因为 $1 / 2+4 e / q \in[0,1)$。感觉也没啥好证的，毕竟就是这么设计的。
跟其他大多数加密算法不同，格密码里面密文不尽相同，也有好坏，这好坏由错误分布 $\abs{\mathbf{e}}\leq\beta$ 体现。为啥这玩意这么重要：
-
第一典当然是正确性。这密文要能正常解密。像上面那个例子如果 $\beta>q/8$ 则解密可能会失败。
-
典中典当然是安全性。假设不带这个 $\mathbf{e}$ 玩，这玩意就变成解线性方程组了，直接高斯消元。实际上格计算问题的最坏情况复杂度的归约要求 $\beta\geq\sqrt n$，并且当 $\beta=o(\sqrt n)$ 时就可以用 relinearization techniques 以亚指数时间破解。
于是一个 $\mathrm{LWE}$ 加密就可以表示成 $\mathrm{LWE}\bqty{m,\beta}$，意思是明文是 $m$，噪音 $\abs{\mathbf{e}<\beta}$ 能使她既安全又可行。
Computing on Ciphertexts
讲了半天没讲到同态。实际上这玩意只能说是(近似)线性同态，支持加(addition)和非(negation)运算，等同于逻辑电路上 XOR 和 NOT 组成的自足链接词？
定理 3 如果 $\mathbf{c}_{0}^{T} \in \mathrm{LWE}_{\mathbf{s}}\left(m_{0}, \beta_{0}\right)$ 和 $\mathbf{c}_{1}^{T} \in \mathrm{LWE}_{\mathbf{s}}\left(m_{1}, \beta_{1}\right)$ ，那么：
-
$\left[\mathbf{0}^{T}, m q / 4\right] \in \mathrm{LWE}_{\mathbf{s}}(m, 0)$ 是一个无噪音的 $m$ 在 $\bmod\enspace 4$ 下的加密。就是 $\Lambda_q(A)$ 的原点。
所以 $q/4$ 的选择实际上是模数决定的？ -
$\mathbf{c}_{0}^{T}+\mathbf{c}_{1}^{T} \in \operatorname{LWE}\left(m_{0}+m_{1}, \beta_{0}+\beta_{1}\right)$ 是 $(m_0+m_1)$ $\bmod\enspace 4$ 下的加密。
-
$-\mathbf{c}_{0}^{T} \in \operatorname{LWE}\left(-m_{0}, \beta_{0}\right)$ 是 $(-m_0)$ 在 $\bmod\enspace 4$ 下的加密。
定理 3 达不到全同态因为：
-
加同态只对线性函数和仿射函数生效。FHE 应对任意函数/电路生效。
-
尽管只限于线性函数，上述的方案不允许任意次数的加运算。因为任意两次的密文相加都会使错误变得更大，最终超过上界使方案有几率无法正常解密。
咱通过一个刷新程序解决上述两个问题。输入密文 $\mathbf{c}^{T} \in \operatorname{LWE}[m, q / 8]$ 输出一个加密的
\[\small\operatorname{HALF}\normalsize(m)=\lfloor m / 2\rfloor \in\{0,1\} \subseteq\{0,1,2,3\}\]得用更小的 $\beta$，比如咱得
\[\mathbf{Refresh}\colon\mathrm{LWE}_{\mathbf{s}}\pqty{m,q/8}\to\mathrm{LWE}\pqty{\small\mathrm{HALF}\normalsize(m),q/16}\]能看出在线性函数下这个操作能让我们实现一个 NAND 门原来是 NAND，是逻辑电路的自足链接词：对于所有 $m_0,m_1\in\qty{0,1}$，
太难辣，布响学辣 XD 有空补完罢
结论
总之咱用一个刷新程序将累加器设置为 0 计算 $\small\operatorname{HALF}\normalsize(m)$ 的 $\mathrm{LWE}$ 加密，接着进行至多 $n\log q(\log q+1)/2$ 次 $\mathrm{A\small CCUM}$ 操作以及一系列不会增大累加器错误的操作。然后刷新程序 $\mathrm{LWE}_{\mathbf{Z}}\pqty{\small\mathrm{MSB}\normalsize\pqty{v},\beta’}$ 噪声最大能有
\[\beta^{\prime} \leq n \log q(\log q+1) N \gamma(n+1) \log q=2 n^{2.5}(n+1) \log ^{3} q(\log q+1)=O\left(n^{3.5} \log ^{4} n\right)\]$n$ 足够大的话，是可以小于期望的 $q/16=\Omega(n^4)$ 的。
另外，看不懂的文字告诉我 circular security 的证明是一个很重要的公开问题。
