前言

借鉴致远的文章学习同态加密，本文主要记录同态加密中Flatten操作，参考文献为 Craig Gentry，Amit Sahai，Brent Waters 的《Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based》。这篇文章主要实现了理论上的创新，在实际应用中仍存在效率瓶颈。下面介绍全同态加密的历史发展流程以及本文的针对性问题：

😄	针对性问题	方法设计
现有方法	同态乘法中的张量积运算使得密钥维度指数级增长	BV11：利用重线性化操作，将同态乘法后的长密钥切换为短密钥
本文方法	BV11 使用重线性化矩阵更新密文的时候，带来了 $\Omega (n^3)$ 级别的计算开销	GSW：将密文表示为矩阵，矩阵与矩阵的乘积不会导致密文维度的增长，所以不需要使用密钥交换来约减密文的维数，进而可用于构建基于身份或属性的加密方案。

基于身份的加密（Identity-based encryption，IBE）：用户用其身份（如邮箱地址）作为公钥，而无需获取具体的公钥进行加密。
基于属性的加密（Attribute-based encryption，ABE）：解密能力由属性决定，只有满足特定策略的用户才能解密。

---

---

一、预备知识

流程	IBFHE方案	ABFHE方案
参数设置	生成“主”（master）公私钥。	生成主公私钥。
密钥生成	根据主私钥和用户身份 $ID$ ，生成该用户的解密私钥 $s{k}_{ID}$ 。	根据主私钥和一个属性（或策略）$y$，生成私钥 $s{k}_y$。
加密算法	使用主公钥和身份 $ID$，加密消息 $m$，得到密文 $c$。	使用主公钥和一个索引 $x$，加密消息 $m$。
解密算法	使用用户私钥 $s{k}_{ID}$ 解密针对其身份 $ID$ 的密文 $c$。	如果属性 $y$ 满足与索引 $x$ 的关系 $R(x,y)=1$，那么可以使用私钥 $s{k}_y$ 解密密文。
同态计算	输入主公钥、一个身份 $ID$、一个函数 $f$，以及一系列在同一身份 $ID$ 下加密的密文。输出一个新的密文 $c^{\prime }$，该密文仍然是在同一身份 $ID$ 下对 $f$ （明文）的加密。特别的，评估算法不应该要求除了主公钥和身份 $ID$ 之外的任何其他用户特定信息，例如评估密钥。	输入主公钥、一个公共索引 $x$、一个函数 $f$，以及一系列在同一索引 $x$ 下加密的密文。输出一个新的密文 $c^{\prime }$，该密文仍然在同一索引 $x$ 下加密了 $f$ （明文）。特别的，如果某个用户拥有私钥 $s{k}_y$，并且 $R(x,y)=1$（即他有权解密原始密文），那么同样能够解密同态计算后产生的新密文 $c^{\prime }$，并得到正确的结果 $f$ （明文）。此外，Eval不应需要任何评估密钥。

---

二、核心思想

1. 现有方案

下面简单描述现有方案（非正式的）：

流程	细节
参数设置	$q$ ：模数 $N$ ：密文维度
密钥生成	$\vec{v}\in {\mathbb{Z}}_q^N$ ：私钥，至少有一个分量很大
加密算法	明文 $\mu$ 被加密为密文 $C\in {\mathbb{Z}}_q^{N\times N}$ ，且满足 $$C\cdot \vec{v}=\mu \cdot \vec{v}+\vec{e}$$ 其中， $\vec{e}\in {\mathbb{Z}}_q^N$ 为小噪声，密文 $C$ 中每个分量都小于 $q$ 。
解密算法	首先选择 $C$ 的任意一行 $C_i$ ，计算 $x=⟨C_i,\vec{v}⟩=\mu \cdot v_i+e_i$ ，则解密结果为 $\mu =\lfloor x/v_i\rceil$
同态加法	对于密文 $C_1$ 和 $C_2$ 有 $C^{+}=C_1+C_2$ ，其中加法密文满足 $$C^{+}\cdot \vec{v}=({\mu }_1+{\mu }_2)\cdot \vec{v}+({\vec{e}}_1+{\vec{e}}_2)$$
同态乘法	对于密文 $C_1$ 和 $C_2$ 有 $C^{\times }=C_1\cdot C_2$ ，其中加法密文满足 $$\begin{array}{rl}{C}^{\times }\cdot \vec{v}& =(C_1\cdot C_2)\cdot \vec{v}\\ & =C_1\cdot ({\mu }_2\cdot \vec{v}+{\vec{e}}_2)\\ & ={\mu }_2\cdot (C_1\cdot \vec{v})+C_1\cdot {\vec{e}}_2\\ & ={\mu }_2\cdot ({\mu }_1\cdot \vec{v}+{\vec{e}}_1)+C_1\cdot {\vec{e}}_2\\ & =({\mu }_2\cdot {\mu }_1)\cdot \vec{v}+({\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2)\end{array}$$ 即 $C^{\times }\cdot \vec{v}=({\mu }_2\cdot {\mu }_1)\cdot \vec{v}+({\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2)$ 。

2. 针对性问题

• 线性代数中的特征向量
  在线性代数中，对于一个方阵 $A$ ，若存在一个非零向量 $\vec{v}$ 和 一个标量 $\lambda$ ，满足
  $$A\cdot \vec{v}=\lambda \cdot \vec{v}$$ 则称 $\vec{v}$ 为矩阵 $A$ 的一个特征向量，$\vec{v}$ 为矩阵 $A$ 的一个特征值。
• 无噪声方案的特征向量
  类似的，如果基础方案中不添加噪声，即
  $$C\cdot \vec{v}=\mu \cdot \vec{v}$$则密钥 $\vec{v}$ 可以看作密文 $C$ 的特征向量，而明文 $\mu$ 为特征值。同态加法后，密文 $C^{+}$ 的特征向量为密钥 $\vec{v}$ ，特征值为明文 ${\mu }_1+{\mu }_2$ ；同态乘法后，密文 $C^{\times }$ 的特征向量为密钥 $\vec{v}$ ，特征值为明文 ${\mu }_1\cdot {\mu }_2$ 。
• 有噪声方案的特征向量
  然而，为了安全性，基础方案中添加了噪声，此时
  $$C\cdot \vec{v}=\mu \cdot \vec{v}+\vec{e}$$ 即密钥 $\vec{v}$ 为密文 $C$ 的近似特征向量，并非准确的。这就导致同态计算中会引入额外的误差项，需要控制其大小。

3. 观察

密文有界：若密文 $C$ 是$B$-bound 的，则要求明文 $|\mu |\le B$，密文每一项 $|C_{i,j}|\le B$，并且噪声每一维 $|\vec{e}|\le B$。
密文强有界：若密文 $C$ 是$B$-strongly-bound 的，则要求明文 $|\mu |\le 1$（即 μ ∈ { 0 , 1 } \mu\in\{0,1\} μ∈{0,1}），密文每一项 $|C_{i,j}|\le 1$，并且噪声每一维 $|\vec{e}|\le B$。

当噪声项接近模数 $q$ 时，解密失败。下面我们计算在解密失败前可以计算的乘法次数：

• 多项式计算中的噪声增长
  假设噪声 $\vec{e}$ 和两个密文 $C_1$ 和 $C_2$ 都是 $B$-bound 的，则同态加法后的误差 ${\vec{e}}_1+{\vec{e}}_2\le 2B$ ，同态乘法后的误差 ${\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2\le (1+N)\cdot B^2$ 。因此，评估 $d$ 阶多项式后，密文的噪声量为 $O((NB{)}^d)$ 。为保证解密的正确性，要求 $(NB{)}^d<q$ ，即 $$d<{\log }_{NB}q$$同时，出于安全性要求，$q/B$ 必须关于 $N$ 的次指数级别，因此 $d$ 只可取对数或多项式级别，无法实现全同态。
• 与非门电路的噪声增长
  假设噪声 $\vec{e}$ 和两个密文 $C_1$ 和 $C_2$ 都是 $B$-strongly-bound 的，则经过与非门（NAND）后密文为 $C_3=I_N-C_1\cdot C_2$ ，其中 $I_N$ 为 $N$ 维全1向量。对 $C_3$ 解密有：
  $$\begin{array}{rl}{C}_3\cdot \vec{v}& =(I_N-C_1\cdot C_2)\cdot \vec{v}\\ & =\vec{v}-C_1\cdot C_2\cdot \vec{v}\\ & =\vec{v}-({\mu }_2\cdot {\mu }_1)\cdot \vec{v}-({\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2)\\ & =(1-{\mu }_2\cdot {\mu }_1)\cdot \vec{v}-({\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2)\end{array}$$ 此时噪声上界为 $|{\mu }_2\cdot {\vec{e}}_1+C_1\cdot {\vec{e}}_2|\le |{\mu }_2\cdot {\vec{e}}_1|+|C_1\cdot {\vec{e}}_2|\le (N+1)\cdot B$ 。若能保证密文 $C_3$ 是 $B$-strongly-bound 的，经过 $L$ 层运算后，噪声上界为 $O((N+1{)}^L\cdot B)$ 。为保证解密的正确性，要求 $(N+1{)}^L\cdot B<q$ ，即 $$L<\frac{\log q/B}{logN}$$同时，出于安全性要求，$q/B$ 必须关于 $N$ 的次指数级别，因此 $L$ 可取多项式级别。

综上，在与非门电路下，我们可以评估一个多项式深度 $L$ 的电路，而不仅仅是多项式阶数 $d$ 。

电路深度（depth）：从输入到输出的最长路径上，加法、乘法、置换等操作的总次数。
乘法阶数（degree）：从输入到输出的最长路径上，连续乘法操作的次数。

4. 核心设计：Flatten 操作

为了保证与非门的输出也是 $B$-strongly-bound 的，文章设计了 Flatten 操作。下面介绍 Flatten 操作所涉及的组件：

组件	细节
$\text{BitDecomp}$	对于 $k$ 维向量 $\vec{a}\in {\mathbb{Z}}_q^k$ ，将其解码为 $N=k\cdot l$ 维二进制向量 $\text{BitDecomp}(\vec{a})=(a_{1,0},\cdots ,a_{1,l-1},\cdots ,a_{k,0},\cdots ,a_{k,l-1})$，其中 $l=\lfloor {\log }_{2}q\rfloor +1$，$a_{i,j}$ 满足 $$a_i=\sum _{j=0}^{l-1}{2}^j\cdot a_{i,j}$$ 即拼接向量 $\vec{a}$ 中每一维 $a_i$ 的二进制编码。
${\text{BitDecomp}}^{-1}$	$\text{BitDecomp}$ 的逆运算，对于 $N$ 维向量 ${\vec{a}}^{\prime }\in {\mathbb{Z}}_q^N$ ，重新聚合为 $k$ 维向量 $${\text{BitDecomp}}^{-1}({\vec{a}}^{\prime })=(\sum _j{2}^j\cdot a_{1,j},\cdots ,\sum _j{2}^j\cdot a_{k,j})$$即以 ${\vec{a}}^{\prime }$ 中每 $l$ 维元素为一组，以2的幂次为权重聚合。值得注意的是，${\vec{a}}^{\prime }$ 中的元素不一定只是0和1，而是在模 $q$ 群下的。
$\text{Flatten}$	对于 $N$ 维向量 ${\vec{a}}^{\prime }\in {\mathbb{Z}}_q^N$ 有 $$\text{Flatten}({\vec{a}}^{\prime })=\text{BitDecomp}({\text{BitDecomp}}^{-1}({\vec{a}}^{\prime }))$$ 对于 $N\times N$ 维矩阵 $A\in {\mathbb{Z}}_q^{N\times N}$ 有 $$\text{Flatten}(A)=[\text{BitDecomp}({\text{BitDecomp}}^{-1}(A[i])){]}_{i\in [N]}$$ 即对矩阵的每一行进行 $\text{Flatten}$ 操作。注意，$\text{Flatten}$ 操作后的向量为0-1串，使得张量的范数很小。
$\text{Powersof2}$	对于 $k$ 维向量 $\vec{b}\in {\mathbb{Z}}_q^k$ ，将其转为 $N$ 维向量 $$\text{Powersof2}(\vec{b})=(b_1,2b_1,\cdots ,2^{l-1}{b}_1,\cdots ,b_k,2b_k,\cdots ,2^{l-1}{b}_k)$$ 即对于 $\vec{b}$ 中每一维元素，分别乘以2的阶梯幂次。

对于 ${\vec{a}}^{\prime }\in {\mathbb{Z}}_q^N,\vec{a},\vec{b}\in {\mathbb{Z}}_q^k$ ，存在以下关系：

• ${\text{BitDecomp}}^{-1}(\text{BitDecomp}(\vec{a}))=\vec{a}$
• $⟨\text{BitDecomp}(\vec{a}),\text{Powersof2}(\vec{b})⟩=⟨\vec{a},\vec{b}⟩$
• $⟨{\vec{a}}^{\prime },\text{Powersof2}(\vec{b})⟩=⟨{\text{BitDecomp}}^{-1}({\vec{a}}^{\prime }),\vec{b}⟩=⟨\text{Flatten}({\vec{a}}^{\prime }),\text{Powersof2}(\vec{b})⟩$

下面证明第三点：
$$\begin{array}{rl}⟨{\vec{a}}^{\prime },\text{Powersof2}(\vec{b})⟩& =\sum _{i=1}^k\sum _{j=0}^{l-1}{a}_{i,j}\cdot (2^j\cdot b_i)\\ & =\sum _{i=1}^k{b}_i\sum _{j=0}^{l-1}(2^j\cdot a_{i,j})\\ & =⟨{\text{BitDecomp}}^{-1}({\vec{a}}^{\prime }),\vec{b}⟩\end{array}$$同时
$$\begin{array}{rl}⟨\text{Flatten}({\vec{a}}^{\prime }),\text{Powersof2}(\vec{b})⟩& =⟨\text{BitDecomp}({\text{BitDecomp}}^{-1}(\vec{a})),\text{Powersof2}(\vec{b})⟩\\ & =⟨{\text{BitDecomp}}^{-1}(\vec{a}),\vec{b}⟩\end{array}$$

---

三、核心方案

1. 方案描述

流程	细节
参数设置	安全参数：$\lambda$ 电路深度：$L$ 比特数：$\kappa =\kappa (\lambda ,L)$ 模数：$q$ ，有 $\kappa$ 比特 误差分布：$\chi =\chi (\lambda ,L)$ 维度参数：设置 $n=n(\lambda ,L)$ 和 $m=m(\lambda ,L)=O(n\log q)$ ，令 $l=\lfloor \log q\rfloor +1$ 和 $N=(n+1)\cdot l$
密钥生成	私钥：随机采样 $\vec{t}\in {\mathbb{Z}}_q^n$，令 $\vec{s}=(1,-\vec{t})=(1,-t_1,\cdots ,-t_n)\in {\mathbb{Z}}_q^{n+1}$ ，则私钥为 $$\vec{v}=\text{Powersof2}(\vec{s})=\text{Powersof2}((1,-\vec{t}))$$ 其前 $l$ 维是 $[1,2,\cdots ,2^{l-1}]$ 。 公钥：随机采样矩阵 $B\in {\mathbb{Z}}_q^{m\times n}$ 和向量 $\vec{e}\in {\chi }^m$ ，令 $$\vec{b}=B\cdot \vec{t}+\vec{e}$$ 则 $A=[\vec{b}|B]\in {\mathbb{Z}}_q^{m\times (n+1)}$，这里可以观察到 $A\cdot \vec{s}=\vec{e}$ 。
加密算法	对于明文 $\mu \in {\mathbb{Z}}_q$ ，随机采样矩阵 R ∈ { 0 , 1 } M × m R\in \{0,1\}^{M\times m} R∈{0,1}M×m ，则密文为 $$C=\text{Flatten}(\mu \cdot I_N+\text{BitDecomp}(R\cdot A))\in {\mathbb{Z}}_q^{N\times N}$$
解密算法	令 $v_i=2^i\in (q/4,q/2]$ ， $C_i$ 为密文 $C$ 的第 $i$ 行，则解密有 $${\mu }^{\prime }=\lfloor \frac{⟨C_i,\vec{v}⟩}{v_i}\rceil$$
同态广播	密文矩阵 $C\in {\mathbb{Z}}_q^{N\times N}$ 与已知常量 $\alpha$ 相乘，令 $M_{\alpha }=\text{Flatten}(\alpha \cdot I_N)$ ，则广播运算如下 $$\text{MultConst}(C,\alpha )=\text{Flatten}(M_{\alpha }\cdot C)$$
同态加法	对于密文 $C_1,C_2\in {\mathbb{Z}}_q^{N\times N}$ ，同态加法如下 $$\text{Add}(C_1,C_2)=\text{Flatten}(C_1+C_2)$$
同态乘法	对于密文 $C_1,C_2\in {\mathbb{Z}}_q^{N\times N}$ ，同态乘法如下 $$\text{Mult}(C_1,C_2)=\text{Flatten}(C_1\cdot C_2)$$
同态与非	对于密文 $C_1,C_2\in {\mathbb{Z}}_q^{N\times N}$ ，同态与非门计算如下 $$\text{NAND}(C_1,C_2)=\text{Flatten}(I_N-C_1\cdot C_2)$$ 特别的，进行同态与非的明文只能是 0 或 1。

2. 噪声分析

2.1. 解密算法的噪声上界

$$\begin{array}{rl}⟨C,\vec{v}⟩& =⟨\text{Flatten}(\mu \cdot I_N)+\text{BitDecomp}(R\cdot A)),\text{Powersof2}(\vec{s})⟩\\ & =⟨\text{Flatten}(\mu \cdot I_N),\text{Powersof2}(\vec{s})⟩+⟨\text{BitDecomp}(R\cdot A)),\text{Powersof2}(\vec{s})⟩\\ & =\mu \cdot \vec{v}+R\cdot A\cdot \vec{s}\\ & =\mu \cdot \vec{v}+R\cdot \vec{e}\end{array}$$ 则对于 $⟨C,\vec{v}⟩$ 的每一行有 $x_i=\mu \cdot v_i+⟨R_i,\vec{e}⟩$ ，由于$R_i$ 为0-1比特串，误差项$⟨R_i,\vec{e}⟩$ 上界为 $|\vec{e}|\le B$。如果 $B\le q/8$ 且 $v_i\in (q/4,q/2]$ ，则 $|x_i/v_i-\mu |<1/2$，因此取整操作可以舍去误差。

2.2. 同态广播的噪声上界

$$\begin{array}{rl}⟨\text{MultConst}(C,\alpha ),\vec{v}⟩& =⟨\text{Flatten}(M_{\alpha }\cdot C),\vec{v}⟩\\ & =M_{\alpha }\cdot C\cdot \vec{v}\\ & =M_{\alpha }\cdot (\mu \cdot \vec{v}+R\cdot \vec{e})\\ & =\mu \cdot (M_{\alpha }\cdot \vec{v})+M_{\alpha }\cdot R\cdot \vec{e}\\ & =\mu \cdot ⟨\text{Flatten}(\alpha \cdot I_N),\vec{v}⟩+M_{\alpha }\cdot R\cdot \vec{e}\\ & =(\mu \cdot \alpha )\cdot \vec{v}+M_{\alpha }\cdot R\cdot \vec{e}\end{array}$$ 由于$M_{\alpha }$ 和 $R_i$ 为0-1比特串，则 $|M_{\alpha }\cdot R\cdot \vec{e}|\le |\vec{e}|\le B$ 。

2.3. 同态加法的噪声上界

$$\begin{array}{rl}⟨\text{Add}(C_1,C_2),\vec{v}⟩& =⟨\text{Flatten}(C_1+C_2),\vec{v}⟩\\ & =(C_1+C_2)\cdot \vec{v}\\ & =C_1\cdot \vec{v}+C_2\cdot \vec{v}\\ & =({\mu }_1\cdot \vec{v}+R_1\cdot {\vec{e}}_1)+({\mu }_2\cdot \vec{v}+R_2\cdot {\vec{e}}_2)\\ & =({\mu }_1+{\mu }_2)\cdot \vec{v}+(R_1\cdot {\vec{e}}_1+R_2\cdot {\vec{e}}_2)\end{array}$$ 由于$R_1$ 和 $R_2$ 由0-1比特组成，则噪声上界为 $|R_1\cdot {\vec{e}}_1+R_2\cdot {\vec{e}}_2|\le |R_1\cdot {\vec{e}}_1|+|R_2\cdot {\vec{e}}_2|\le |{\vec{e}}_1|+|{\vec{e}}_2|\le 2B$ 。

2.4. 同态乘法的噪声上界

$$\begin{array}{rl}⟨\text{Mult}(C_1,C_2),\vec{v}⟩& =⟨\text{Flatten}(C_1\cdot C_2),\vec{v}⟩\\ & =(C_1\cdot C_2)\cdot \vec{v}\\ & =C_1\cdot ({\mu }_2\cdot \vec{v}+R_2\cdot {\vec{e}}_2)\\ & ={\mu }_2\cdot (C_1\cdot \vec{v})+C_1\cdot R_2\cdot {\vec{e}}_2\\ & ={\mu }_2\cdot ({\mu }_1\cdot \vec{v}+R_1\cdot {\vec{e}}_1)+C_1\cdot R_2\cdot {\vec{e}}_2\\ & =({\mu }_2\cdot {\mu }_1)\cdot \vec{v}+({\mu }_2\cdot R_1\cdot {\vec{e}}_1+C_1\cdot R_2\cdot {\vec{e}}_2)\end{array}$$ 由于$R_1$ 、$R_2$ 和 $C_1$ 由0-1比特组成，则噪声上界为 $|{\mu }_2\cdot R_1\cdot {\vec{e}}_1+C_1\cdot R_2\cdot {\vec{e}}_2|\le |{\mu }_2\cdot R_1\cdot {\vec{e}}_1|+|C_1\cdot R_2\cdot {\vec{e}}_2|\le |{\mu }_2\cdot {\vec{e}}_1|+|C_1\cdot {\vec{e}}_2|\le (|{\mu }_2|+N)\cdot B$ 。由于 ${\vec{e}}_1$ 和 ${\vec{e}}_2$ 均为小噪声，因此噪声上界主要受 ${\mu }_2$ 影响。

3.5. 同态与非的噪声上界

$$\begin{array}{rl}⟨\text{NAND}(C_1,C_2),\vec{v}⟩& =⟨\text{Flatten}(I_N-C_1\cdot C_2),\vec{v}⟩\\ & =(I_N-C_1\cdot C_2)\cdot \vec{v}\\ & =\vec{v}-C_1\cdot C_2\cdot \vec{v}\\ & =\vec{v}-(({\mu }_2\cdot {\mu }_1)\cdot \vec{v}+({\mu }_2\cdot R_1\cdot {\vec{e}}_1+C_1\cdot R_2\cdot {\vec{e}}_2))\\ & =(1-{\mu }_2\cdot {\mu }_1)\cdot \vec{v}-({\mu }_2\cdot R_1\cdot {\vec{e}}_1+C_1\cdot R_2\cdot {\vec{e}}_2)\end{array}$$ 与同态乘法不同，进行与非运算的两个明文只能是 0 或 1，即 μ 2 ∈ { 0 , 1 } \mu_2 \in \{0,1\} μ2​∈{0,1}。因此，噪声上界为 $|{\mu }_2\cdot R_1\cdot {\vec{e}}_1+C_1\cdot R_2\cdot {\vec{e}}_2|\le |{\vec{e}}_1|+|C_1\cdot {\vec{e}}_2|\le (1+N)\cdot B$ 。

3. 正确性

解密成功的前提是最终误差小于 $q/8$。根据噪声分析我们发现，同态乘法的噪声增长受明文大小影响。为了控制同态计算中的噪声上界，我们有两种办法：

• 将评估函数转为布尔电路：由于与非门具有完备性，所有电路都可只用与非门构造。因此，将评估函数转为 $L$ 层与非门电路后，总误差上界可控制在 $(N+1{)}^L\cdot B$ 。因此，解密成功的前提是 $8\cdot (N+1{)}^L<q/B$，即模数要随电路深度呈指数级增长。
• 将评估函数转为算术电路：为控制噪声上界，限制明文大小 $|\mu |\le T$ ，其中 $B\ll T$。假设在此前提下，中间密文是 $T^{\prime }$-bound 的，那么最终误差上界为 $(N+T^{\prime }{)}^L\cdot B$ 。因此，解密成功的前提是 $8\cdot (N+T^{\prime }{)}^L<q/B$ 。

4. 安全性

• 若将评估函数转为布尔电路：为了保证 $2^{\lambda }$ 的安全级别，格维度 $n$ 要与 $\log (q/B)$ 成正比。其中， $q/B=O(N^L)$ 且 $N=(n+1)\cdot l=\tilde{O}(n)$，所以 $\log (q/B)=L\log (N)=L\log (n)$ ，即 $n=O(L\log (n))$。在渐进分析中，这意味着格维度要随电路深度增长。
• 若将评估函数转为算术电路： $m>2n\log q$ ，则方案的安全性可归约于 ${\text{LWE}}_{n,q,\chi }$ 难题。

6. 性能比较

若将评估函数转为 $L$ 层与非门电路，则每个 NAND 门的平均计算开销为 $\tilde{O}((nL{)}^{\omega })$ ，其中 $\omega <2.3727$ 。

• 优点：GSW方案中的密文矩阵是 0/1 矩阵，与现有方法在 ${\mathbb{Z}}_q$ 上的通用矩阵乘法相比，计算更快。同时，每门的计算开销低于现有方法的 $\tilde{O}(n^{3}L)$ 。
• 缺点：GSW方案的渐进优势 $\omega <2.3727$ ，在问题规模 $nL$ 非常大时才能体现出来，而在实际应用中常见的参数范围内，其巨大的常数因子和存储开销可能使其比某些更直接的方案更慢。

此外，Bootstrapping 是使同态加密方案的性能独立于 $L$ 的标准方法。在GSW方案中，其解密函数本质上是深度为 $O(\log n)$ 的 Regev 解密，因此将 $q/B$ 设置为关于 $n$ 的准多项式级别即可实现自举。

准多项式级别：对于常数 $c$，关于 $n$ 的准多项式级别是指 $$2^{O((\log n{)}^c)}$$

---

四、基于身份或属性的全同态加密方案

尽管已有部分 IBE 方案支持有限的同态运算，但构建能够提供完全同态或部分同态能力的 IBE 方案仍然是一个开放
问题。同时，现有的全同态加密方案在执行同态计算时均依赖用户特定的评估密钥，而该密钥无法由用户的身份或属性直接派生。因此，这类 FHE 方案也无法自然地转化为 IBE 或 ABE 方案。相比之下，GSW方案在同态计算时无需评估密钥，只需获取基础参数设置 $(n,m,l)$ ，因此可用于构建基于身份或属性的全同态加密方案。

1. 基于身份的全同态加密方案

下面介绍如何将 IBE 方案转为 IBFHE 方案。

1.1. 转化前提

只要一个基于 LWE 的 IBE 方案满足以下三个属性，则可以转化为 IBFHE：

• 对于身份 $id$ ，其解密密钥 ${\vec{s}}_{id}\in {\mathbb{Z}}_q^{n^{\prime }}$ 和密文 ${\vec{c}}_{id}\in {\mathbb{Z}}_q^{n^{\prime }}$ 都是 $n^{\prime }$ 维向量，且密钥 ${\vec{s}}_{id}$ 的第一维是1。
• 如果密文 ${\vec{c}}_{id}$ 加密了 $id=0$ ，则 $⟨{\vec{c}}_{id},{\vec{s}}_{id}⟩$ 非常小。
• 身份 $id=0$ 的密文 ${\vec{c}}_{id}$ 与 ${\mathbb{Z}}_q$ 上的随机数不可区分。

1.2. 转化方法

流程	细节
参数设置	直接使用原 IBE 方案的参数设置。
公钥生成	将原 IBE 方案的主公钥和 GSW 方案的公共参数一起作为 IBFHE 的主公钥。
加密算法	为了将消息 μ ∈ { 0 , 1 } \mu\in\{0,1\} μ∈{0,1} 加密后传给身份 $id$ ，首先使用原 IBE 方案的加密算法对 0 进行 $N$ 次加密，以这 $N$ 个密文向量为行，堆叠成一个矩阵 $C_{id}^{\prime }$ ；然后，用 GSW 的加密算法得到密文$$C_{id}=\text{Flatten}(\mu \cdot I_N+\text{BitDecomp}(C_{id}^{\prime }))$$
解密算法	身份 $id$ 用原 IBE 方案的密钥生成算法获得身份的解密密钥 ${\vec{s}}_{id}$ ，并计算私钥 ${\vec{v}}_{id}=\text{Powersof2}({\vec{s}}_{id})$ ，然后利用 GSW 的解密算法对密文解密。
同态计算	利用 GSW 的评估函数。

2. 基于属性的全同态加密方案

对于一个密文属性 $x$ 和一个用户密钥属性 $y$ 满足 $R(x,y)=1$ ，则解密过程中首先要生成一个与 $x,y$ 相关的子密钥 ${\vec{s}}_{x,y}$ ，则任何拥有满足条件密钥 $y$ 的用户都可以解密同态计算后的结果。