之前看过一次，根本看不懂，现在隔这么久，再次阅读，希望有所收获！
论文版本：Homomorphic Evaluation of the AES Circuit(Updated Implementation)
- 首先明白AES电路是什么？
暂且理解为AES加密算法，以电路的形式实现。
注：bootstrapping 自举；key switching 密钥交换； modulus switching 模交换
介绍#
- 使用Leveled-FHE方案（BGV）加密和同态计算（不用自举），使用同态库（HElib）
- 使用SIMD编码技术
- 使用模交换和密钥交换技术改进版
AES电路#
当对使用AES加密的数据进行计算时，AES同态解密就是将用AES加密的数据转换为用，FHE加密的数据，然后执行计算。
环表示#
符号表示#
-
[z]q：整数z模q，范围在(−q/2,q/2]
-
m次分圆多项式：Φm(X)，阶数为ϕ(m)，即多项式的最高次幂为ϕ(m)，例如Φm(x)=(x−a1)(x−a2)...(x−aϕ(m))，阶是ϕ(m)
-
模q的多项式环：Aq=Z[X]/(Φm(X)) ，即整系数的多项式（模Φm(x)和模q）集合，阶数为ϕ(m)−1
多项式表示#
一个m次分圆多项式Φm(X)包含m次本原单位根ζ，m次分圆多项式可以拆分为若干个多项式相乘，即Φm(X)=∏i(X−ζi)(modq)
m次本原单位根有ϕ(m)个
给定一个多项式a∈Aq，有两种表示方法：：系数表示法（coefficient representations）和计算表示法（evaluation representation）
系数表示法#
可以将a看作一个阶为ϕ(m)−1的多项式，即a(X)=∑i<ϕ(m)aiXi，列出所有的系数表示这个多项式，即a=<a0,x1,...,xϕ(m)−1>∈(Z/qZ)ϕ(m)，这就是系数表示法
计算表示法#
将m次本原单位根ζ带入多项式a(X)，即bi=a(ζi)，会得到ϕ(m)长的向量，即(b0,b1,...,bϕ(m))，这就是计算表示法
转换#
可以看出，这两种表示法是通过b=Vm.a转换的，其中Vm是一个基于m次本原单位根的范德蒙矩阵(modq)，即(a(X)mod(X−ζi))=a(ζi)=bi，因此用计算表示法的a是一个多项式的中国剩余定理的表示 (CRT表示法)。
上面是基于CRT实现的转换，还有其他的方法：牛顿插值法、拉格朗日插值法、**快速傅立叶变换（FFT）更多请参考：FFT
上面两种表示法，都可以将一个多项式a∈Aq表示为一个长ϕ(m)的整数向量。如果q是一个"复合体"，这些整数每一个都可以用标准二进制编码（ standard binary encoding）或者用CRT（ Chinese-Remaindering）。我们一般在系数表示法中使用标准二进制编码，计算表示法中使用CRT。
所以后者也叫做双CRT表示（double CRT representation），对应于Φm(X)和q所拆分的因子。
这里的q说是一个"复合体"，可以看作是一个很大的数
多项式计算#
由于是基于多项式环上的计算，所以会有很多整数多项式间的计算。例如：模乘（modular multiplications），模加（modular additions）， Frobenius映射（用于快速计算次幂xa）。
大部分的计算可以在计算表示法下进行，另外标准的模交换和密钥交换需要在系数表示法下进行【密文中的噪音在系数表示法很小，在计算表示法下则不会】，所以在整个过程中，多项式需要在这两种表示下来回转换，这是最耗时的！所以在该方案中，将始终将密文保持在计算表示下，仅当某些操作需要时才转换为系数表示，然后再转换回来。该方案中描述的密钥交换和模交换的变体是可以在计算表示法下执行的，密钥交换还有一个优点：密钥交换矩阵的尺寸减少，这是影响性能的重要因素。
由于转换耗费计算量，所以本文也是一直做优化，减少转换次数。
BGV基础方案#
这里采用的是BGV变体方案[1]，密文和密钥都是在A上的向量，明文空间为A2，密文空间Aq
密钥【current secret key s】和模数【current integer modulus q】会随着同态计算而变化（密钥交换和模交换导致的）
给定一个结构：密文c，对应的密钥s、模数为q、明文为a，则解密结构为:
其中[⟨c,s⟩modΦm(X)]q叫做密文c的噪音，衡量噪音的大小用欧几里德范数，即噪音的大小为：
以下再提到范数，即欧几里德范数（l2范数）
噪音需要足够小，这样密文才有效，所以噪音满足一定的界限。
这里的BGV方案提供5个同态计算：加法（ addition）、乘法（ multiplication）、"自同构"（automorphism）、密钥交换（key-switching）和模交换（modulus-switching）：
加法#
密文+密文，具体来说：两个密文c1,c2∈Aq，对应的明文为a1,a2∈A2，具有相同的密钥和模数q，相加后c1+c2∈Aq，对应的明文为a1+a2∈A2。
相加后模数和密钥不变，噪音累加。
乘法#
密文*密文(张量积)，具体来说，两个密文c1,c2∈Aq，对应的明文为a1,a2∈A2，具有相同的密钥和模数q，相乘后c1∗c2∈Aq，对应的明文为a1∗a2∈A2。
模数不变，密钥维数翻倍(n->n2)，噪音剧增。
密钥交换#
需要密文的范数远小于q
转换密文的密钥，具体来说（密文，密钥，模数）：
(c′,s′,q)->密钥交换->(c,,s,q)
主要用作在密文*密文后，密钥的维数增长，这时需要使用密钥交换，把密钥的维数降下去。假设s′的维数为n2，s的维数为n。
进行密钥交换，需要一个交换矩阵W=W[s→s]∈Aq，W的第i列近似表示为s′的第i个元素的加密。"近似"转换：c=W.c′ ，例如：
s的第i个元素为s′i∈A（范数远小于q），W的第i列为一个n维向量wi，则
其中，ei的范数很低，那么对于e=(e1,e2,..,en′)，有sW=s′+2e∈Aq，对于任意的密文c′，设c=W.c′∈Aq，则有：
可以看出，由于[<c′,s′>modΦm(X)]q的范数远小于q，而且e的范数远小于q，故[[<c,s>modΦm(X))]q]2=[[<c′,s′>modΦm(X)]q]2
总的来说，密钥交换改变了密钥，模数没有改变，噪音增加了2||<c′,e>||2。
模交换#
模交换用来减少噪音的范数，具体来说（密文，密钥，模数）：
(c,s,q)->模交换->(c′,,s,q′)
其中，新模数q′给定，c′=c.q′/q，c乘以q′/q，得到了一个"分数密文"，然后通过四舍五入得到整数密文c′。模交换需要满足两个前提条件：
- c′=c(mod2)
- 四舍五入产生的噪音范数很小，即τdef←c′−(q′/q)c的范数很小
c和c′的转换是用系数表示法，只要密钥s的范数足够小和q′<<q，则噪音的大小就可以降低！
因为模数改变，所以BGV方案需要提前准备"一串"模数，即模数链（chain of moduli），q0<q1<...<qL−1，从小到大，L为方案的级数（层数），对于"新鲜密文"对应的模数为qL−1，即最大。
同态计算（一般指乘法）后密文的噪音过大，需要执行模交换将模数从qi转换为qi−1，噪音降低。直到模数为q0，就不能进行同态计算了，所以才叫做有限级数的FHE（Leveled-FHE）。
自同构#
定义一种映射:
使得a(X)∈A转换为a(i)(X)def←a(Xi)modΦm(X)
也是一种对密文的运算，具体来说（密文，密钥，明文）：
(c,s,a)->自同构->(c(i),s(i),a(i))
具体没看懂，涉及到伽罗瓦群的概念，后面补充
打包密文#
明文空间:A2可以看作是一个"plaintext slots"向量，具体说：若分圆多项式Φm(X)能拆分为l个不可约多项式的乘积，即Φm(X)=∏l−1j=Fj(X)(mod2)，则一个明文a(X)∈A2可以被看作是l个小多项式的编码而成，即aj(X)=a(X)modFj(X)，这里的aj(X)modFj(X)是一个slot，因此我们可以用它表示扩域GF(2d)上的一些元素。
为什么可以表示，或许是扩域的性质吧
附录#
明文槽(plaintest slot)#
多项式环：A=Z[X]/Φm(X)
明文空间：A2
密文空间：Aq
分圆多项式Φm(X)可以分为l个不可约多项式的乘积，即Φm(X)=F1(X).F2(X)....Fl(X)(mod2)，其中Fi(X)的最大阶数为d=ϕ(m)/l，每一个Fi(X)对应一个"plaintest slot"，所以a∈A2可以表示为一个l长的向量(amodFi(X))li=1
伽罗瓦群Gal=Gal(Q(ζm)/Q)包含一个映射:
并且a(xk)与(Z/mZ)∗同构。
等学完伽罗瓦群后再回看
标准嵌入范数（Canonical embedding norm）#
双CRT表示（Double CRT）#
分圆多项式Φm(X)包含m次本原根，可以分为本原根的乘积：Φm(X)=∏i∈(Z/mZ)∗(X−ζj)(modq);
模数q可以拆分为多个素数相乘q=∏ti=0pi;
所以一个密文a∈Aq可以表示为一个(t+1)∗ϕ(m)的矩阵（以Φm(X)modpi包含m次本原根为元素），即：
其中，这种表示法可以用t+1次FFT算法(模 pj)，如下：
一次FFT，可将一个多项式"解码为"一组数（向量）编码；而逆操作，则需t+1次IFFT算法(模 Φm(X)模 pj)，如下：
一次IFFT，可以将一组数（向量）"编码为"一个多项式
这种表示法也具有同态乘法和加法：
参考#
1、Fully Homomorphic Encryption with Polylog Overhead