CIS 2018回顾

符号说明

本文中, 我们采用方括号+下标的方式来表示向量中的具体某一位. 例如向量$\mathbf{s}$的第$i$位用$\mathbf{s}[i]$来表示. 我们有时候会用下标0来表示不存在的下标, 例如$h_i$可以用$h_{i,0}$来表示, 这样做的好处是, 我们不用显式地提及$h_i$, 而是用$h_{i,j}$就可以表示所有的$h_{i,j\ne 0}$和$h_i$来避免描述地冗长.

原文中的安全参数采用的是$\kappa$, 由于这个字母容易和$k$混淆, 且为了与我其他博文统一, 我修改为了$\lambda$.

简介

假设我们采用的LWE的噪声为偶数, 即具有$2\mathbf{e}$的形式, 则最终我们得到的加密密文具有$(\mathbf{a},b=⟨\mathbf{a},\mathbf{s}⟩+2e+m)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$的形式, 其中$m\in \{0,1\}$是我们加密的密文. 在有了这种形式的密文后, 通过$b-⟨\mathbf{a},\mathbf{s}⟩=2e+m$, 再模上2方可解除$m$.

如果我们将解密的过程看作是一个函数, 即对于$\mathbf{a}$来说, $f_{\mathbf{a},b}(\mathbf{x})=b-⟨\mathbf{a},\mathbf{x}⟩\mathrm{mod}q$, 那么当我们输入正确的密钥$\mathbf{s}$时, 最终计算出的结果再模上2就是解密的结果. 如果$\mathbf{a}$具有$n$维, 我们有 $$f_{\mathbf{a},b}(\mathbf{x})=b-\sum _{i=1}^n\mathbf{a}[i]\cdot \mathbf{s}[i]$$ 先假设另一个明文$m^{\prime }\in \{0,1\}$采用$({\mathbf{a}}^{\prime },b^{\prime }=⟨{\mathbf{a}}^{\prime },s⟩+2e^{\prime }+m^{\prime })$进行加密, 那么很显然的, $f_{{\mathbf{a}}^{\prime },b^{\prime }}(\mathbf{x})$可以用来描述其解密过程. 我们发现, 如果将两个函数加或乘在一起, 传入正确的密文后, 我们将会得到原先密文的加或乘的加密. 当然, 这里的加是指比特异或或者$GF(2)$上的加法. 观察 $$\begin{array}{rl}{f}_{\mathbf{a},b}(\mathbf{x})\cdot f_{{\mathbf{a}}^{\prime },b^{\prime }}(\mathbf{x})& =(b-\sum \mathbf{a}[i]\cdot \mathbf{x}[i])\cdot (b^{\prime }-\sum {\mathbf{a}}^{\prime }[i]\cdot \mathbf{x}[i])\\ & =h_0+\sum h_i\cdot \mathbf{x}[i]+\sum h_{i,j}\cdot \mathbf{x}[i]\mathbf{x}[j]\end{array}$$ 这里传入参数$\mathbf{s}$后, 就有 $$\begin{array}{rl}{f}_{\mathbf{a},b}(\mathbf{s})\cdot f_{{\mathbf{a}}^{\prime },b^{\prime }}(\mathbf{s})& =(2e+m)\cdot (2e^{\prime }+m‘)\\ & =4e{e}^{\prime }+2e^{\prime }m+2e{m}^{\prime }+m{m}^{\prime }\\ & =2(2e{e}^{\prime }+e^{\prime }m+e{m}^{\prime })+m{m}^{\prime }\end{array}$$ 最终模上2后确实可以得到$m{m}^{\prime }$. 类似的加法我们也可以具体验证.

但是这里的乘法也就带来了一个问题, 描述我们多项式的系数个数, 由原先的$O(n)$个变成了$O(n^2)$个—-多了那些二次项的系数. 如果我们反复的进行乘法, 那么进行$L$次乘法, 描述多项式的系数个数就会变成$O(n^{2^L})$, 这显然不是我们想要的.

解决这一问题的办法是, 让我们同态加密的加密方, 用一个新的密钥$\mathbf{t}$将原先密钥$\mathbf{s}$的所有一次项$\mathbf{s}[i]$二次项$\mathbf{s}[i]\mathbf{s}[j]$都加密起来, 即生成密文$({\mathbf{a}}_{i,j},b_{i,j})$满足 $$b_{i,j}=⟨{\mathbf{a}}_{i,j},\mathbf{t}⟩+2e_{i,j}+\mathbf{s}[i]\mathbf{s}[j]\approx ⟨a_{i,j},\mathbf{t}⟩+\mathbf{s}[i]\mathbf{s}[j]$$ 如果我们将以上密文改写成解密多项式并带入到$f_{\mathbf{a},b}(\mathbf{x})\cdot f_{{\mathbf{a}}^{\prime },b^{\prime }}(\mathbf{x})$中, 我们将会得到一个全新的多项式函数 $$g(\mathbf{x})=h_0+\sum h_i(b_i-⟨{\mathbf{a}}_i,\mathbf{x}))+\sum h_{i,j}(b_{i,j}-⟨{\mathbf{a}}_{i,j},\mathbf{x}⟩)$$ 这个多项式满足 $$\begin{array}{rl}g(\mathbf{t})& =h_0+\sum h_i(b_i-⟨{\mathbf{a}}_i,\mathbf{t}))+\sum h_{i,j}(b_{i,j}-⟨{\mathbf{a}}_{i,j},\mathbf{t}⟩)\\ & =h_0+\sum h_i\cdot \mathbf{s}[i]+\sum h_{i,j}\cdot \mathbf{s}[i]\mathbf{s}[j]\end{array}$$ 其最终模2的结果也就是$m{m}^{\prime }$.

如果我们还想多进行一层的乘法运算怎么办? 由于$g$和$f_{\mathbf{a},b}$具有类似的形式, 因此我们也可以将$\mathbf{t}$的一次项和二次项用另一个新的密钥${\mathbf{t}}^{\prime }$进行加密, 再交由同态运算方处理即可—-类似的过程再噪声没有过大的情况下可以一直持续下去.

当然, 这里我们保持了噪声是偶数的性质了吗? 这一点毋庸置疑, 因为说明所有的噪声都是偶数, 无论如何也不可能凑出奇数的噪声来.

潜在的问题

上面的方案由一个潜在的问题. $h_{i,j}$不是标准的LWE生成的项, 我们也没有理由假设它是一个较小的值, 而实际上它们确实可以很大. 当这些项很大的时候, 极有可能导致$h_{i,j}\cdot (b_{i,j}-⟨{\mathbf{a}}_{i,j},\mathbf{t}⟩)\not\approx h_{i,j}\cdot \mathbf{s}[i]\mathbf{s}[j]$.为了避免这一情况的发生, 我们需要让$h_{i,j}$都不要太大. 我们采用的办法就是我们用过的"BitDecomp"大法, 即用二进制来表示$h_{i,j}$, 将其表示为$h_{i,j}=\sum _{i=0}^{\lfloor \log q\rfloor }{2}^{\tau }\cdot h_{i,j,\tau }$. 到这里看起来也许就不那么美好了, 因此每项参数的意思需要你牢记, 这样你才能继续读下去.

接下来更令人费解的是, 我们要构造一个是密文的形式, 但是又不是对任何东西的加密的一种"密文", 令 $$b_{i,j,\tau }=⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩+2e_{i,j,\tau }+2^{\tau }\mathbf{s}[i]\mathbf{s}[j]\approx ⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩+2^{\tau }\mathbf{s}[i]\mathbf{s}[j]$$ 这里像是将${\mathbf{a}}_{i,j},b_{i,j}$按照$h_{i,j}$的方式拆开, 但是实际上是我们为每一个$2^{\tau }\mathbf{s}[i]\mathbf{s}[j]$单独准备的"密文", 但是他们并不是对$2^{\tau }\mathbf{s}[i]\mathbf{s}[j]$的加密, 因为我们的加密方案只会加密1 bit, 在$\tau \ge 1$的时候, 整个$2^{\tau }\mathbf{s}[i]\mathbf{s}[j]$会在模2的时候被一同模掉. 不过好在是$b_{i,j,\tau }-⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩\approx 2^{\tau }\cdot \mathbf{s}[i]\mathbf{s}[j]$还是成立的.

但是这样做也有一个好处, 就是我们可以利用对$h_{i,j}$的拆分, 用以上的这组"密文"来表示$h_{i,j}$, 我们有 $$h_{i,j}\cdot \mathbf{s}[i]\mathbf{s}[j]=\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,j,\tau }{2}^{\tau }\mathbf{s}[i]\mathbf{s}[j]\approx \sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,j,\tau }(b_{i,j,\tau }-⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩)$$ 这个时候$h_{i,j,\tau }$较小, $h_{i,j,\tau }\cdot (b_{i,j,\tau }-⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩)\not\approx h_{i,j,\tau }\cdot \mathbf{s}[i]\mathbf{s}[j]$的情况就不会出现了, 因此整个等式的$\approx$也就能得到保持.

Bootstrapping准备工作

回想一下每进行一次乘法的噪声增长. $$\begin{array}{rl}{f}_{\mathbf{a},b}(\mathbf{s})\cdot f_{{\mathbf{a}}^{\prime },b^{\prime }}(\mathbf{s})& =(2e+m)\cdot (2e^{\prime }+m^{\prime })\\ & =4e{e}^{\prime }+2e^{\prime }m+2e{m}^{\prime }+m{m}^{\prime }\\ & =2(2e{e}^{\prime }+e^{\prime }m+e{m}^{\prime })+m{m}^{\prime }\end{array}$$ 从$e{e}^{\prime }$项可以看出, 每进行一次乘法运算, 噪声都从$E$变成了$E^2$, 同GSW方案一样, 我们的噪声是按双对数的方式进行增长的. 即在进行$L$层乘法之后, 噪声至少变成了$E^{2^L}$. 我们的模数¹$q$的选择只能是$n$的不能达到双指数而只能达到$2^{n^{ϵ}}$(其中$ϵ$为常数), 要使得噪声不超过$O(q)=O(2^{n^{ϵ}})$, 我们的$L$只能选择在$\text{polylog }n$. 但是, LWE解密电路的深度是$max(n,\log q)$, 也就是说, 我们的的方案不能支持我们的解密电路! 也就无法实现Bootstrapping来达到FHE!

此时我们的办法是, 用大的模数和维数来进行Bootstrapping, 而用小的模数和维数来进行同态运算. 这样, 我们同态运算过程中解密电路的深度就不会太深, 能够被模数和维数大的Bootstrapping过程所支持. 现在我们来介绍如何从参数$(n,\log q)$转换到$(k,\log p)$². 其中, $n=k^c,p=\text{poly}(k)$, 由于$q=2^{n^{ϵ}}$, 我们就可以用大参数做约$D=n^{ϵ}=k^{c\cdot ϵ}$层同态运算, 成功地将小参数下地解密电路包括进来.

我们首先可以发现, 在我们进行一次乘法, 将密钥从$\mathbf{s}$切换到$\mathbf{t}$时, 我们并不以一定需要$\mathbf{t}$与$\mathbf{s}$的维数相同, 通过选择维数更小的$\mathbf{t}$我们就可以降低维数. 降低模数时, 采用的思想是近似逼近. 假设在模$p$时我们用如下的方式来生成"密文" $${\hat{b}}_{i,j,\tau }=⟨{\hat{\mathbf{a}}}_{i,j,\tau },\mathbf{t}⟩+e+\lfloor \frac{p}{q}\cdot 2^{\tau }\cdot \mathbf{s}[i]\rceil$$ 其中$({\hat{\mathbf{a}}}_{i,j,\tau },{\hat{b}}_{i,j,\tau })\in {\mathbb{Z}}_p^k\times {\mathbb{Z}}_p$是按照LWE加密生成的, 则 $$2^{\tau }\cdot \mathbf{s}[i]\mathbf{s}[j]\approx \frac{q}{p}\cdot (b_{i,j,\tau }-⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩)$$ 即可大致还原出$2^{\tau }\cdot \mathbf{s}[i]\mathbf{s}[j]$. 我们用$\frac{q}{p}\cdot ({\hat{b}}_{i,j,\tau }-⟨{\hat{\mathbf{a}}}_{i,j,\tau },\mathbf{t}⟩)$来代替之前的$b_{i,j,\tau }-⟨{\mathbf{a}}_{i,j,\tau },\mathbf{t}⟩$用于构造新的一次多项式函数, 使得新的多项式模数变得更小了. 值得一提的是, 这里需要引入**稀疏子集和假设**. 也许你看到这里又迷糊了, 这里又还原不出$2^{\tau }\cdot \mathbf{s}[i]\mathbf{s}[j]$, 那又有意义呢? 单独来看是没有什么意义, 但它的噪声是偶数的, 所有的这样的东西拼凑在一起最终可以帮助我们解密出同态运算的结果.

到此为止, 我们就可以将切换到$\mathbf{t}$进行计算时的模数和维数都变小了.

BV11b中的SWHE同态加密方案

这一部分将分为两个小部分介绍, 第一步就是不做模数切换和维数切换的基础同态方案$\mathsf{SH}$. 第二部分就是采用模数切换和维数切换的技术, 将$\mathsf{SH}$转换成一个可以加入Bootstrapping的方案$\mathsf{BTS}$, 在$\mathsf{BTS}$的基础上加上Bootstrapping技术就可以得到一个FHE方案.

即使是本节内容大多已经在前面介绍过了, 这里只是将其形式化, 并对整个方案的流程做一定的解读.

密钥生成、加密、解密

第一步和GSW一样, 都要有一个Setup, 之所以需要这个过程是因为我们要选择需要做同态的层数. 注意, 这一步在原文中是没有显式地写出来地, 但是它确实也这一做了.

• $\mathsf{SH}\mathsf{.}\mathsf{Setup}(1^L,1^{\lambda })$: 用$\lambda$表示安全参数, $L$表示同态运算的层数, 选择参数$m,n,q$满足$n=\text{poly}(\lambda )$, $m\ge n\log q+2\lambda$, $L\approx ϵ\log n$和$q$为奇数且$q\in [2^{n^{ϵ}},2\cdot 2^{n^{ϵ}})$, 其中$ϵ\in (0,1)$为常数. 选择${\mathbb{Z}}_q$上的噪声分布$\chi$.

这些参数的选择大多是为了保证基于的LWE加密的安全性. 如果不关注实现的细节和安全性规约, 可以忽略大部分的参数选择. 需要记住的选择规则是: $q$可以是$n$的超指数的, 但不能达到$n$的双指数, 且$m$大约是$n\log q$.

接下来的$\mathsf{KeyGen}$看起来会有一些复杂, 因为我们把每一层的密钥的一次和二次项用下一层密钥加密后的结果写在了一起, 作为计算密钥(Evaluation Key), 但是他们的本质实际上读者已经见过了

• $\mathsf{SH}\mathsf{.}\mathsf{KeyGen}(1^{\lambda })$: 选择$L+1$个向量${\mathbf{s}}_0,\cdots ,{\mathbf{s}}_L\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q^n$, 对于所有的$\ell \in [L],0\le i\le j\le n$和$\tau \in \{0,\cdots ,\lfloor \log q\rfloor \}$计算

  $${\psi }_{\ell ,i,j,\tau }:=({\mathbf{a}}_{\ell ,i,j,\tau },b_{\ell ,i,j,\tau }:=⟨{\mathbf{a}}_{\ell ,i,j,\tau },\mathbf{s}⟩+2\cdot e_{\ell ,i,j,\tau }+2^{\tau }\cdot {\mathbf{s}}_{\ell -1}\cdot {\mathbf{s}}_{\ell -1}[j])\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$$

  同时选择$\mathbf{A}\leftarrow {\mathbb{Z}}_q^{m\times n}$和$\mathbf{e}\leftarrow {\chi }^m$, 计算$\mathbf{b}:=\mathbf{A}{\mathbf{s}}_0+2\mathbf{e}$.

  输出公钥$sk=s_L$, 计算密钥$evk=\mathrm{\Psi }=\{{\psi }_{\ell ,i,j,\tau }{\}}_{\ell \in [L],0\le i\le j\le n,\tau \in \{0,\cdots ,\lfloor \log q\rfloor \}}$和私钥$pk=(\mathbf{A},\mathbf{b})$.

计算密钥这一长串的东西, 读者在前面已经见过很多次了, 应该比较熟悉了. 唯一多了的参数是$\ell$是代表当前同态的层.

• $\mathsf{SH}\mathsf{.}\mathsf{Enc}\mathsf{(}\mathsf{pk}\mathsf{,}\mathsf{m}\mathsf{)}$: 选择$\mathbf{r}\leftarrow \{0,1{\}}^m$, 计算$\mathbf{v}:={\mathbf{A}}^T\mathbf{r}$和$w:={\mathbf{b}}^T\mathbf{r}+m$, 输出密文$c:=((\mathbf{v},w),0)$.

注意这里最后的$0$代表当前同态(乘法)运算的层数. 同时由于噪声始终是偶数累计的, 因此模2仍然可以消除噪声.

在做完同态运算后, 我们得到的是第$L$层的密文, 即密文的格式是$c=((\mathbf{v},w),L)$.

• $\mathsf{SH}\mathsf{.}\mathsf{Dec}\mathsf{(}\mathsf{sk}\mathsf{,}\mathsf{c}\mathsf{)}$: 输出$((w-⟨\mathbf{v},{\mathbf{s}}_L⟩)\mathrm{mod}q)\mathrm{mod}2$

这里注意$\mathbf{v}$连同$w$就构成了最终解密多项式函数的描述, $(w-⟨\mathbf{v},{\mathbf{s}}_L⟩)\mathrm{mod}q$就相当于是求解密多项式在${\mathbf{s}}_L$点的值.

同态运算

加法的同态比较简单, 将多个同一层的密文相加即可.

• 加法门: 对于n个密文$\{c_i=(({\mathbf{v}}_i,w_i),\ell ){\}}_{i\in [n]}$做加法同态, 计算和输出 $$c_{+}=(({\mathbf{v}}_{+},w_{+}),\ell )=((\sum _i{\mathbf{v}}_i,\sum _i{w}_i),\ell ).$$

解密的正确性留给读者. 可以看出, 加法同态不消耗同态层数, 因此我们的同态层数$L$是指乘法层数.

对于乘法来说, 我们需要用到前面介绍的技术.

• 乘法门: 对于两个同层的乘法密文$c=((\mathbf{v},w),\ell )$和$c^{\prime }=(({\mathbf{v}}^{\prime },w^{\prime }),\ell )$, 计算 $$\varphi (\mathbf{x})=(w-⟨\mathbf{v},\mathbf{x}⟩)(w^{\prime }-⟨{\mathbf{v}}^{\prime },\mathbf{x}⟩)=\sum _{0\le i\le j\le n}{h}_{i,j}\cdot \mathbf{x}[i]\mathbf{x}[j]$$ 令$h_{i,j}=\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,j,\tau }\cdot 2^{\tau }$, 并带入$evk=\mathrm{\Psi }$, 得到 $${\mathbf{v}}_{\times }=\sum _{\begin{array}{rl}0\le i\le & j\le n\\ tau\in \{0,\cdots & ,\lfloor \log q\rfloor \}\end{array}}{h}_{i,j,\tau }\cdot {\mathbf{a}}_{\ell +1,i,j,\tau }$$ 和 $$w_{\times }=\sum _{\begin{array}{rl}0\le i\le & j\le n\\ tau\in \{0,\cdots & ,\lfloor \log q\rfloor \}\end{array}}{h}_{i,j,\tau }\cdot b_{\ell +1,i,j,\tau }$$ 最终输出$(({\mathbf{v}}_{\times },w_{\times }),\ell +1)$.

注意$\sum$记号处发扬了我们在符号说明处的关于下标的说明, 实际上其内容包括常数项$h_0=w{w}^{\prime }$, 一次项(系数为$h_{i\ne 0,j=0}$)和二次项(系数为$h_{i\ne 0,j\ne 0}$). 同样这里的同态计算验证留作.

将加法门和乘法门的Eval方式结合起来, 我们就可以得到

• $\mathsf{SH}\mathsf{.}\mathsf{Eval}(evk,f,c_1,\cdots ,c_t)$: 采用加法门和乘法门Eval的方式输出最终运算结果.

要使得结果正确, $f$点电路必须是我们支持的电路, 必须是一个加法乘法交替的电路, 第$\ell$层的乘法密文的输出只能通向$\ell +1$层的乘法. 如果不考虑深度限制, 实际上所有的布尔电路都可以转化为这一的电路, 但是考虑到深度限制, 我们还有工作要做. 到这里, SWHE方案就算介绍完了, 采用该方案可以做到$n$的对数多项式(polylog)层的同态运算.

BV11b中的FHE方案

我们用$\mathsf{BTS}$来表示我们的可以加入Bootstrapping的方案, 该方案需要用到$\mathsf{SH}$方案的内容, 阅读这一部分, 请确保对前面知识的熟悉. 为了使我们的方案支持Bootstrapping, 我们必须降低解密电路的深度, 我们使用的方法是用维数切换和模数切换, 将密文的模数和维数变得更小.

• $\mathsf{BTS}\mathsf{.}\mathsf{Setup}(1^L,1^{\lambda })$: 用$\lambda$表示安全参数, $L$表示同态运算的层数, 选择参数$m,n,q$满足$n=\text{poly}(\lambda )$, $m\ge n\log q+2\lambda$, $L\approx ϵ\log n$和$q$为奇数且$q\in [2^{n^{ϵ}},2\cdot 2^{n^{ϵ}})$, 其中$ϵ\in (0,1)$为常数. 选择${\mathbb{Z}}_q$上的噪声分布$\chi$. 选择${\mathbb{Z}}_p$上的噪声分布$\hat{\chi }$.

$\mathsf{Setup}$是和$\mathsf{SH}$方案是一样的, 实际上我们$\mathsf{SH}$中参数的设定就是为了方便$\mathsf{BTS}$中的方案描述. 来自[BV11b]作者的建议: 在阅读时可以带入参数$k=\lambda ,n=k^4,q\approx \sqrt{n},L=1/3\log n=4/3\log k,p=(n^2\log n)\cdot \text{poly}(k),m=O(n\log q)$以及$n$-bounded的$\chi$和$k$-bounded的$\hat{\chi }$进行理解.

• $\mathsf{BTS}\mathsf{.}\mathsf{KeyGen}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$: 调用$\mathsf{SH}\mathsf{.}\mathsf{KeyGen}(1^{\lambda })$得到${\mathbf{s}}_L,\mathrm{\Psi },(\mathbf{A},\mathbf{b})$. 生成短的私钥$\hat{\mathbf{s}}\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p^k$并计算对应于这个短私钥的计算密钥, 即对于所有的$i\in [n],\tau \in \{0,\cdots ,\lfloor \log q\rfloor \}$, 生成${\hat{\mathbf{a}}}_{i,\tau }\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p^k,\hat{e}\stackrel{\$}{\leftarrow }\hat{\chi }$ 并计算

  $${\hat{b}}_{i,\tau }:=⟨{\hat{\mathbf{a}}}_{i,\tau },\hat{\mathbf{s}}⟩+{\hat{e}}_{i,\tau }+\lfloor \frac{p}{q}\cdot (2^{\tau }\cdot {\mathbf{s}}_L[i])\rceil \mathrm{mod}p$$

  记${\hat{\psi }}_{i,\tau }:=({\hat{\mathbf{a}}}_{i,\tau },{\hat{b}}_{i,\tau })\in {\mathbb{Z}}_p^k\times {\mathbb{Z}}_p$和$\hat{\mathrm{\Psi }}=\{{\hat{\psi }}_{i,\tau }{\}}_{i\in [n],\tau \in \{0,\cdots ,\lfloor \log q\rfloor \}}$.

  最终输出公钥$pk=(\mathbf{A},\mathbf{b})$, 私钥$sk=\hat{\mathbf{s}}$, 计算密钥$evk=\{\mathrm{\Psi },\hat{\mathrm{\Psi }}\}$.

实际上可以看出, 我们仍然需要借用原先方案的密钥. 原因是我们在做同态运算的时候, 接收到的输入是大密文, 而最后输出必须是小密文. 我们要求大密文和小密文的解密结果是一样的, 但是小密文的解密电路却更浅. 因此, 我们首先需要调用原先的$\mathsf{SH}\mathsf{.}\mathsf{Eval}$, 得到计算结果后, 再将密文变成小密文. 因此我们的加密算法, 应当和$\mathsf{SH}\mathsf{.}\mathsf{Enc}$相同:

• $\mathsf{BTS}\mathsf{.}\mathsf{Enc}(pk,m)$: 输出$\mathsf{SH}\mathsf{.}\mathsf{Enc}(pk,m)$.

具体的计算过程:

• $\mathsf{BTS}\mathsf{.}\mathsf{Eval}(evk,f,c_1,\cdots ,c_t)$: 计算$c_f\leftarrow \mathsf{SH}\mathsf{.}\mathsf{Eval}(\mathrm{\Psi },f,c_1,\cdots ,c_t)$. 记$c_f=((\mathbf{v},w),L)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q\times \{L\}$. 考虑多项式函数

  $$\varphi (\mathbf{x}):=\frac{p}{q}\cdot (\frac{q+1}{p}\cdot (w-⟨\mathbf{v},\mathbf{x}⟩))\mathrm{mod}p$$

  按照之前的方式将其系数整理为$h_0,\cdots ,h_n\in {\mathbb{Z}}_q$的形式, 即

  $$\varphi (\mathbf{x})=\sum _{i=0}^n{h}_i\cdot (\frac{p}{q}\cdot \mathbf{x}[i])$$

  再将$h_i$按照二进制展开, 得到

  $$\varphi (\mathbf{x})=\sum _{i=0}^n\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,\tau }\cdot (\frac{p}{q}\cdot 2^{\tau }\cdot \mathbf{x}[i])$$

  采用$\hat{\mathrm{\Psi }}$中的密钥来替换上式中的$\frac{p}{q}\cdot (2^{\tau }\cdot {\mathbf{s}}_L[i])$可以得到一个新的一次多项式函数, 记常数项为$\hat{w}$, 一次项系数向量为$\hat{\mathbf{v}}$则

  $$\begin{array}{r}\hat{\mathbf{v}}:=2\cdot \sum _{i=0}^n\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,\tau }\cdot {\hat{\mathbf{a}}}_{i,\tau }\mathrm{mod}p\in {\mathbb{Z}}_p^k\hat{w}:=2\cdot \sum _{i=0}^n\sum _{\tau =0}^{\lfloor \log q\rfloor }{h}_{i,\tau }\cdot {\hat{b}}_{i,\tau }\mathrm{mod}q\in {\mathbb{Z}}_q\end{array}$$

  最后输出密文$\hat{c}=(\hat{\mathbf{v}},\hat{w})$.

最后密文确实是小密文的格式, 因此我们的解密需要按照小密文的格式进行解密:

• $\mathsf{BTS}\mathsf{.}\mathsf{Dec}(sk=\hat{\mathbf{s}},\hat{c})$: 计算并输出 $$m^{\ast }:=((\hat{w}-⟨\hat{\mathbf{v}},\hat{\mathbf{s}}⟩)\mathrm{mod}q)\mathrm{mod}2$$

这里仍然有一个问题, 就是要验证经过大密钥转换后的小密钥用$\mathsf{BTS}\mathsf{.}\mathsf{Dec}$解密的结果与大密钥用$\mathsf{SH}\mathsf{.}\mathsf{Dec}$解密出的结果相同, 其基本思想已经在本文中有所体现, 具体的验证过程也可以参考[BV11b]论文.

注释