BGV同态加密方案是由Zvika Brakerski, Graig Gentry, Vindo Vaikuntanathan提出于[BGV12] ¹. 该方案是BV11b方案基础上一个较大的改进. 该方案挖掘出BV11b方案中模数切换可以降低密文的绝对噪声这一特点, 将其发扬广大, 使得在加密在无需Bootstrapping的情况下可以做到较多层数的同态乘法运算.

如果需要实现全同态加密, 该方案仍需要引入Circular Security假设和Boostrapping. 但是由于模数切换使得我们可以在不进行Bootstrapping的情况下做较多次数的同态运算, 并且使得Bootstrapping之前的密文模数变得非常小, 因此Bootstrapping是非常容易的. 因此该方法能够显著降低Bootstrapping的次数和难度.

简介

我们在介绍BV11b方案的时候, 介绍过密文的格式为 $(v, w)$ , 此处我们忽略了密文的同态层数. 密钥的解密可以表示为

$Dec (s k = s^{'}, (v, w))$ : 计算并输出

$(w - ⟨ v, s^{'} ⟩ \mod q) \mod 2$

我们将采用另一种形式的LWE加密来表示上述问题(在LWE介绍性文章(写成后地址将被更新到这里)以及本文之后的内容会有介绍), 用 $c$ 表示密文, 用 $s$ 表述明文, 上述解密过程可以被简化为 $[[⟨ c, s ⟩]_{q}]_{2}$ , 其中 $[\cdot]_{k}$ 表示模 $k$ 运算. 这种形式的密文噪声体现在哪里呢? 其实本身就是大 $[⟨ c, s ⟩]_{q}$ 概的噪声.

BV11b的核心思想之一是在最后同态计算结束后, 需要将大密文(即维数和模数较大的密文)转换为小密文(即模数和维数较小的密文). 其中, 维数切换的操作是平凡, 而模数切换的操作需要一定的技巧性, 且其安全性依赖于稀疏子集和假设. 一个不太让人感觉到的惊奇的现象是, 在进行模数切换的时, 噪声也成比例减小了. 即我们有如下引理:

引理1 设 $p$ 和 $q$ 是两个奇数模数, $c$ 是一个整数向量. 令 $c^{'}$ 为一个距离 $(p / q) \cdot c$ 最近的一个整数向量满足 $c^{'} = c \mod 2$ . 则对于任意的 $s$ 使得 $| [⟨ c, s ⟩]_{q} | < q / 2 - (q / p) \cdot ℓ_{1} (s)$ 有 $[⟨ c^{'}, s ⟩]_{p} = [⟨ c, s ⟩]_{q} \mod 2$ 且 $| [⟨ c^{'}, s ⟩]_{p} | < (p / q) \cdot | [⟨ c, s ⟩] | + ℓ_{1} (s)$ 其中 $ℓ_{1} (s)$ 是 $s$ 的第一范数.

第一个结果能够保持我们在输入正确密钥时解密结果的正确性, 而第二个结果则表明我们确实几乎在模数切换的同时几乎时等比例缩小了噪声, 这是由于从噪声分布中选择 $s$ 的LWE具有从均匀分布中选择 $s$ 的LWE具有几乎相当的平均意义下的困难性, 这使得我们的加密方案中 $s$ 可以选自噪声分布 $χ^{n}$ 使得 $ℓ_{1} (s)$ 较小. 下面我们来证明上述引理.

证明: 根据假设, 对于某个整数 $k$ 有 $[⟨ c, s ⟩]_{q} = ⟨ c, s ⟩ - k q$ . 假设 $e_{p} = ⟨ c^{'}, s ⟩ - k p$ , 我们现在证明 $e_{p}$ 大概就是 $c^{'}$ 的噪声, 即 $e_{p} = [⟨ c^{'}, s ⟩]_{p}$ . 由于 $c^{'} = c \mod 2$ 且 $p = q \mod 2$ , 因此 $e_{p} = [⟨ c, s ⟩]_{q} \mod 2$ . 由于 $\begin{aligned} e_{p} & = ⟨ c^{'}, s ⟩ - k p = ⟨ c^{'}, s ⟩ - k q \cdot \frac{p}{q} \\ = ⟨ c^{'}, s ⟩ + \frac{p}{q} \cdot ([⟨ c, s ⟩]_{q} - ⟨ c, s ⟩) \\ = \frac{p}{q} \cdot [⟨ c, s ⟩]_{q} + ⟨ c^{'} - (p / q) c, s ⟩ \end{aligned}$ 即 $| e_{p} | \leq (p / q) [⟨ c, s ⟩]_{q} + ℓ_{1} (s) < p / 2$ . 从第二个不等式中, 我们得出, $e_{p}$ 大概就是 $c^{'}$ 的噪声, 因此有 $| [⟨ c^{'}, s ⟩]_{p} | < (p / q) \cdot | [⟨ c, s ⟩] | + ℓ_{1} (s)$ .

从上式的证明中, 我们也可以看出额外的噪声是如何引入的, 即从 $⟨ c^{'} - (p / q) c, s ⟩$ 中产生.

到了这里你也许就明白这个方案的工作原理了: 虽然噪声是和模数等比例缩小的, 但是如果噪声本身就比较小, 那么通过模数切换, 它将变得非常小, 使得一次乘法同态运算后噪声也不会变得太大. 例如两个模 $q$ 噪声为 $B$ 的密文进行同态乘法运算, 其结果噪声将会达到约 $B^{2}$ , 而将其模数切换为 $p$ 后噪声为约 $p B / q$ . 再做乘法同态运算, 则噪声是 $(p B / q)^{2}$ . 我们发现, 虽然 $B / q \approx (p B / q) / p$ , 但是做同态乘法运算后, 小密文产生的结果噪声占比约为 $(p B / q)^{2} / q = p^{2} B / q^{3}$ , 而原先的大密文噪声扎占比约为 $B^{2} / q$ , 显然小密文更占优势.

基于如上的思想, 我们可以从一开始就选择非常大的模数 $q_{0}$ , 使得模数可以接受多次模数切换操作, 这样每次对噪声上界为 $B$ 得密文做乘法后我们就进行一次模数切换, 将模数变成 $q_{i} \approx q_{i - 1} / B$ , 即模数变为原来的大概 $1 / B$ , 来使得噪声不变得更大, 我们就可以在做到多次同态后, 使得噪声上界始终维持在一个较为稳定的范围内. 这个过程可以一直持续到我们将模数下降得太小(使得 $B > q_{L} / 2$ )之前.

如果不进行模数切换, 噪声是双指数倍数增长的, $B$ 噪声的密文经过 $L$ 次同态变成 $B^{2^{L}}$ 很快就能接近 $q_{0} / 2$ , 而做模切换噪声则是指数下降的, 使得 $q_{i} \approx q_{0} / B^{i}$ 满足 $B > q_{i} / 2$ 显然要比原来的方案慢得多, 因此我们就可以进行更多次的同态乘法运算.

GLWE介绍

在本文中, 作者将LWE与RLWE统一为了GLWE, 使得在介绍方案的时候不用重复劳动. 我们按照作者的思路, 对GLWE一些介绍.

GLWE (General Learning with Errors) 是一种将LWE与RLWE统一的表示方式. 我们知道, LWE的元组都是 $Z_{q}^{n} \times Z_{q}$ , 而RLWE的元组都是来自 $R_{q} \times R_{q}$ , 我们注意到有一个维数 $n$ 来描述元组中第一个选自均匀分布的元. 如果我们将 $Z$ 也视作是一个环, 那么LWE的元组基于的环是 $Z_{q} = Z / q Z$ , 而RLWE基于的则是 $R_{q} = R / q R$ , 即可将二者也统一起来. 这样, 我们通过两个参数就可以确定我们选择的是LWE还是RLWE, 即元组中第一个元的维数 $n$ (对于LWE来说, $n = poly (n)$ , 对于RLWE来说 $n = 1$ ), 以及元组所基于的环 $R$ . 我们用这种记法表示统一表示二者, 即GLWE.

定义2 GLWE

设安全参数为 $λ$ , 令 $n = n (λ)$ 为一个整数维数, 令 $f (x) = x^{d} + 1$ 其中 $d = d (λ)$ 是一个2的指数幂, ling $q = q (λ) \geq 2$ 是一个素数², 令 $R = Z [x] / (f (x))$ 和 $R_{q} = R / q R$ , 令 $χ = χ (λ)$ 是一个 $R$ 上的分布. GLWE $_{n, f, q, χ}$ 问题, 定义为区分如下两个分布:

$R_{q}^{n + 1}$ 上的均匀分布.

由如下方式产生的分布: 首选均匀生成 $a \overset{$}{\leftarrow} R_{q}^{n}$ 和 $s \overset{$}{\leftarrow} R_{q}^{n}$ , 选择 $e \leftarrow χ$ , 然后输出 $(a, b = ⟨ a, s ⟩ + e)$ .

现在我们介绍GLWE困难的参数假设. 我们认为, 满足参数 $n \cdot d = Ω (λ \log (q / B))$ 的GLWE问题是安全的, 其中 $B$ 表示 $χ$ 输出的元素的长度上界. 目前该假设还未被证明, 但是也没有出现分析结果. 这里需要再次重申一下: GLWE的定义仅仅是为了我们的描述方便, 即我们实际上还是在基于LWE假设RLWE假设构造公钥加密方案和全同态加密方案. 也就是说, 你无需关心那些最终参数使得GLWE不是LWE或RLWE的参数.

Leveled FHE构造

现在, 我们就来构造安全性基于GLWE的Leveled FHE方案. 这个方案采用了模数切换来控制噪声, 使得噪声始终维持在较小的水平, 而使得我们可以进行较多次的乘法同态运算. 不过在此之前, 我们还是像BV11b基于LWE的公钥加密方案一样, 我们先构造好基于GLWE的公钥加密方案.

基于GLWE假设的公钥加密方案

该方案在选择 $n = 1$ 和环 $R = Z$ 时, 得到的加密方案实际上是同BV11b中的LWE公钥加密方案是类似的, 但是有两点不同:

由于换了一种LWE的形式, 密钥的形式和最终解密的形式看起来略有不同.
基础密钥 $s^{'}$ 的选择来自于 $χ^{n}$ , 则是为了保证 $s^{'}$ 的第一范数较小, 从而使得我们在模数切换的时候能够有效控制噪声.

对于第一点不同, 熟悉LWE的读者可以立即看出来, 这仅仅是由于我们不再单独写出 $b = A^{'} s^{'} + 2 e$ , 而是将它作为矩阵的一列写进了 $A = [b | - A^{'}]$ .

基于GLWE假设的公钥加密方案:

$E . Setup (1^{λ}, 1^{μ}, b)$ : 由比特 $b$ 来确定我们是构造LWE假设下的方案( $b = 0$ )还是RLWE假设下的方案( $b = 1$ ). 选择一个 $μ$ 比特的模数 $q$ 和参数 $d = d (λ, μ, b), n = n (λ, μ, b), N = ⌈ (2 n + 1) \log q ⌉, χ = χ (λ, μ, b)$ 此处要求最终的参数使得GLWE问题实例具有安全性. 令 $R = Z [x] / (x^{d} + 1)$ , 并令参数集合 $p a r a m s = (q, d, n, N, χ)$ .
$E . SecretKeyGen (p a r a m s)$ : 选择 $s^{'} \leftarrow χ^{n}$ , 输出 $s k = s = (1, s^{'} [1], \dots, s^{'} [n]) \in R_{q}^{n + 1}$ .
$E . PublicKeyGen (p a r a m s, s k)$ : 均匀选择 $A^{'} \overset{$}{\leftarrow} R_{q}^{N \times n}$ , 选择 $e \leftarrow χ^{N}$ 并令 $b = A^{'} s^{'} + 2 e$ . 并令 $p k = A = [b | - A^{'}]$ .
$E . Enc (p a r a m s, p k, m \in {0, 1})$ : 令 $m = (m, 0, \dots, 0) \in R_{q}^{n + 1}$ , 选择 $r \overset{$}{\leftarrow} R_{q}^{N}$ , 输出密文 $c = m + A^{T} r \in R_{q}^{n + 1}$ .
$E . Dec (p a r a m s, s k, c)$ : 输出 $m \leftarrow [[⟨ c, s ⟩]_{q}]_{2}$ .

现在我们来看一下这个加密及解密过程为什么同BV11b中的方案是一样的. 对于加密来说, $c = m + [b | - A^{'}]^{T} r = (b^{T} r + m, - A^{' T} r)$ 可见, 这就是把BV11b中密文的两部分写在了一起. 而解密操作也是类似 $\begin{aligned} ⟨ c, s ⟩ & = b^{T} r + m - ⟨ A^{' T} r, s^{'} ⟩ = b^{T} r + m - (A^{'} s^{'})^{T} r \\ = b^{T} r + m - (b - 2 e)^{T} r = m + 2 e \end{aligned}$ 其中 $e = e^{T} r$ . 可见, 解密过程也是和BV11b中的方案是相同的.

其他符号介绍

这里使用的技术喝BV11b中基本是一样的, 只是由于模数切换的原因, 我们需要经常处理不同的模数, 因此几个函数中多了模数这一个参数. 此外, 结果的顺序也由有所不同.

$BitDecomp (x \in R_{q}^{n}, q)$ : 即将 $x$ 拆解成其二进制表示, $x = \sum_{j = 0}^{⌊ \log q ⌋} 2^{j} \cdot u_{j}$ , 其中 $u_{j} \in R_{2}^{n}$ . 输出 $(u_{0}, u_{1}, \dots, u_{⌊ \log q ⌋})$ .

显然有 $x [i] = \sum_{j = 0}^{⌊ \log q ⌋} 2^{j} \cdot u_{j} [i]$ . 类似的, 定义

$Powerof 2 (x \in R_{q}^{n}, q)$ : 输出 $(x, 2 \cdot x, \dots, 2^{⌊ \log q ⌋} \cdot x$ ).

根据以上的定义, 我们有 $⟨ BitDecomp (c, q), Powerof 2 (s, q) ⟩ = ⟨ c, s ⟩$

密钥切换

现在我们来介绍密钥切换的具体过程. 与其说是介绍, 不如说是熟悉我们的新记号. 回顾一下我们要将密钥 $s_{1}$ 下的密文 $c_{1}$ 切换的到密钥 $s_{2}$ 下的密文 $c_{2}$ , 我们就要用 $s_{2}$ 作为私钥来生成一个LWE公钥并"加密" $s_{1}$ 的每个项的每个Powerof2, 即需要每个 $2^{τ} \cdot s_{1} [i]$ 的"密文". 我们将这些"密文"项的集合记作 $τ_{s_{1} \to s_{2}}$ . 第二部就是将 $τ_{s_{1} \to s_{2}}$ 带入到 $c_{1}$ 中来生成密文 $c_{2}$ . 我们将这两个过程形式化. 首先第一步是要生成 $τ_{s_{1} \to s_{2}}$ , 即

$SwitchKeyGen (s_{1}, s_{2}, n_{1}, n_{2}, q)$ :
1. 对于每个 $N = n_{1} \cdot ⌊ \log q ⌋$ , 执行 $A \leftarrow E . PublicKeyGen (s_{2}, N)$ .
2. 令 $B = A + [Powerof 2 (s_{1}) | 0]$ . 输出 $τ_{s_{1} \to s_{2}} = B$ .

其中第二步是一个批量操作, 此处是在将 $Powerof 2 (s_{1})$ 加到 $A$ 的第一列上去.

看到这里你也许会觉得蹊跷, 为什么没有二次项了? 实际上这里作者又换了一种写法, 将 $s_{1}$ 就视作是含有二次项的项. 在之前的BV11b方案中, 假设两个密文 $c, c^{†}$ 均为 $s$ 的密文, 那么他们做第一步同态运算但不替换密钥时, 则新的多项式函数(由新密文 $c^{'}$ 表示的多项式函数)会包含 $s [i] s [j]$ 项. 实际上, 我们大可不必这么认为, 我们可以认为有一个新的密钥向量 $s_{1}$ 包含了所有的 $s [i] s [j]$ 项, 我们只需要认为 $s^{'} = s \otimes s$ 即可. 实际上作者比我们还要更激进一点, 此时作者认为还可以将 $c^{'}$ 进行 $Powerof 2$ 操作, 得到 $c_{1} = Powerof 2 (c^{'})$ , 该密文就应该是 $s_{1} = BitDecomp (s^{'})$ 下的密文. 同态运算第一步之后的结果即可认为是新密钥下的密文, 而我们的"加密"了所有的 $2^{τ} \cdot s_{1} [i]$ 项就是相当于时"加密"了所有的 $2^{τ} \cdot s_{i, j}$ 项了. 我们用 $τ_{s_{1} \to s_{2}}$ 即可进行下一步的私钥切换.

$SwitchKey (τ_{s_{1} \to s_{2}}, c_{1})$ : 输出 $c_{2} = BitDecomp (c_{1})^{T} \cdot B \in R_{q}^{n_{2}}$ .

模数切换

模数切换的方法我们也已经在前文中介绍完毕, 现在将其形式化

$Scale (x, q, p, r)$ : 输出距离 $(p / q) \cdot x$ 最近且满足 $x^{'} = x \mod r$ 的向量 $x^{'}$ .

很明显, 这里我们是要将 $q$ 模数下的密文 $x$ 切换到 $p$ 模数下的密文 $p$ . 而一般来说, 我们只加密一个比特, 即选择 $r = 2$ .

我们之前已经估计了对于LWE下的密文, 这么做会导致噪声如何变化, 那么对于RLWE, 有类似的结果吗? 有的, 正如如下引理

引理3 设 $d$ 是多项式环的次数. 令 $q > p > r$ 为满足 $p = q = 1 \mod r$ 的正整数. 令 $c \in R^{n}$ 和 $c^{'} = Scale (c, q, p, r)$ . 则对于任意 $s \in R^{n}$ 满足 $| [⟨ c, s ⟩]_{q} | < q / 2 - (q / p) \cdot (r / 2) \cdot \sqrt{d} \cdot γ (R) \cdot ℓ_{1}^{(R)} (s)$ , 则有 $[⟨ c^{'}, s ⟩]_{p} = [⟨ c, s ⟩]_{q}$ 且 $| [⟨ c^{'}, s ⟩]_{p} | < (p / q) \cdot | [⟨ c, s ⟩]_{q} | + (r / 2) \cdot \sqrt{d} \cdot γ (R) \cdot ℓ_{q}^{(R)} (s)$

其中 $γ (R)$ 为仅与 $R$ 相关的任何函数, 而 $ℓ_{q}^{(R)}$ 表示环 $R$ 上定义的第一范数. 这个地方在介绍了RLWE后我将会回来补充. 这个引理的证明方式和引理1类似, 就不在这里赘述, 希望知道具体过程的读者可以翻阅[BGV12]论文中Lemma 4的证明.

Leveled FHE方案

铺垫到这里, 我们终于可以拿出LWE方案了. 实际上这里相比BV11b并没有多少新内容, 我们做的大部分工作是在带大家适应新的符号和解释模数切换的好处.

首先和其他的Leveled FHE一样, 有个Setup阶段

$FHE . Setup (1^{λ}, 1^{L}, b)$ : 设 $μ = μ (λ, L, b) = θ (\log λ + \log L)$ . 对于每个 $j = L to 0$ :
1. 执行 $p a r a m s_{j} \leftarrow E . Setup (1^{λ}, 1^{(j + 1) \cdot μ}, b)$ , 其中 $p a r a m s_{j}$ 中的模数逐渐从 $q_{L}$ 降低到 $q_{0}$ .
对于每个 $j = L - 1 to 0$
1. 令 $d_{j} = d_{L}$ , $χ_{j} = χ_{L}$

这里的 $q_{L}$ 大概有 $(L + 1) \cdot μ$ 位, 其维数逐层降低到 $q_{0}$ 的 $μ$ 位. 此外, 每一层的 $d, χ$ 参数需要与 $L$ 层统一, 而维数 $n$ 则没有这个要求. 这是由于在 $q$ 变小时, 维数的减少不会影响方案的安全性, 毕竟当 $q$ 下降时, 维数的减小不会然破解变得容易.

$FHE . KeyGen ({p a r a m s_{j}})$ : 对于每个 $j = L to 0$ , 执行:
1. 执行 $s_{j} \leftarrow E . SecretKeyGen (p a r a m s s_{j})$ 和 $A_{j} \leftarrow E . PublicKeyGen (p a r a m s_{j}, s_{j})$
2. 令 $s_{j}^{'} \leftarrow s_{j} \otimes s_{j}$ .
3. 令 $s_{j}^{″} \leftarrow BitDecomp (s_{j}^{'}, q_{j})$ .
4. 令 $τ_{s_{j}^{″} \to s_{j - 1}} \leftarrow SwitchKeyGen (s_{j}^{″}, s_{j - 1})$ ³. (当 $j = L$ 时不执行该步骤)

实际上上述算法中, 我们就生成了每一层的公私钥, 并且做好了每一层的 $τ_{s_{j}^{″} \to s_{j - 1}}$ , 则一部分在BV11b中被称为计算密钥. 注意我们先前已经说过了, 作者比较激进, 这里直接就将张量积后的密文做了 $BitDecomp$ 再来生成密钥切换时的计算密钥, 那么对应的密文也要做 $Powerof 2$ 操作.

$FHE . Enc (p a r a m s, p k, m \in {0, 1})$ : 计算并输出 $E . Enc (A_{L}, m)$ .
$FHE . Dec (p a r a m s, s k, c)$ : 根据密钥的层数选择 $s_{j}$ , 计算并输出 $E . Dec (s_{j}, c)$ .

此处我们忽略了确定密文层数的参数来化简表示. 接下来我们演示同态计算. 同态计算中, 需要用到密钥切换过程, 该过程包括模数切换过程和维数切换过程, 我们将其统一为一个 $Refresh$ 过程, 首先要根据计算密钥的格式, 将乘法(或加法)得到的结果进行 $Powerof 2$ 操作, 然后依次进行模数切换和密钥切换, 总的来说是把一个$\mathbf s_j'=\mathbf{s}j\otimes\mathbf s_j $下得密文变为$ \mathbf s{j-1}$下得密文. 我们将整个模数切换过程形式化.

$FHE . Refresh (c, τ_{s_{j}^{″} \to s_{j - 1}, q_{j}, q_{j - 1}})$ :
1. 计算 $c_{1} \leftarrow Powerof 2 (c, q_{j})$
2. 计算 $c_{2} \leftarrow Scale (c_{1}, q_{j}, q_{j - 1}, 2)$
3. 计算并输出 $c_{3} \leftarrow SwitchKey (τ_{s_{j}^{″} \to s_{j - 1}}, c_{2}, q_{j - 1})$

最后我们补充完同态借助 $Refresh$ 完成的同态运算过程:

$FHE . Add (p k, c_{1}, c_{2})$ : 首先计算 $c_{3} = c_{1} + c_{2}$ , 再计算输出 $c_{4} = FHE . Refresh (c_{3}, q_{j}, q_{j - 1})$ .
$FHE . Mult (p k, c_{1}, c_{2})$ : 首先计算 $c_{3}$ , 即由 $c_{1}, c_{2}$ 所表示的多项式函数相乘得到的多项式函数对应的密文, 再计算并输出 $c_{4} = FHE . Refresh (c_{3}, q_{j}, q_{j - 1})$ .

这里要注意的是, 加法的密文后完全可以看做是 $s_{j}^{'} = s_{j} \otimes s_{j}$ 下的密文, 只需要令二次项表示的位为 $0$ 就可以了.

其他

在作者阅读完代数数论和RLWE的知识后, 将会带各位阅读Batching部分的操作, 该部分内容可以极大地提升本方案的效率, 也被CKKS方案借鉴. Bootstrapping和安全性证明也将在之后完成.

注释

Zvika Brakerski, Graig Gentry and Vindo Vaikuntanathan. Fully homomorphic encryption without bootstrapping. In Innovations in Theoretical Computer Science (ITCS'12), 2012. ↩︎
实际上LWE和RLWE的模数都不需要是素数, 而且后文中也没有提到是素数. 此处存疑. ↩︎
此处eprint上版本的原文中有笔误. ↩︎