前言

借鉴致远的文章学习同态加密，本文主要记录密钥切换与模切换流程，参考文献为Zvika Brakerski 和Vinod Vaikuntanathan的《Efficient Fully Homomorphic Encryption from (Standard) LWE》，这篇文章的针对性问题如下：

😄	现有方法的问题	改进方法 / 文章贡献
1	现有的全同态加密算法复杂度被量子规约到 worst-case 理想格难题上，但是当时对理想格的研究较少，未经过充分验证	容错学习问题（Learning with error problem）：基于容错学习问题，算法复杂度可以标准规约到任意格的worst-case 难题上
2	现有的全同态加密算法在进行同态乘法时，密文维度从$n+1$扩展到将近 $n^2/2$。因此，随着乘法深度增加，计算开销上升。	重线性化（re-relinearization）：进行密钥切换，将平方级密钥维度收缩为线性大小
3	为将部分同态算法提升至全同态，现有方法基于稀疏子集和假设（sparse subset-sum assumption），引入压缩（Squashing step）技术	维度-模数约减（dimension-modulus reduction）：进行模数和密钥维度的切换，避免使用压缩技术，从而去除稀疏子集和这个强假设

半同态加密（Partially Homomorphic Encryption，PHE）：仅支持一种同态运算，但是支持无限次运算。
部分同态加密（Somewhat Homomorphic Encryption，SWHE）：支持多种同态运算，但是运算次数有限。
全同态加密（Fully Homomorphic Encryption，FHE）：支持无限次多种同态运算。

---

---

一、预备知识

1. 基础定义

知识点	个人理解	形式化定义
B-bound distribution	分布多数样本的范数小于$B$。换句话说，样本落在以原点为圆心，$B$为半径的圆外的概率很小。
Matrix-vector leftover hash lemma	剩余哈希引理揭示了LWE样本接近均匀分布。
Correctness	对称加密算法是正确的，意味着对于任何明文和密钥，解密失败的概率非常小。
IND-CPA secure	攻击者无法在有限时间内区分真实明文对应的密文和比特0对应的密文
$\mathcal{C}$-Homomorphism	同态性是指，对于函数集合中某类函数的实例，解密同态计算后的密文 = 明文运算结果
Compactness	紧凑性要求，无论有几个输入，同态计算的密文输出长度最多为多项式级别的。
Bootstrappable encryption scheme	同时包含异或运算和与运算的同态方案。这是因为XOR和AND可以组合出任意布尔电路，包括解密电路。
Weak circular security	弱循环安全是指，攻击者拥有按比特加密的私钥，但公钥加密算法仍是IND-CPA安全的。

2. IND-CPA secure

IND-CPA安全是指攻击者即使能够自由加密任何他选中的明文，也无法区分两个特定明文的加密结果。下面介绍同态加密方案的CPA安全性：

知识点	个人理解	形式化定义
CPA security	攻击者已知公钥、同态计算的评估密钥、密文，但在多项式时间内无法区分同一明文对应的两条不同密文。同一密文可以加密成两条不同的密文，这是因为同态加密算法是一种随机算法
$(t,ϵ)$-CPA security	攻击者已知公钥$pk$、同态计算的评估密钥$evk$、密文，但在时间$t$（超多项式级别）内区分同一明文对应的两条不同密文的概率很小，小于次多项式级别。

在证明CPA安全时，需要通过一个挑战者（Challenger）和攻击者（Adversary）之间的安全游戏来定义：

• 初始化：挑战者运行密钥生成算法 $KeyGen(1^{\kappa })$，产生一对公钥 $pk$ 和私钥$sk$。挑战者将公钥 $pk$ 发送给攻击者。私钥 $sk$ 被安全保存。
• 查询阶段 1：攻击者可以自适应地选择任意明文 $m$，并发送给挑战者。挑战者返回对应的密文 $Enc(pk,m)$。攻击者可以根据之前收到的密文，不断调整并选择新的明文进行查询。这个阶段可以重复多项式次。
• 挑战阶段：攻击者选择两个等长的明文 $m_0$ 和 $m_1$，并发送给挑战者。挑战者随机地抛一枚硬币，选择一个比特 b ∈ { 0 , 1 } b ∈ \{0, 1\} b∈{0,1}。挑战者计算挑战密文 $c^{\ast }=Enc(pk,m_b)$，并将 $c^{\ast }$ 发送给攻击者。
• 查询阶段 2：攻击者可以像阶段1一样继续请求加密其他明文，但不能请求解密挑战密文 $c^{\ast }$。
• 猜测阶段：攻击者输出一个猜测比特 $b^{\prime }$。攻击者的优势是指以超过$50\%$的概率猜对的可能性，定义为：$$Ad{v}_{CPA}[\mathcal{A}]=|Pr[b^{\prime }=b]-1/2|$$
• 定义：如果对于所有多项式时间的攻击者 $\mathcal{A}$，其优势 $Ad{v}_{CPA}[\mathcal{A}]$ 都是可忽略的，那么这个加密方案就是 IND-CPA 安全的。

3. 全同态加密方案的扩展

Gentry提出了自举（Bootstrapping）技术，有研究者在此基础上得出以下结论：

• 理论3.1：利用基于自举的同态加密方案，可以构造层次全同态加密方案。
• 理论3.2：利用一个满足弱循环安全的基于自举的同态加密方案，可以构造全同态加密方案。
• 引理3.3：若一个（层次）全同态加密方案是由自举技术构造的，那么同态计算后的密文长度与新密文一样长。

---

二、核心算法

本文的同态计算函数由伽罗瓦域$GF(2)$上的电路表示。下面介绍BV11的核心算法：

1. 密钥切换：Re-linearization

重线性化是为了解决同态乘法中密文维度指数级增长的问题，主要新增了重线性化密钥，并改动了同态乘法的计算方法。

• 参数设置

参数	解释
$\kappa$	安全参数
$n=poly(\kappa )$	密文维度
$m=poly(n)\ge n\log q+2\kappa$	LWE样本个数
$q\in [2^{n^{ϵ}},2\cdot 2^{n^{ϵ}})$	模数，取奇数，其中$ϵ\in (0,1)$，保证$q$是$n$次指数级别
$L\approx ϵ\log n$	乘法深度，即允许计算的乘法次数
$\chi$	噪声分布，取小噪声，噪声范数最多为$n$

• 生成密钥

参数	解释
$s_0,\cdots ,s_L$	私钥链：包括$L+1$个私钥，其中$s_i\leftarrow {\mathbb{Z}}_q^n$前$L$个私钥的第0位为1，即$s_{l-1}[0]=1$
$(A,b)$	公钥：首先均匀采样矩阵$A\in {\mathbb{Z}}_q^{m\times n}$和噪声$e\in {\chi }^m$，然后计算 $b=A{s}_0+2e$
Φ = { ϕ l , i , j , τ } \Phi=\{\phi_{l,i,j,\tau}\} Φ={ϕl,i,j,τ​}	重线性化密钥：用于加密同态乘法后的密文二次项 $2^{\tau }\cdot s_l[i]\cdot s_l[j]$。对于每一层$l\in [L]$，乘法索引对 $0\le i\le j\le n$，和每个比特位 τ ∈ { 1 , ⋯   , log ⁡ q ⌋ } \tau\in\{1,\cdots, \log q \rfloor\} τ∈{1,⋯,logq⌋}，从LWE分布中采样密钥$${\varphi }_{l,i,j,\tau }=(a_{l,i,j,\tau },b_{l,i,j,\tau })$$ 其中，向量$a_{l,i,j,\tau }\in {\mathbb{Z}}_q^n$和小噪声$e_{l,i,j,\tau }\in {\mathbb{Z}}_q^n$通过随机采样得到，则$$b_{l,i,j,\tau }=⟨a_{l,i,j,\tau },s_l⟩+2\cdot e_{l,i,j,\tau }+2^{\tau }\cdot s_{l-1}[i]\cdot s_{l-1}[j]\in {\mathbb{Z}}_q$$

• 加密
  给定明文$\mu \in GF(2)$，随机选取一个向量 r ∈ { 0 , 1 } m r\in \{0,1\}^m r∈{0,1}m，则密文为$c=((v,w),0)$。其中，0 表示初始化乘法深度，$v=A^{T}r$， $w=b^{T}r+\mu$
• 解密
  对于乘法深度为$l$的密文$c=((v,w),l)$，解密结果如下：$$(w-⟨v,s_l⟩\mathrm{mod}q)\mathrm{mod}2$$一般只解密同态计算后的结果，即对最后一层 $l=L$ 密文解密。
• 同态加法
  同态加法可以有多个输入$c_1,\cdots ,c_t$，但必须在同一层，其中$c_i=((v_i,w_i),l)$，则加法运算后的密文$c_{\mathrm{add}}=((v_{\mathrm{add}},w_{\mathrm{add}}),l)$有$$v_{\mathrm{add}}=\sum _i{v}_i$$$$w_{\mathrm{add}}=\sum _i{w}_i$$
• 同态乘法
  同态乘法只可以输入同一层的两个密文$c=((v,w),l)$ 和 $c^{\prime }=((v^{\prime },w^{\prime }),l)$。令$h_{i,j}$为函数$\varphi (s_l)$的系数，即：
  $$\begin{array}{rl}\varphi (s_l)& =(w-⟨v,s_l⟩)\cdot (w^{\prime }-⟨v^{\prime },s_l⟩)(\mathrm{mod}q)\\ & =\sum _{0\le i\le j\le n}{h}_{i,j}\cdot s_l[i]\cdot s_l[i]\end{array}$$具体而言有：
  $$h_{i,j}=\{\begin{array}{llc}w\cdot w^{\prime },& \text{if }& i=0,j=0\\ -w\cdot v^{\prime }[j]-w^{\prime }\cdot v[j],& \text{if }& i=0,j\ge 1\\ v^{\prime }[i]\cdot v[i],& \text{if}& i=j\ge 1\\ v[i]\cdot v^{\prime }[j]+v^{\prime }[i]\cdot v[j],& \text{if }& j>i\ge 1\end{array}$$将$h_{i,j}$转为二进制后有：$$h_{i,j}=\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,j,\tau }\cdot 2^{\tau }$$则乘法运算后的密文$c_{\mathrm{mult}}=((v_{\mathrm{mult}},w_{\mathrm{mult}}),l+1)$有$$v_{\mathrm{mult}}=\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot a_{l+1,i,j,\tau }\mathrm{mod}q$$$$w_{\mathrm{mult}}=\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot b_{l+1,i,j,\tau }\mathrm{mod}q$$其中，$0\le i\le j\le n$， τ ∈ { 0 , ⋯   , ⌊ log ⁡ q ⌋ } \tau\in \{0,\cdots,\lfloor \log q\rfloor\} τ∈{0,⋯,⌊logq⌋}。

2. 模切换、密钥维度切换：Dimension-modulus Reduction

维度-模数约减是在$L$层同态乘法结束后，为了减小自举（解密）的计算开销而设计的，在重线性化的基础上，将原本的密文维度$n$和模数$q$ 切换为更小的参数$(k,p)$，新增了约减密钥，并设计了在新参数下的同态计算。下面只介绍改进步骤，其余都与上文一致：

• 参数设置

参数	解释
$k=\kappa$	新的密文维度
$n={\kappa }^4$	旧的密文维度
$q\approx 2^{\sqrt{n}}$	旧的模数
$p=(n^2\log q)\cdot poly(k)=poly(k)$	旧的模数
$m=O(n\log q)$	LWE样本个数
$L=1/3\log n=4/3\log k$	乘法深度
$\chi$	旧的噪声分布，噪声范数最多为$n$
$\hat{\chi }$	新的噪声分布，噪声范数最多为$k$

• 生成密钥

参数	解释
$s_L\in {\mathbb{Z}}_q^n$	旧的私钥，有$n$维
$\hat{s}\in {\mathbb{Z}}_p^k$	新的私钥，只有$k$维
$(A,b)$	公钥，$A\in {\mathbb{Z}}_q^{m\times n}$，$e\in {\chi }^m$，$b\in {\mathbb{Z}}_q$
Φ = { ϕ l , i , j , τ } \Phi=\{\phi_{l,i,j,\tau}\} Φ={ϕl,i,j,τ​}	重线性化密钥，$l\in [L]$， $0\le i\le j\le n$， τ ∈ { 1 , ⋯   , log ⁡ q ⌋ } \tau\in\{1,\cdots, \log q \rfloor\} τ∈{1,⋯,logq⌋}
Φ ^ = { ϕ ^ i , τ } \hat \Phi=\{\hat \phi_{i,\tau}\} Φ^={ϕ^​i,τ​}	约减密钥。对于$i\in [n]$，和每个比特位 τ ∈ { 1 , ⋯   , log ⁡ q ⌋ } \tau\in\{1,\cdots, \log q \rfloor\} τ∈{1,⋯,logq⌋}，从LWE分布中采样密钥$${\varphi }_{i,\tau }=({\hat{a}}_{i,\tau },{\hat{b}}_{i,\tau })$$ 其中，向量${\hat{a}}_{i,\tau }\in {\mathbb{Z}}_p^k$和小噪声${\hat{e}}_{i,\tau }\in \hat{\chi }$通过随机采样得到，则$${\hat{b}}_{i,\tau }=⟨{\hat{a}}_{i,\tau },\hat{s}⟩+{\hat{e}}_{i,\tau }+\lfloor \frac{p}{q}\cdot (2^{\tau }\cdot s_L[i])\rceil \mathrm{mod}p$$

• 自举（解密）
  对于$L$层同态乘法后的密文$c_f=((v,w),L)$。令${\hat{h}}_i$为函数$\hat{\varphi }(s_L)$的系数，即：
  $$\begin{array}{rl}\hat{\varphi }(s_L)& =\frac{p}{q}\cdot (\frac{q+1}{2}\cdot (w-⟨v,s_L⟩))(\mathrm{mod}p)\\ & =\sum _{i\in [n]}{h}_i\cdot (\frac{p}{q}\cdot s_L[i])\end{array}$$具体而言有：
  $${\hat{h}}_i=\{\begin{array}{llc}\frac{q+1}{2}\cdot w,& \text{if }& i=0\\ -\frac{q+1}{2}\cdot v[i],& \text{if }& i\ge 1\end{array}$$将${\hat{h}}_i$转为二进制后有：$${\hat{h}}_i=\sum _{\tau =0}^{\lfloor \log q\rfloor }{\hat{h}}_{i,\tau }\cdot 2^{\tau }$$则自举后的密文$\hat{c}=((\hat{v},\hat{w}),0)$有$$\hat{v}=2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{a}}_{i,\tau }\mathrm{mod}p$$$$\hat{w}=2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{b}}_{i,\tau }\mathrm{mod}p$$其中，$i\in [n]$， τ ∈ { 0 , ⋯   , ⌊ log ⁡ q ⌋ } \tau\in \{0,\cdots,\lfloor \log q\rfloor\} τ∈{0,⋯,⌊logq⌋}。

---

三、算法分析

1. 正确性

1.1 Re-linearization 的正确性

• 解密的正确性
  $$\begin{array}{rl}w-⟨v,s_l⟩& =(b^{T}r+\mu )-⟨A^{T}r,s_l⟩\\ & =b^{T}r+\mu -⟨r,A\cdot s_l⟩\\ & =b^{T}r+\mu -r^T\cdot A\cdot s_l\\ & =\mu +r^T\cdot (b-A{s}_l)\\ & =\mu +r^T\cdot 2e_{total}\end{array}$$在模$q$和模$2$后为$\mu$。
• 同态加法的正确性
  $$\begin{array}{rl}{w}_{\mathrm{add}}-⟨v_{\mathrm{add}},s_l⟩& =\sum _i{w}_i-⟨\sum _i{v}_i,s_l⟩\\ & =\sum _i(w_i-⟨v_i,s_l⟩)\\ & =\sum _i({\mu }_i+r_i^T\cdot 2e_i^{total})\\ & =\sum _i{\mu }_i+2\cdot \sum _i{r}_i^T\cdot e_i^{total}\end{array}$$在模$q$和模$2$后为${\sum }_i{\mu }_i$。
• 同态乘法的正确性
  $$\begin{array}{rl}{w}_{\mathrm{mult}}-⟨v_{\mathrm{mult}},s_{l+1}⟩& =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot b_{l+1,i,j,\tau }-⟨\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot a_{l+1,i,j,\tau },s_{l+1}⟩\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot (b_{l+1,i,j,\tau }-⟨a_{l+1,i,j,\tau },s_{l+1}⟩)\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot (2\cdot e_{l+1,i,j,\tau }+2^{\tau }\cdot s_l[i]\cdot s_l[j])\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot 2\cdot e_{l+1,i,j,\tau }+\sum _{i,j,\tau }(h_{i,j,\tau }\cdot 2^{\tau })\cdot s_l[i]\cdot s_l[j]\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot 2\cdot e_{l+1,i,j}+\sum _{i,j}{h}_{i,j}\cdot s_l[i]\cdot s_l[j]\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot 2\cdot e_{l+1,i,j}+\varphi (s_l)\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot 2\cdot e_{l+1,i,j}+(w-⟨v,s_l⟩)\cdot (w^{\prime }-⟨v^{\prime },s_l⟩)\\ & =\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot 2\cdot e_{l+1,i,j}+(\mu +r^T\cdot 2e_{total})\cdot [{\mu }^{\prime }+(r^{\prime }{)}^T\cdot 2e_{total}^{\prime }]\\ & =\mu {\mu }^{\prime }+2\cdot [\mu \cdot (r^{\prime }{)}^T\cdot e_{total}^{\prime }+{\mu }^{\prime }\cdot r^T\cdot e_{total}+2\cdot (r^{\prime }{)}^T\cdot e_{total}^{\prime }\cdot r^T\cdot e_{total}+\sum _{i,j,\tau }{h}_{i,j,\tau }\cdot e_{l+1,i,j}]\end{array}$$在模$q$和模$2$后为$\mu {\mu }^{\prime }$。

1.2 Dimension-modulus Reduction的正确性

$$\begin{array}{rlr}\hat{w}-⟨\hat{v},\hat{s}⟩& =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{b}}_{i,\tau }-⟨2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{a}}_{i,\tau },\hat{s}⟩(\mathrm{mod}p)& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot ({\hat{b}}_{i,\tau }-⟨{\hat{a}}_{i,\tau },\hat{s}⟩)& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot ({\hat{e}}_{i,\tau }+\lfloor \frac{p}{q}\cdot (2^{\tau }\cdot s_L[i])\rceil )& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+2\cdot \sum _i{\hat{h}}_i\cdot \lfloor \frac{p}{q}\cdot s_L[i]\rceil & \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+2\cdot \hat{\varphi }(s_L)& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+\frac{p\cdot (q+1)}{q}(w-⟨v,s_L⟩)& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+\frac{p\cdot (q+1)}{q}(2\cdot e_{total}+\mu +kq)& (\text{where }k\in \mathbb{Z})\\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+\frac{2p\cdot (q+1)}{q}\cdot e_{total}+\frac{p\cdot (q+1)}{q}\mu +kp\cdot (q+1)& \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+(2p\cdot e_{total}+\frac{2p}{q}\cdot e_{total})+(p+1+\frac{p}{q}-1)\cdot \mu & \\ & =2\cdot \sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+\frac{2p}{q}\cdot e_{total}+p\mu +\mu +(\frac{p}{q}-1)\cdot \mu & \\ & =\mu +2\cdot (\sum _{i,\tau }{\hat{h}}_{i,\tau }\cdot {\hat{e}}_{i,\tau }+\frac{p}{q}\cdot e_{total}+\frac{p-q}{2q}\cdot \mu )& \end{array}$$在模$p$和模$2$后为$\mu$。

2. 安全性

${\text{DLWE}}_{n,m,q,\chi }$：判断$m$个样本来自LWE分布还是均匀分布。
${\text{DLWE}}_{n,q,\chi }$：判断任意数量的样本来自LWE分布还是均匀分布。

如果 ${\text{DLWE}}_{n,m,q,\chi }$问题和${\text{DLWE}}_{n,q,\chi }$问题都是 $(t,ϵ)$-困难的，那么BV11方案是 $(t-\text{poly}(\kappa ),2(L+1)\cdot (2^{-\kappa }+ϵ))$-CPA安全的。原文的结论如下：

假定有一个IND-CPA攻击者$\mathcal{A}$。下面利用混合论证，证明该方案的安全性：

• 定义攻击者的优势
  首先，思考攻击者$\mathcal{A}$攻击成功的概率，即猜测值 $b^{\prime }$ 和真实值 $b$ 一样的概率，如下：
  $$\begin{array}{rl}P(b^{\prime }=b)& =P(b=0)\cdot P(b^{\prime }=0|b=0)+P(b=1)\cdot P(b^{\prime }=1|b=1)\\ & =\frac{1}{2}\cdot [1-P(b^{\prime }=1|b=0)]+\frac{1}{2}\cdot P(b^{\prime }=1|b=1)\\ & =\frac{1}{2}+\frac{1}{2}\cdot [P(b^{\prime }=1|b=0)-P(b^{\prime }=1|b=1)]\end{array}$$其中，$\mathcal{A}$在游戏$H$中获胜的优势${\text{Adv}}_H$被定义为概率公式里中括号那部分，即：
  $${\text{Adv}}_H[\mathcal{A}]=P(b^{\prime }=1|b=0)-P(b^{\prime }=1|b=1)$$此时，${\text{Adv}}_H$越大，攻击成功率越高，则优势越大。
• 定义攻击者的知识：攻击者有一个LWE Oracle，该Oracle可能生成LWE样本，也可能生成均匀样本；攻击者已知密文，以及加密所用的公钥、重线性化密钥、约减密钥。
• 定义混合游戏

混合 游戏	描述
${\hat{H}}_{L+1}$	攻击者$\mathcal{A}$根据真实密文和密钥（公钥、重线性化密钥、约减密钥）所生成的密文猜测真实明文
$H_{L+1}$	攻击者$\hat{\mathcal{B}}$仅将约减密钥替换为随机数。具体而言，攻击者$\hat{\mathcal{B}}$向LWE Oracle申请一个样本，并用该样本替换约减密钥。然后，攻击者$\hat{\mathcal{B}}$用替换后的密钥加密一个随机比特，并交给攻击者$\mathcal{A}$猜测。如果猜对了，攻击者$\hat{\mathcal{B}}$认为密文来自LWE分布，否则为均匀样本。
$H_{l\in [L]}$	攻击者${\hat{\mathcal{B}}}_l$将约减密钥、前第$l$层所有重线性化密钥 { ϕ λ , i , j , τ } λ ≤ l , i , j , τ \{\phi_{\lambda,i,j,\tau}\}_{\lambda\leq l,i,j,\tau} {ϕλ,i,j,τ​}λ≤l,i,j,τ​替换为随机数。攻击者${\hat{\mathcal{B}}}_l$向LWE Oracle申请一个样本，并用该样本替换重线性化密钥链中第$l+1$层密钥。攻击者${\hat{\mathcal{B}}}_l$用替换后的密钥加密一个随机比特，并交给攻击者$\mathcal{A}$猜测。如果猜对了，攻击者${\hat{\mathcal{B}}}_l$认为密文来自LWE分布，否则为均匀样本。
$H_0$	攻击者将约减密钥、所有重线性化密钥、公钥替换为随机数，并根据替换后的密钥生成的密文猜测真实明文
$H_{\text{rand}}$	攻击者将约减密钥、所有重线性化密钥、公钥、密文替换为随机数，并猜测真实明文

• 计算每个游戏下的优势
  对于游戏${\hat{H}}_{L+1}$：根据优势的定义，我们假设${\text{Adv}}_{{\hat{H}}_{L+1}}[\mathcal{A}]=\delta$。
  对于游戏$H_l$：如果Oracle生成均匀样本，$H_l$ 分布与 $H_{l+1}$ 相同，此时攻击成功的概率为
  $$\begin{array}{rl}P(H_l\in A_{s,\chi }|H_l\in U)& =\frac{1}{2}+\frac{1}{2}\cdot [P_{l+1}(b^{\prime }=1|b=0)-P_{l+1}(b^{\prime }=1|b=1)]\\ & =\frac{1}{2}+\frac{1}{2}\cdot {\text{Adv}}_{H_{l+1}}[\mathcal{A}]\end{array}$$如果生成LWE样本，分布仍为$H_l$，此时攻击成功的概率为
  $$\begin{array}{rl}P(H_l\in A_{s,\chi }|H_l\in A_{s,\chi })& =\frac{1}{2}+\frac{1}{2}\cdot [P_l(b^{\prime }=1|b=0)-P_l(b^{\prime }=1|b=1)]\\ & =\frac{1}{2}+\frac{1}{2}\cdot {\text{Adv}}_{H_l}[\mathcal{A}]\end{array}$$ 此时该游戏的区分优势为
  $$\begin{array}{rl}\text{DLWE Adv}[\hat{\mathcal{B}}]& =|P(H_l\in A_{s,\chi }|H_l\in U)-P(H_l\in A_{s,\chi }|H_l\in A_{s,\chi })|\\ & =\frac{1}{2}\cdot |{\text{Adv}}_{H_l}[\mathcal{A}]-{\text{Adv}}_{H_{l+1}}[\mathcal{A}]|\end{array}$$
  对于游戏$H_{\text{rand}}$：所有元素都是均匀随机，与消息无关，因此优势为0。

先解释一下文章中在定义不同混合游戏的优势时，所用到的符号表示：$\mu$表示真实明文；${\text{SH.Enc}}_{pk}(\mu )$ 是按规矩一步一步生成的真实密文；$\mathcal{A}(\cdot )$表示攻击者$\mathcal{A}$在已知一定知识的情况下猜测对应明文，攻击知识即输入$(\cdot )$，例如$\mathcal{A}(pk,{\text{SH.Enc}}_{pk}(\mu ))$表示攻击者$\mathcal{A}$在已知公钥和真实密文的情况下猜测对应明文。

混合游戏	优势
${\hat{H}}_{L+1}$	$$\mathrm{Pr}[\mathcal{A}(pk,{\text{SH.Enc}}_{pk}({\mu }_0))=1]-\mathrm{Pr}[\mathcal{A}(pk,{\text{SH.Enc}}_{pk}({\mu }_1))=1]|=\delta$$
$H_{L+1}$	$${\text{DLWE}}_{k,p,\hat{\chi }}\text{Adv}[\hat{\mathcal{B}}]\ge \frac{1}{2}\cdot |{\text{Adv}}_{{\hat{H}}_{l+1}}[\mathcal{A}]-{\text{Adv}}_{H_{l+1}}[\mathcal{A}]|$$
$H_{l\in [L]}$	$${\text{DLWE}}_{n,q,\chi }\text{Adv}[{\hat{\mathcal{B}}}_l]=\frac{1}{2}\cdot |{\text{Adv}}_{H_l}[A]-{\text{Adv}}_{H_{l+1}}[A]|$$
$H_0$	$${\text{DLWE}}_{n,q,\chi }\text{Adv}[{\hat{\mathcal{B}}}_l]=\frac{1}{2}\cdot |{\text{Adv}}_{H_1}[A]-{\text{Adv}}_{H_0}[A]|$$
$H_{\text{rand}}$	$${\text{Adv}}_{H_{\text{rand}}}[\mathcal{A}]=0$$

• 计算总优势
  根据 Leftover hash lemma，样本与均匀随机统计接近：
  $$|{\text{Adv}}_{H_0}[\mathcal{A}]-{\text{Adv}}_{H_{\text{rand}}}[\mathcal{A}]|\le 2^{-\kappa }$$
  则将所有游戏中的优势关系相加有：
  $$\begin{array}{rl}{\text{Adv}}_{\text{CPA}}[\mathcal{A}]& ={\text{Adv}}_{{\hat{H}}_{L+1}}[\mathcal{A}]-{\text{Adv}}_{H_{\text{rand}}}[\mathcal{A}]\\ & \le 2^{-\kappa }+2\cdot ({\text{DLWE}}_{k,p,\hat{\chi }}\text{Adv}[\hat{\mathcal{B}}]+\sum _{l\in [L]}{\text{DLWE}}_{n,q,\chi }\text{Adv}[{\hat{\mathcal{B}}}_l])\end{array}$$

3. 同态性

😛这章部分证明看懂了，但懒得打字了，要是以后用到了再填坑

4. 全同态性

😐这章部分证明还有没打通的地方，就不详解了
通过Gentry的自举定理，BV11可以转为全同态方案。文章中首先证明了BV11的解密电路足够浅，可以由深度为$O(\log k+\log \log p)$的算术电路实现；其次证明了方案可自举，即存在常数 $C$，当设置 $n=k^{C/ϵ}$ 时，BV11可以同态计算自己的增强解密电路；最后，利用Gentry自举定理，可以获得层次全同态加密，若方案满足弱循环安全性，则获得真正的完全同态加密。