介绍本节内容记录阅读该论文的笔记
首先，介绍了两种明文“打包”的方法：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\)
安全参数\(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\)
即判绝版本的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)\)是难以区分的
一个基于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）笔记