本节内容记录阅读该论文的笔记
首先，介绍了两种明文“打包”的方法：PVW和SV
PVW：对应论文(PVW:A framework for efficient and composable oblivious transfer)，打包思想就是，将多个bit明文是为一个明文向量。
SV：对应论文（SV11:Fully homomorphic SIMD operations），打包思想：将多个明文通过“编码”插入到一个多项式上，转换成多项式的计算相当于这么多明文计算。多用于基于RLWE方案的。
原paper：On lattices, learning with errors, random linear codes, and cryptography
加密单比特数据：系统参数(qin Z)，明文比特(bin (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_1bigotimes c_2))，并满足(<s_1,c_2>.<s_2,c_2>=<s_1bigotimes s_2,c_1bigotimes c_2>)
张量积：参考（点积、张量积和范数）
下面就是如何构造乘法后的正确解密：
(c^*=left lceil 2/q.(c_1bigotimes c_2)right rfloor)
则：(z^*=<sbigotimes s.c^*>=k^*.q+b_1b_2.q/2+e^*(mod q))，其中(k^*,e^*)也是相对较小的，所以参数选取适当的情况下，乘法后能正常解密！
可以看出，如果(c_1,c_2)是一个(n)维的向量的话，则(c_1bigotimes c_2)是一个(n^2)维的矩阵，若在此基础上再进行一次乘法，则新密文的维数为(n^4)，可见存在一个问题：密文维数随着乘法次数而变大（指数级）。
所以需要一种方法去“降维”，即（BV11a）中给出的重线性化技术（re-linearization）将密文维数(n^2)将为(n)。
重线性化，实质上就是密钥交换技术（Key Switching），即给出两个密钥(s,s')，使用密钥交换技术将密钥(s')对应的密文转换为(s)对应的密文。密钥交换矩阵实际上包含用(s')加密的(s)，这是一个矩阵（密钥交换矩阵），其实也是将(sbigotimes 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_ibigotimes s_i)，现在如何进行重线性化呢？
选择一个合适的密钥交换矩阵（用(s_i)加密的(s_ibigotimes 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)
安全参数(n)，模数(q>poly(n))，(chi)表示均值为0，标准差为(q/ beta)的离散高斯分布，(beta =poly(n))
问：poly()表示什么意思？
关于LWE问题的困难性，在[Regev09]中给出了证明，表明能将LWE问题通过量子规约（quantum reductions）到(n)维格上的困难问题；在[Pei09]中给出了经典规约的方法（classical reductions）
即搜索版本的LWE（search-LWE）：
对于((a_iin Z_q^n,b_i=[<s,a_i>+e_i]_q))，(e_iin beta) ，给出(a_i,b_i)，难以计算出(s)
即判绝版本的LWE（decision-LWE）：
给出(<a_i'in Z_q^n,b_i'in Z_q^n>)和((a_iin Z_q^n,b_i=[<s,a_i>+e_i]_q))是难以区分的
一个基于LWE问题的公钥加密方案，这里给出了一个对称加密方案，可以通过范型变换（generic transformations）获得一个公钥加密方案。
范型变换？
明文空间(Z_2=(0,1))，模数(q)，安全参数(n'),(n=n'+1)
这里介绍对称加密方案
密钥(s'in chi ^{n'})，明文(sigmain Z_2)，选取(ain Z_q^{n'}),(ein 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_2in 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_1bigoplus b_2)q/2+e_i')，其中(k'=k_1+k_2) 或 (k_1+k_2pm 1<<q)和(e'=e_1+e_2 <<q)。（这里的加法是异或）
所以(c')是(b_1+b_2)的有效加密。
（2）乘法
在【BV11】和【Bra12】中给出了Regev的乘法同态。
对于(c^*=c_1bigotimes c_2)（(n^2)维向量），(s^*=sbigotimes 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^*=sbigotimes s)和(e)中元素很小，所以(<s^*,e>)也很小，且(|e^*|<<q)。
最后令(c''=left lceil 2/q.c^*right rfloor_q)，满足：
其中(e^*<<q)，(k^*)满足：
所以(c'')是(b_1b_2)的有效加密，密钥为(s^*=sbigotimes 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 ,bin 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_iin chi^{n'})，将其组成一个(m'.n')的矩阵(S')（按行），之前使用的是(n'+1)维的密钥向量(s=(1|s'))，现在使用的是(m'.m)的密钥矩阵(S=(I|S'))，其中，(I)是i个(m'.m')的单位矩阵。
上面是密钥生成，下面开始加解密：
（1）加密
对于明文(bin Z_2^{m'})，即明文是一个比特串（向量），随机取向量(zin Z_q^{n'})，误差向量(xin 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_2in Z_q^m)，分别对应明文是(b_1,b_2in Z_2^{m'})，密钥为(Sin Z_q^{m'.m})。
密文相加(c'=[c_1+c_2]_q)，分别对应于明文((b_1bigoplus b_2))。
密文相乘(c''=[2/q.c_1 bigotimes c_2]_q)，分别对应明文(b_1bigodot b_2in 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')，可以利用(Win Q^{m.m^2})，将(S^*in Z^{m'.m^2})对应的密文转换为(S=(I|S')in Z^{m'.m})对应的密文，那(W)如何求呢？
上面比较重要的内容是：想要安全性高，那就要提升模数(n')的大小。
对于(jin (1,2,...,m^2))，(widetilde{s}_j in Z^{m'})组成矩阵(S^*)（按列），(a_iin Z_Q^{n'})组成矩阵(W)（按行），(e_jin Z^{m'})是误差向量，计算(d_j=[2^l.widetilde{s}_j-S'a_j+e_j]_Q)，输出(w_j=(d_j|a_j)^T/2^lin 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)，解密后的密文为(bin 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）笔记
