本节内容记录阅读该论文的笔记
介绍
首先，介绍了两种明文“打包”的方法：PVW和SV
PVW：对应论文(PVW:A framework for efficient and composable oblivious transfer)，打包思想就是，将多个bit明文是为一个明文向量。
SV：对应论文（SV11:Fully homomorphic SIMD operations），打包思想：将多个明文通过“编码”插入到一个多项式上，转换成多项式的计算相当于这么多明文计算。多用于基于RLWE方案的。
Regev简介
原paper：On lattices, learning with errors, random linear codes, and cryptography
加密单比特数据：系统参数/(q/in Z/)，明文比特/(b/in (0,1)/)，私钥/(s/)和密文/(c/)都是向量/(Z^n/)，
加解密
具体加解密参考：密码算法汇总
将明文/(b/)加密，密文是个向量，解密的私钥/(s/)也是向量，解密框架为:
/(z=<c,s>(mod q)=k.q+b.q/2+e(mod q)/)，其中/(e,k/)是小整数，/(z/)的范围为/([-q/2,q/2]/)，若/(|z|<q/4/)，则解密为0，否则为1。
同态计算
（1）加法
Regev本身支持同态加法计算，即/(E(b_1+b_2)=c_1+c_2(mod q)/)。
（2）乘法
在该paper：（BV11a：Efficient fully homomorphic encryption from (standard) LWE）中给出同态乘法运算：
这里的“乘法”是张量积，满足：/(E(b_1.b_2)=(c_1/bigotimes c_2/))，并满足/(<s_1,c_2>.<s_2,c_2>=<s_1/bigotimes s_2,c_1/bigotimes c_2>/)
张量积：参考（点积、张量积和范数）
下面就是如何构造乘法后的正确解密：
/(c^*=/left /lceil 2/q.(c_1/bigotimes c_2)/right /rfloor/)
则：/(z^*=<s/bigotimes s.c^*>=k^*.q+b_1b_2.q/2+e^*(mod q)/)，其中/(k^*,e^*/)也是相对较小的，所以参数选取适当的情况下，乘法后能正常解密！
可以看出，如果/(c_1,c_2/)是一个/(n/)维的向量的话，则/(c_1/bigotimes c_2/)是一个/(n^2/)维的矩阵，若在此基础上再进行一次乘法，则新密文的维数为/(n^4/)，可见存在一个问题：密文维数随着乘法次数而变大（指数级）。
所以需要一种方法去“降维”，即（BV11a）中给出的重线性化技术（re-linearization）将密文维数/(n^2/)将为/(n/)。
重线性化，实质上就是密钥交换技术（Key Switching），即给出两个密钥/(s,s’/)，使用密钥交换技术将密钥/(s’/)对应的密文转换为/(s/)对应的密文。密钥交换矩阵实际上包含用/(s’/)加密的/(s/)，这是一个矩阵（密钥交换矩阵），其实也是将/(s/bigotimes s/)转换为/(s/)
打包“压缩”明文
前面提到原始的Regev方案是加密单bit明文，密文和密钥都是向量，这样效率较低。
可以将多个密钥/(s_i/)按行组成一个矩阵/(S/)，可以加密一个明文向量/(b/)，解密时：/(z=S.c=k.q+b.q/2+e/)，其中/(k,e/)是小向量。（这里的密钥有多种？）
（1）打包明文的计算
还是和上面说的类似，加法(mod q)，乘法通过张量积。
只不过在乘法后执行重线性化时有些变化：
假设/(c^*/)是一个高维的“打包”密文，对于每/(i/)个明文/(b_ib_i’/)，对应的密钥为/(s_i/bigotimes s_i/)，现在如何进行重线性化呢？
选择一个合适的密钥交换矩阵（用/(s_i/)加密的/(s_i/bigotimes s_i/)），可以将/(c^*/)转换为一个新的密文/(c’/)，对应的密钥为 /(s_i/)。
（2）其他计算
可以在“打包”明文基础上实现SIMD同态计算、密文置换（permutation），并且使用PVW方法进行密文置换比使用SV方法更有优势。
SV方法，是通过自同构（automorphisms）实现，但是需要其他计算；而PVW是通过密钥交换实现的。
密文置换：移动密文内的slot，实现密文置换，解密后相当于明文置换。
基础
符号
（1）范数
/(||v||_1/)：欧式范数
/(||v||_{/infty }/)：无穷范数
具体参考：点积、张量积和范数
（2）其他符号
/(Z_q/)：表示范围在/([-q/2,+q/2]/)内的整数
/([a]_q/)：表示/(a mod q/)
/(/left /lceil a /right /rfloor/)：表示四舍五入
/(/left /lceil a /right /rfloor_q/)：表示/(/left [/left /lceil a /right /rfloor /right ]_q/)
LWE问题
安全参数/(n/)，模数/(q>poly(n)/)，/(/chi/)表示均值为0，标准差为/(q/ /beta/)的离散高斯分布，/(/beta =poly(n)/)
问：poly()表示什么意思？
关于LWE问题的困难性，在[Regev09]中给出了证明，表明能将LWE问题通过量子规约（quantum reductions）到/(n/)维格上的困难问题；在[Pei09]中给出了经典规约的方法（classical reductions）
SLWE
即搜索版本的LWE（search-LWE）：
对于/((a_i/in Z_q^n,b_i=[<s,a_i>+e_i]_q)/)，/(e_i/in /beta/) ，给出/(a_i,b_i/)，难以计算出/(s/)
DLWE
即判绝版本的LWE（decision-LWE）：
给出/(<a_i’/in Z_q^n,b_i’/in Z_q^n>/)和/((a_i/in Z_q^n,b_i=[<s,a_i>+e_i]_q)/)是难以区分的
Regev方案
一个基于LWE问题的公钥加密方案，这里给出了一个对称加密方案，可以通过范型变换（generic transformations）获得一个公钥加密方案。
范型变换？
明文空间/(Z_2=(0,1)/)，模数/(q/)，安全参数/(n’/),/(n=n’+1/)
这里介绍对称加密方案
密钥生成
密钥/(s’/in /chi ^{n’}/)，明文/(/sigma/in Z_2/)，选取/(a/in Z_q^{n’}/),/(e/in /chi/)（小向量）
加解密
计算/(b=[/sigma q/2-<s’,a>+e]_q/)，输出密文/((b,a)/)
解密：
计算/(d=[b+<s’,a>]_q=[/sigma q/2+e]_q/)，若/(d>q/4/)，则输出1，否则输出0。
解密成功的关键在于/(||e||_{/infty}<<q/4/)
上述解密可以看作：/(/sigma =/left /lceil [<s,c>]_q /(q/2)/right /rfloor_2/)，其中/(s=(s|s’),c=(b|a)/)都是/(n/)维向量。
/(<s,c>=kq+/sigma q/2+e/)，/(||<s,c>||_{/infty}<<q^2,|k|<<q/)。
以上基础的加密方案只需/(|e|<<q/4/)，下面在同态计算中，需要/(k，e<<q/)。
同态计算
若/(c_1,c_2/)是两个有效密文，分别对应的明文为/(b_1,b_2/in Z_2/)，使用的密钥是/(s/)，从上面可知，满足：/(<s,c_i>=k_iq+b_iq/2+e_i/)，其中/(k_i,e_i/)是很小的数。
（1）加法
对于/(c’=[c_1+c+2]/)，满足/(<s,c’>=k’q+(b_1/bigoplus b_2)q/2+e_i’/)，其中/(k’=k_1+k_2/) 或 /(k_1+k_2/pm 1<<q/)和/(e’=e_1+e_2 <<q/)。（这里的加法是异或）
所以/(c’/)是/(b_1+b_2/)的有效加密。
（2）乘法
在【BV11】和【Bra12】中给出了Regev的乘法同态。
对于/(c^*=c_1/bigotimes c_2/)（/(n^2/)维向量），/(s^*=s/bigotimes s/)，有乘法：
这里的/(e”/)是多项式大于（polynomially (n) larger ）/(e_1,e_2/)的，因为/(k_1,k_2/)是有范围的/(poly(n)/)
这里如何理解：polynomially larger？
见参考【1】
在这里的意思就是/(e”/e_1/)或者/(e”/e_2/)是有范围的！
下面将/(2/q.c^*/)四舍五入为整数向量，即求/(/left /lceil 2/q.c^*/right /rfloor=2/q.c^*+e/)，其中/(e/)是舍入误差，/(||e||_{/infty} /leq 1/2/)，则：
其中/(e^*/)是误差集合，/(k^*/)是一些整数，由于/(s^*=s/bigotimes s/)和/(e/)中元素很小，所以/(<s^*,e>/)也很小，且/(|e^*|<<q/)。
最后令/(c”=/left /lceil 2/q.c^*/right /rfloor_q/)，满足：
其中/(e^*<<q/)，/(k^*/)满足：
所以/(c”/)是/(b_1b_2/)的有效加密，密钥为/(s^*=s/bigotimes s/)。
密钥交换
上面可以看出，密文相乘后，维数扩张严重（指数级）。在【BV11a】中给出了方法-密钥交换技术，作用就是降维。
从上面密钥交换的简单介绍中，可知道主要功能：将一个维数为/(n^2/)维的密文/(c’/)，对应的密钥为/(s’/)，转换为一个新的密文/(c/)，其维数为/(n/)，对应的密钥为/(s/)。
下面介绍一种密钥交换的变体技术，相对更加简单。
（1）密钥交换需要一个密钥交换矩阵
密钥交换（/(s^*->s/)）可以看成：在密钥/(s/)下加密的/(s^*/)，详细点说：对于每一个/(s^*[i]/)，构造一个公开的“计算密钥”/(w_i/)（rational “ciphertext” ）,满足：/(<s,w_i>=k_iq+s^*[i]+e_i/)，其中/(k_1/)是一个整数，/(|e_i|/leq poly(n)/q/)，将所有的/(w_i/)按列组成一个/(n*n^2/)的矩阵/(W/)，满足/(s.W=kq+s*+e/)，其中/(k/)是一个整数向量，/(||e_i||_{/infty}/leq poly(n)/q/)。
（2）然后将高维密文转换为低维密文
给出一个/(n^2/)维密文向量/(c^*/)满足：/(<s^*,c^*>=k’q+b(q/2)+e’/)，其中/(k’/)是小整数，/(e’ <<q ,b/in Z_2/)。定义/(c=/left /lceil Wc^* /right /rfloor_q=Wc^* +e^* +k^*q/)，其中/(e^*/)是舍入误差，/(k^*/)是整数，则：
其中的/(/widetilde{e}/)是有界限的：
即/(|/widetilde{e}|<<q/)，那么对于/(/widetilde{k}/)，有：
总的来说，对于维数为/(n/)的新密文/(c/)，满足/(<s,c>=/widetilde{k}q+b(q/2)+/widetilde{e}/)，其中/(/widetilde{k},/widetilde{e}<<q/)，所以能够将一个高维/(n^2/)密文/(c^*/)，转换为低维/(n/)的密文/(c/)，且对应的明文都是/(b/)，即新密文/(c/)是有效的加密，其中密钥是/(s/)。
“打包”明文的计算
介绍
从上面可以看出，1bit的明文加密后的密文是/(n’+1/)维，在【PVW08】中给出了一种“打包”明文的方法，提升计算效率，简单点说就是，/(m’/)bit的明文加密后的密文是/(m=n’+m’/)维
这里选取/(m’/)个向量（/(m’/)个大小为/(n’/)的向量），即/(s_i/in /chi^{n’}/)，将其组成一个/(m’.n’/)的矩阵/(S’/)（按行），之前使用的是/(n’+1/)维的密钥向量/(s=(1|s’)/)，现在使用的是/(m’.m/)的密钥矩阵/(S=(I|S’)/)，其中，/(I/)是i个/(m’.m’/)的单位矩阵。
上面是密钥生成，下面开始加解密：
（1）加密
对于明文/(b/in Z_2^{m’}/)，即明文是一个比特串（向量），随机取向量/(z/in Z_q^{n’}/)，误差向量/(x/in /chi ^m/)，计算/(d=[b.q/2-S’a+x]_q/)，输出密文向量/(c=(d|a)/in Z_q^m/)。
（2）解密
计算/(Sc=d+S’a=b.q/2+x(mod q)/)，对于计算结果（向量），观察其中每个元素，若元素大于/(q/4/)，则为1，否则为0。其中/(x/)中的每个元素远小于/(q/)，解密也可以表示为/(b=/left /lceil [Sc]_q/(q/2) /right /rfloor_2/)。
总的来说，对于密文/(c/)，对应密钥为/(S/)，有效的解密为:
其中/(/left/|k /right/|_{/infty },/left/|x /right/|_{/infty }<<q/)。
（3）同态计算
从加解密来看，对于两个密文/(c_1,c_2/in Z_q^m/)，分别对应明文是/(b_1,b_2/in Z_2^{m’}/)，密钥为/(S/in Z_q^{m’.m}/)。
密文相加/(c’=[c_1+c_2]_q/)，分别对应于明文/((b_1/bigoplus b_2)/)。
密文相乘/(c”=[2/q.c_1 /bigotimes c_2]_q/)，分别对应明文/(b_1/bigodot b_2/in Z_2^{m’}/)（bitwise product，按位乘）。
密钥交换
密钥交换是需要“计算密钥”（public key key-switching gadgets）的，利用计算密钥使得/(s_i^*->s_i/)，但是这样对于每一个密文转换/((c”->c)/)，都需要一个计算密钥，我们想要的是使用一个计算密钥，将高维密文/(c”/)（对应的密钥为/(s^*/)），转换为一个低维密文/(c/)（对应密钥为/(s/)）。
计算密钥能得到密钥交换矩阵/(W/)
密钥交换的“计算密钥”可以看作是用密钥/(s/)加密/(s^*/)构成的。具体来看，就是把/(s_i/)作为密钥，加密所有的/(s_i^*/)。
这里的密钥交换矩阵/(W/)，满足/(SW=S*+E(mod q)/)，其中/(E/)是误差矩阵。具体说，/(m=n’+m’/)，可以利用/(W/in Q^{m.m^2}/)，将/(S^*/in Z^{m’.m^2}/)对应的密文转换为/(S=(I|S’)/in Z^{m’.m}/)对应的密文，那/(W/)如何求呢？
上面比较重要的内容是：想要安全性高，那就要提升模数/(n’/)的大小。
对于/(j/in (1,2,…,m^2)/)，/(/widetilde{s}_j /in Z^{m’}/)组成矩阵/(S^*/)（按列），/(a_i/in Z_Q^{n’}/)组成矩阵/(W/)（按行），/(e_j/in Z^{m’}/)是误差向量，计算/(d_j=[2^l./widetilde{s}_j-S’a_j+e_j]_Q/)，输出/(w_j=(d_j|a_j)^T/2^l/in Q^m/)，按行组成/(W/)。
/(d_j/)也可以表示为/(d_j=2^l./widetilde{s}_j-S’a_j+e_j+kQ/)，则满足：
也即是：
其中整数矩阵/(K/)和误差矩阵/(E/)满足/(/left/|E /right/|_{/infty }/leq poly(n)/q/)
总结
给出一个高维密文/(c^*/)，对应密钥为/(S*/)，利用密钥交换矩阵/(W/)，可得低维新密文/(c=/left /lceil Wc^* /right /rfloor_q/)，对应密钥为/(S/)，且解密后的明文是一样的。
若对于/(S^*.c^*=k^*.q+b(q/2)+e^*/)和/(S.c=k.q+b(q/2)+e/)，需要满足/(k^*,e^*,k,e<<q/)。
在一个Leveled-FHE方案中，需要提前生成多个互相独立的密钥矩阵/(S_k/)，使得在每次乘法后执行密钥交换，转换为新的密钥，所以在该方案中，乘法的次数就受限于密钥的个数。
安全性是基于LWE问题。上面的引理是在/(S^*/)和/(S/)是独立关系的前提下，假如/(S^*/)和/(S/)不是独立的，那这就依赖于“循环安全假设”（circular security）了。
密文置换
使用以上技术，可以实现“压缩”版的SIMD同态计算，就是每计算一次相当于计算多次！
在密文计算量更大的需求下，“压缩”实为是一种好的实现，对于密文置换，可以利用密钥交换实现。
介绍
什么是密文置换？
规定一种置换映射/(/pi()/)：
对于一个密文/(c/)，对应密钥为/(S/)，解密后的密文为/(b/in Z_2^{m’}/)，将其作用在/(/pi()/)上，得到/(c’=/pi(c)/)。用/(S/)去解密/(c’/)，会得到/(/pi(b)/)。
使用密钥交换实现很简单：准备一个密钥交换矩阵/(W/)，可以得到将/((/pi(S)->S)/)
对于/(/pi(c)/)，对应密钥为/(/pi(S)/)，解密明文为/(/pi(b)/)，使用密钥交换，将其转换为一个新的密文/(c’/)，对应的密钥为/(S/)，解密明文为/(/pi(b)/)。
总结
本文基于LWE问题，设计了一种PVW变体的压缩明文方案，这就类似于SV压缩方案，在环上的便利。
基于整数环和多项式环上的对比
（1）基于多项上环比实数环的方案具有更好的渐进效率（asymptotic efficiency）
（2）两种情况下密文的大小大致相同：多项式环上的密文是一个多项式，其中包含/(O(n)/)个整数。
（3）对于密文乘法（tensor product multiplication），基于整数的密文大小扩大为/(O(n^2)/)倍，基于多项式的密文大小仍是/(O(n)/)。
（4）对于重线性化，基于整数的密钥交换矩阵为/(O(n^3)/)，基于多项式的密钥交换矩阵为/(O(n)/)，基于整数上的计算会产生更多开销。
（5）对于密文中的“slot”个数，基于多项式的是由底层环结构决定的，基于整数的slot个数可以任意设置。
（6）在密文置换上，基于整数的比基于多项式更优。
（7）对于密钥交换，基于整数的比基于多项式的更方便和高效。
参考
1、【论文阅读笔记】-针对RSA的短解密指数的密码学分析(Cryptanalysis of Short RSA Secret Exponents)
2、范数||x||（norm）笔记
