开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 区块链 -> 全同态加密：BGV -> 正文阅读

[区块链]全同态加密：BGV

参考文献：

Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on computing, 2014, 43(2): 831-871.
Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.
Peikert C. A decade of lattice cryptography[J]. Foundations and trends? in theoretical computer science, 2016, 10(4): 283-424.

基础知识

快速数论变换 NTT，在文章深入理解NTT 中介绍。BGV 方案中，使用多项式环 $\mathbb Z[x]/(f(x))$ ，其中 $f(x)=x^d+1$ 是分圆多项式， $d=2^k$ 是二的幂次。环 $R$ 包含所有次数小于 $d$ 的整系数多项式。然后，选取它的一个主理想 $I = (q (x))$ ，满足它的指数 $[R : I] = p$ 是个素数，即环 $R$ 是 $p$ 个陪集 $a_i+I,\, a_i \in R$ 的不交并。做商环：
$R_q = R/I = R = \mathbb Z[x]/(q(x),f(x))$

最简单的，可令 $q (x) = p$ 是个素数，那么 $R_q = \mathbb Z_p[x]/(f(x))$

假如 $\equiv 1 \mod 2d$ ，那么在 $R_p$ 上多项式 $f (x)$ 可以完全分解为线性的互素因式，
$x^d+1 = \prod_{i=1}^d (x-\xi_i)$

从而根据 CRT，令 $P_i = (x-\xi_i,\, p)$ 为彼此互素的理想，有：
$R_p \cong \mathbb Z[x]/P_1 \times \cdots \mathbb Z[x]/P_d$

简记 $\mathbb Z[x]/P_i = R_{P_i}$

LWE 和 RLWE 问题，在文章格上困难问题中介绍。为了方便方案的描述，BGV 不想对两种格困难问题分别构造方案，因此定义了 General Learning with Errors (GLWE) Problem：

在这里插入图片描述

其中的噪声分布（一般取做离散高斯分布） $\chi$ 是 B-bounded distributions，定义如下：

在这里插入图片描述

格上的陷门，在文章格密码：陷门OWF 中介绍。在 BGV 中对 Gadget 的描述为：
$G:=I_n \otimes g= \left[ \begin{array}{c | c c c} g & 0 & \cdots \\ \hline 0 & g & 0 \\ \vdots & 0 & \ddots & \vdots\\ & & ... & g\\ \end{array} \right] \in \mathbb Z_q^{n \times nl}$

其中 $q$ 是素数， $\lceil \log q \rceil$ ， $g=[1,2,4,\cdots,2^{l}]$

$\vec x = G \vec u$ ：将向量 $\vec u \in R_2^{nl}$ 分成 $n$ 块，每个长为 $l$ 的 block 做二进制合成，得到向量 $\vec x \in R_q^n$
$\vec u = G^{-1}(x)$ ：将向量 $\vec x \in R_q^n$ 的每个分量都做二进制分解，得到向量 $\vec u \in R_2^{nl}$

BGV

Basic Encryption Scheme

BGV 方案基于 BV 方案（在文章全同态加密(FHE) 中介绍）。在 BGV 中，首先表述了基于 GLWE 的 BV 方案：

$E.Setup(1^\lambda,1^\mu,b)$ ：
- 如果 $b = 0$ ，那么设置 $d = 1$ （LWE），如果 $b = 1$ ，那么设置 $n = 1$ （RLWE）。甚至，可以设置这两个极端之间的参数？
- 选取 $\mu$ 比特的素数模 $q$ ，设置 $d=d(\lambda,\mu,b)$ ， $n=n(\lambda,\mu,b)$ ， $N=\lceil (2n+1)\log q \rceil$ ， $\chi = \chi(\lambda,\mu,b)$ ，使得 GLWE 实例的强度为 $2^\lambda$
- 令 $R=\mathbb Z[x]/(x^d+1)$ ，明文空间为 $R_p$ ，其中 $\ll q$ 是素数（例如 $p = 2$ ），密文空间为 $R_q^{n+1}$
- 设置 $params=(R,p,q,d,n,N,\chi)$
$E . S ecre t Key G e n (p a r am s)$ ：
- 采样 $\leftarrow \chi^n$ ，设置 $\in R_q^{n+1}$
$E.PublicKeyGen(params,\, sk)$ ：
- 生成均匀随机矩阵 $\leftarrow U(R_q^{N \times n})$ ，采样 $\leftarrow \chi^N$
- 计算 $b = A^{'} s^{'} + p e$ ，使得噪音 $p e$ 属于理想 $(p)$
- 设置 $\in R_q^{N \times (n+1)}$ ，易知 $\equiv 0 \mod (p)$
$E.Enc(params,\, pk,\, m)$ ：
- 给定明文 $\in R_p$ ，设置行向量 $\vec m = (m,0,\cdots,0) \in R_q^{n+1}$
- 采样行向量 $\leftarrow R_p^N$ ，输出密文
  $\vec m+rA \in R_q^{n+1}$
$E.Dec(params,\, sk,\, c)$ ：
- 给定密文 $\in R_q^{n+1}$ ，输出明文
  $m=[[<c,s>]_q]_p \in R_p$
  
  其中 $[\cdot]_q$ 表示模 $q$ 的余数，范围 $(? q /2, q /2]$

在 BGV 中 $\equiv [<c,s>]_q \mod p$ ，可将 $[<c,s>]_q \in R_q$ 视为由明文 $m$ 编码的噪声。

Homomorphic Operations

矩阵 $\in R^{m \times n},\, B \in R^{p \times q}$ 的 Kronecker product 定义为：
$\otimes B = \left[ A_{ij} \cdot B \right]_{ij} \in R^{mp \times nq}$

克罗内克积是结合的，但不是交换的
克罗内克积与矩阵加法间，满足左右分配律
$\otimes B)^T = A^T \otimes B^T$ ， $\otimes B)^{-1} = A^{-1} \otimes B^{-1}$ ，注意对比 $AB)^T = B^TA^T$ 、 $AB)^{-1} = B^{-1}A^{-1}$ 、 $AB)^* = B^*A^*$ （穿脱原理）
$(X\otimes Y)(U \otimes V) = (XU) \otimes (YV)$
对于 $\in R^{m \times m},B \in R^{n \times n}$ ，有 $\otimes B)=det(A)^n \cdot det(B)^m$
$\otimes B) = rank(A) \cdot rank(B)$

根据上述性质，易知
$\begin{aligned} <c_1 \otimes c_2,\, s_1 \otimes s_2> &= (c_1 \otimes c_2)^T (s_1 \otimes s_2)\\ &= (c_1^T \otimes c_2^T)(s_1 \otimes s_2)\\ &= (c_1^T s_1) \otimes (c_2^T s_2)\\ &= <c_1,s_1> \cdot <c_2,s_2> \end{aligned}$

因此，

同态加法： $Dec(c_1+c_2,\, s) = Dec(c_1,s)+Dec(c_2,s)$
同态乘法： $Dec(c_1 \otimes c_2,\, s \otimes s) = Dec(c_1,s) \cdot Dec(c_2,s)$

然而，上述的同态乘法有很大的缺陷：密文和私钥的规模指数级增大，噪声指数级增大。

Key Switching

密钥切换技术，用于降低密文和密钥的维度。

BGV 将 Gadget 视为二进制合并和分解，

在这里插入图片描述

有 $BitDecomp(c)=G^{-1}(c),\, Powersof(s)=s^TG$ ，易知：
$\begin{aligned} &<BitDecomp(c,q),Powersof(s,q)> \\ &= \sum_{j=0}^{l-1}<u_j,2^j s> \\ &= <c,s> \\ &= s^TG \cdot G^{-1}(c) \end{aligned}$

密钥切换的程序为：

在这里插入图片描述

可以理解为：寻找 $s_2^TK=s_1^TG$ 的 $K$ ，设置 $c_2=K \cdot G^{-1}(c_1)$ ，于是 $s_2^Tc_2 = (s_1^TG) \cdot G^{-1}(c_1) = s_1^Tc_1$

Modulus Switching

模切换技术，用于降低噪声的绝对大小（相对大小略有上升）。

模切换技术并不能降低噪声比率（the ratio of the noise to the “noise ceiling” (the modulus size)），而噪声比率约束了密文的同态能力。似乎降低噪音绝对大小并不会提高同态能力。然而，对于乘法来说：

噪声大小为 $x$ ，假设 $q\approx x^k$ ，于是噪声比率为 $\approx x^{1-k}$
选择 a ladder of gradually decreasing moduli $\{q_i \approx \dfrac{q}{x^i}\}$
每次密文乘法，导致结果的噪声从 $x^a$ 成为 $x^{2a}$
假设不做模切换，那么下一次乘法将会达到 $x^4$ 的噪声，最多只能做 $\log k$ 次乘法，噪声就会达到 $x^k=q$ ，导致不可解密。
如果每次都做模切换，第 $j$ 次乘法后，从 $q_{j-1}$ 切换到 $q_{j}$ 上，同时噪声从 $x^2$ 降低到 $x$ ，比率为 $x/q_{j} = x^{j-k}$ ，因此最多可以做 $k$ 次乘法。

模切换的程序为：

在这里插入图片描述

(Leveled) FHE Based on GLWE without Bootstrapping

如果设置 Basic Encryption Scheme 的明文空间为 $R_2$ ，那么 BGV 方案如下：

在这里插入图片描述

其同态运算为：

在这里插入图片描述

由于密钥切换和模切换，都是算术电路上计算的，因此它们比 Bootstrapping 的布尔电路计算要高效的多。为了计算深度 $d$ 的算术电路，只要在初始化的时候设置 $L = d$ 即可。

但随着 $L$ 增大，模数 $q_L$ 的比特长度会线性增长，从而导致每个 Gate 的计算复杂度上升。对于很深的电路，我们可以重新引入 Bootstrapping 作为优化（而非必需）。

Optimizations

Batching

上述的 BGV 方案中，设置了 $p = 2$ ，从而可以对商环 $R_2$ 上的明文做运算。

奇素数 $\equiv 1 \mod 2d$ ，根据数论可以知道，
$R_p \cong R_{P_1} \times \cdots \mathbb R_{P_d}$

其中 $P_i = (p,x-\xi_i)$ ，且陪集 $0+P_i,\cdots,(p-1)+P_i$ 恰好拼成整个环 $R=\mathbb Z[x]/(f(x))$ ，或者说 $I$ 作为加群的指数为 $[R : I] = p$ （Emmmm, 怎么觉得不太对呢？）

上述的每个理想都是同构的，存在环 $R$ 的自同构（automorphism） $\sigma_{i \to j}$ ，使得 $\sigma_{i \to j}(P_i)=P_j$ ，确切地说：
$\sigma_{i \to j}\left(\sum_{i=0}^{d-1}r_ix^{d-1} \in P_i \right) = \sum_{i=0}^{d-1}r_ix^{e_{ij}(d-1) \mod 2d} \in P_j$

其中 $e_{ij} \in [1,2d]$ 是奇数。

于是，我们可以将一个密文上划分出 $d$ （或者 $d$ 的因子，类似不完全NTT）个明文槽（plaintext slots），第 $i$ 个明文的取值范围是理想 $P_i$ 对应的商环 $R_{P_i}$

我们使用 RLWE 版本的 BGV 方案，

设置 $n = 1$ ，令 $d=2^k$ 是二的幂次，选取奇素数 $\equiv 1 \mod 2d$
在 $E . P u b l i cKey G e n ()$ 中，设置 $A s = p e$
在 $E . Dec ()$ 中，设置 $m = [[<c,s>]_q]_p$
在 $S c a l e ()$ 中，设置 $r = p$
同态运算都是在 mod-p gates 的电路上的

注意，这里的 $p=O(poly(\lambda))$ ，此时同态运算的额外的噪声是多项式的。对于超多项式的 $p$ ，噪音增长严重，从而无法使用。

使用 Batching 技术，计算一个密文的同态运算，就达到了 $d$ 个明文的运算，因此效率几乎（因为模数 $q (x)$ 从 $2$ 增大到了 $p$ ，算术运算会慢一些）提高了 $d$ 倍。

Bootstrapping as an Optimization

自举的优点为：

Performance： $L$ 不必设置的和电路深度一样大，于是每个门的计算复杂度独立于电路深度，计算效率高。
Flexibility：假设循环安全，那么自举将导致无限深度的电路，而不必预设电路深度上界，更加灵活。
Memory：可以把原始数据的密文用 AES 存储，占内存很小。当需要计算时，用 Bootstrapping 执行解密电路，解压（de-compressed）为长密文，再执行同态运算。解压的长密文没法重新变回 AES 短密文。

对于 LWE 版本的 BGV，解密函数为： $m = [[<c,s>]_q]_2$ ，可以用 $R_2=\mathbb Z_2$ 上的算术电路来计算它：

内积中的对应分量两两乘积，由于 $c [i]$ 有 $\log q$ 比特，因此 $\cdot s[i]$ 可以写成至多（比特 $0$ 的不必相加） $\log q$ 个 $s [i]$ 的左移的加和。一个 $s [i]$ 的左移，它的长度至多为 $\log q$ 比特。
一个内积有 $n$ 个对应分量，共需要 $\log q$ 个 $\log q$ 比特数的加和。使用二叉树式的电路，深度为 $O(\log(n \log g)) = O(\log n + \log\log q)$ ，逻辑门的数量为 $\log q \cdot \log q) = O(n \log^2 q)$
然后，计算 $<c,s>\mod q$ ，除法可以转化为乘法，电路大小为 $O(poly\log(q))$ ，电路深度为 $O(\log\log q)$
最后，计算 $\mod q) \mod 2$ ，仅需要截取最低位比特。
综上所述，Bootstrapping 的电路深度为：
$O(\log n + \log\log q)$

电路大小为：
$O(n \log^2 q)$

代入安全参数 $n=O(\lambda)$ 和 $\log q = O(\log \lambda)$ ：电路大小为 $\tilde O(\lambda)$ ，电路深度为 $O(\log \lambda)$

对于 RLWE 版本的 BGV，解密函数中的向量长度为 $2$ ，每个分量都是多项式环 $\mathbb Z_2[x]/(f(x))$ 上的乘积，可以使用 DFT 来计算。其 Bootstrapping 的电路规模与 LWE 版本的类似。

由于噪声增长的没那么快，因此我们可以 Bootstrapping Lazily，每 $L$ 层才自举一次，其他层都不执行自举程序。经最优化，得到：
$\theta(\log \lambda)$

Batching the Bootstrapping Operation

上述的 Batching 方案，每个明文槽都只能和对应的明文槽内的明文做运算。如果我们想让它们之间也可以交互计算怎么办呢？

思路是，

规定普通密文仅使用第一个明文槽 $R_{P_1}$ ，其他的槽中都是 $\in R_{P_i},\, i \neq 1$
利用理想之间的环 $R$ 自同构映射 $\sigma_{i \to j}$ ，将各个槽里的明文进行搬移，
$m=[[<c,s>]_q]_{P_i} \iff m=[[<\sigma_{i \to j}(c),\sigma_{i \to j}(s)>]_q]_{P_j}$
选取 $\in 1+P_1$ ，且 $\in P_i,i \neq 1$ ，这用于将其他槽的内容清零。

实现 Pack 和 Unpack 函数，进行 normal homomorphic operation 和 batch operation 之间的转换：

在这里插入图片描述

只要上边的私钥链 $s_1,s_2,\cdots$ 是无环的，那么就可以避免 circular security problem，但需要存储的密钥切换映射 $\tau$ 就会多一些。如果我们假设它是循环安全的，那么就只需要存储一个私钥 $s$ 的那些映射即可。

利用上述的 Pack 和 Unpack，就可以对电路同一层的密文执行并行的 Bootstrapping。如果电路的宽度足够大（每一层的宽度为 $O(\lambda)$ ），那么 Bootstrapping 的计算复杂度可以降低一个 $\log \lambda$ 因子。

其实上边的 Pack 和 Unpack 更重要的是：可以在明文需要串行计算时串行，可以并行计算时并行。从而加速单个算术电路的计算效率。否则，Batching 只能并行计算 $d$ 个相同电路的 copy，对于不同的明文输入。

Plaintext Spaces

上述的方案中， $R_q$ 上的 $q_j(x)$ 都选做了素数。如果我们想要在很大的明文空间 $\mathbb Z_p$ 上运算，那么 $q_j$ 就不得不选取为安全参数 $\lambda$ 的指数级。此时 $q_j/B$ （ $B$ 是噪声上界）是指数级的，导致 LWE 问题不难。

因此，我们不直接使用 $\mathbb Z_p$ 作为明文空间，而是使用同构的 $R / I$ ，其中 $[R ； I] = p$ ，同时获得理想 $I$ 的一组短格基 $B_I$ （ $\|B_I\|=O(poly(d) \cdot p^{1/d})$ ）。对于“ladder”，我们选取多项式 $q_j \in R$ ，构造主理想 $q_j)$ ，使它满足 $q_j \in 1+I$ 且 $q_{j+1}\|/\|q_j\|$ 大约为 $2^\mu$ 大小，令理想 $q_j)$ 的 rotation basis 为：
$B_{q_j} = \{x^iq_j(x) \mod f(x)\}_{i=0}^{d-1}$