本文中的数、向量、矩阵分别记为x、x、X，向量的内积记为 < v, u > ，I_k表示k阶单位矩阵，A^T表示矩阵A的转置，[k]表示集合$\{ 1, 2, \cdots, k\} $。对于概率分布D而言，$x \leftarrow D$表示$x $依概率分布D选取，对于集合S，$x \leftarrow S$表示$x $在集合S上均匀随机选取。$ ||\mathit{\boldsymbol{v}}|{|_\infty } $、$ ||\mathit{\boldsymbol{A}}|{|_\infty } $分别表示向量v及矩阵A中元素最大的量级。$\left\lfloor x \right\rfloor, \left\lceil x \right\rceil $($x \ge 0$)表示对数x向下和向上取整，${[x]_q} $表示$ x(\bmod q) $，$ {[\mathit{\boldsymbol{A}}]_q} $表示对矩阵A的每一个元素分别模q。规定${{\mathbb{Z}}_{q}}=(-q/2, q/2]\bigcap \mathbb{Z}$。

定义1 (LWE问题^[9])对于整数$q=q(n) $，向量$\mathit{\boldsymbol{s}}\in \mathbb{Z}_{q}^{n}$及一个${{\mathbb{Z}}_{q}}$上的误差分布$\chi =\chi (n)$，选取$\mathit{\boldsymbol{a}}\leftarrow \mathbb{Z}_{q}^{n}$及$x\leftarrow \chi $，输出$(\mathit{\boldsymbol{a}}, <\mathit{\boldsymbol{a}}, \mathit{\boldsymbol{s}}>+x)\in \mathbb{Z}_{q}^{n}\times {{\mathbb{Z}}_{q}}$，该分布记为${{A}_{\mathit{\boldsymbol{s}}, \chi }}$。$\text{LW}{{\text{E}}_{n, m, q, \chi }}$的判定问题为：以不可忽略的优势来区分m个来自${{A}_{\mathit{\boldsymbol{s}}, \chi }}$的取样和m个$\mathbb{Z}_{q}^{n}\times {{\mathbb{Z}}_{q}}$上的均匀随机取样。文献[9]在2005年证明了在量子归约下，LWE问题至少与worst-case的近似因子为$ \widetilde{O}(n/\alpha ) $的SVP、SIVP的变体一样困难，其中$\alpha $是LWE实例中与扰动分布的方差有关的参数。文献[10-11]分别给出了从GapSVP到LWE一个经典归约。

定义2  (B界分布^[12])对于一个定义在整数上的分布全体$ {{\left\{ {{\chi }_{n}} \right\}}_{n\in N}} $，如果$ \mathop {\Pr }\limits_{\mathit{\boldsymbol{e}} \leftarrow {\chi ^n}} [|\mathit{\boldsymbol{e}}| > B]$是可忽略的，则$ {{\left\{ {{\chi }_{n}} \right\}}_{n\in N}} $称为B界的。

定理1^[12]  设$ q=q(n)\in \mathbb{N} $为素数的幂或者为不同poly(n)大小的素数的乘积，$B \ge \omega ({\rm{log}}n)\sqrt n $。那么存在一个有效的取样B界分布χ，使得如果存在一个有效的算法解决参数为$ n, q, \chi $的一般情况的LWE困难问题，那么：

1) 存在一个有效的量子算法在n维格上解决$ {\rm{GapSV}}{{\rm{P}}_{\widetilde O(nq/B)}} $；

2) 如果$ q \ge \widetilde O({2^{n/2}}) $，那么存在一个有效的经典算法在n维格上解决${\rm{GapSV}}{{\rm{P}}_{\widetilde O(nq/B)}} $。

对于这两种情况，如果考虑以亚多项式的优势来区分，那么需要$B \ge \widetilde O(n)$，并且最后的近似因子比\widetilde O({n^{1.5}}q/B)略大。

本节利用BGV12的加密方案设计了一种变形的加密方案。加密的明文为矩阵，密文也为矩阵。因为密文的乘法运算是矩阵的乘法，所以密文的规模在运算后没有增大。又因为该加密方案也支持任意次密文加法运算，所以为BGN加密方案。

BGN加密方案由五元组(E.Setup, E.SecretKeygen, E.PublicKeygen, E.Enc, E.Enc, E.Dec)构成。

初始化阶段$ {\rm{E}}{\rm{.Setup(}}{{\rm{1}}^\lambda }{\rm{, }}{{\rm{1}}^\mu }{\rm{)}} $：适应性地选择μ比特的模q，及参数$ n = n(\lambda, \mu )$，$ m = \left\lceil {(2n + 1)\log q} \right\rceil $，$ \chi = \chi (\lambda, \mu ) $。

密钥生成算法E.SecretKeygen(1ⁿ)：选取 $\mathit{\boldsymbol{S}}\leftarrow \mathbb{Z}_{q}^{n\times m} $，输出。

公钥生成算法E.PublicKeygen(S)：选取$ \mathit{\boldsymbol{A}}\leftarrow \mathbb{Z}_{q}^{m\times n} $及$\mathit{\boldsymbol{X}}\leftarrow {{\chi }^{n\times n}}$，计算$\mathit{\boldsymbol{B}}={{[\mathit{\boldsymbol{SA}}+2\mathit{\boldsymbol{X}}]}_{q}}$。输出。

加密算法E.Enc(pk, M)：对于明文$\mathit{\boldsymbol{M}}\in {{\{0, 1\}}^{n\times n}}$，，选取$\mathit{\boldsymbol{R}}\in {{\{0, 1\}}^{n\times n}}$，并输出密文。

解密算法E.Dec(sk, C)：对于密文C，，令，然后输出${{m}_{(i, j)}}={{\left[{{\left[<{{\mathit{\boldsymbol{e}}}_{i}}, {{\mathit{\boldsymbol{s}}}_{j}}> \right]}_{q}} \right]}_{2}}$，这里e_i是E是的第i行，s_j是的第j列，$i, j\in [n]$。

注：解密算法中的右乘是多余的，仅在乘积密文的解密中会用到。

命题1  (正确性)设$q, n, m, |\chi |\le B$为上述加密方案E所需的参数，$\mathit{\boldsymbol{S}}\in \mathbb{Z}_{q}^{n\times m}$为任意矩阵，$\mathit{\boldsymbol{M}}\in {{\{0, 1\}}^{n\times n}}$。令，$\mathit{\boldsymbol{C}}\leftarrow \rm{E}\rm{.Enc}(\rm{pk}, \mathit{\boldsymbol{M}})$，如果${{[\mathit{\boldsymbol{M}}+2\mathit{\boldsymbol{XR}}]}_{q}}=\mathit{\boldsymbol{M}}+2\mathit{\boldsymbol{XR}}$，那么$\rm{E}\rm{.Decs}(\rm{sk}, \mathit{\boldsymbol{C}})=\mathit{\boldsymbol{M}}$。

证明：由定义可知，因而解密正确。

引理1  (安全性)^[5]：设参数$m, n, q, \chi $，使得${\rm{LWE}}_{m, n, q, \chi }$成立，那么对任意的$\mathit{\boldsymbol{M}}\in \mathbb{Z}_{2}^{n\times n}$，如果，$\mathit{\boldsymbol{R}}\in {{\{0, 1\}}^{n\times n}}$，则$(\mathit{\boldsymbol{BR}}, \mathit{\boldsymbol{AR}})$与$\mathbb{Z}_{q}^{m\times n}\times \mathbb{Z}_{q}^{m\times n}$上的均匀分布计算不可区分。

设密文：

则：

1) 加法

对于适合的参数有：

是${{[{{\mathit{\boldsymbol{M}}}_{1}}+{{\mathit{\boldsymbol{M}}}_{2}}]}_{2}}$的密文。

2) 乘法

规定密文乘积为${{\mathit{\boldsymbol{C}}}^{*}}={{\mathit{\boldsymbol{C}}}_{1}}\mathit{\boldsymbol{C}}_{2}^{{\rm{T}}}\ {\rm{mod}}q$。因此

式中，${{\mathit{\boldsymbol{X}}}^{*}}=2{{\mathit{\boldsymbol{M}}}_{1}}\mathit{\boldsymbol{R}}_{2}^{\rm{T}}\mathit{\boldsymbol{X}}_{2}^{\rm{T}}+2{{\mathit{\boldsymbol{X}}}_{1}}{{\mathit{\boldsymbol{R}}}_{1}}\mathit{\boldsymbol{M}}_{2}^{\rm{T}}+4{{\mathit{\boldsymbol{X}}}_{1}}{{\mathit{\boldsymbol{R}}}_{1}}\mathit{\boldsymbol{R}}_{2}^{\rm{T}}\mathit{\boldsymbol{X}}_{2}^{\rm{T}}$，那么对于适合的参数${{\mathit{\boldsymbol{C}}}^{*}}={{\mathit{\boldsymbol{C}}}_{1}}\mathit{\boldsymbol{C}}_{2}^{\rm{T}}\ \bmod q$为${{[{{\mathit{\boldsymbol{M}}}_{1}}\mathit{\boldsymbol{M}}_{2}^{\rm{T}}]}_{2}}$的密文。

定理2 令n为安全参数，任意的$c=c(n)>0$。设$q>6{{n}^{2c+6}}$为素数，$m=\left\lceil (2n+1)\log q \right\rceil $，$B={{n}^{\frac{3}{2}}}$。那么上述加密方案支持密文的${{n}^{c}}$次加法和一次乘法运算。

证明：先考虑密文C为$ l\le {{n}^{c}} $个密文的和，记。

因为

所以${{\left[\sum\limits_{i=1}^{l}{{{\mathit{\boldsymbol{M}}}_{i}}}+2\sum\limits_{i=1}^{l}{{{\mathit{\boldsymbol{X}}}_{i}}{{\mathit{\boldsymbol{R}}}_{i}}} \right]}_{q}}=\sum\limits_{i=1}^{l}{{{\mathit{\boldsymbol{M}}}_{i}}}+2\sum\limits_{i=1}^{l}{{{\mathit{\boldsymbol{X}}}_{i}}{{\mathit{\boldsymbol{R}}}_{i}}}$，故$ {\rm{E}}{\rm{.Dec}}({\rm{sk}}, \mathit{\boldsymbol{C}})={{\left[\sum\limits_{i=1}^{l}{{{\mathit{\boldsymbol{M}}}_{i}}} \right]}_{2}} $。

下面考虑密文C′为两个密文的乘积，这两个密文分别为$ {{l}_{1}}, {{l}_{2}} $个密文的和，其中$ {{l}_{1}}+{{l}_{2}}\le {{n}^{c}} $，记。

因为：

所以$ {\rm{E}}{\rm{.Dec}}({\rm{sk}}, C') = {\left[{\left( {\sum\limits_{i = 1}^{{l_1}} {{\mathit{\boldsymbol{M}}_i}} } \right){{\left( {\sum\limits_{i = 1}^{{l_2}} {{\mathit{\boldsymbol{M}}_i}} } \right)}^{\rm{T}}}} \right]_2} $。

注：本方案与GHV10^[3]相比较，对于任意的$c = c(n) > 0$，仅要求$ q > 6{n^{2c + 6}} $为素数，而GHV10要求$q > {2^{20}}{(c + 4)^3}{n^{3c + 4}}{\rm{lo}}{{\rm{g}}^5}n$为素数。这意味着如果q的范围扩大，则能支持比$c = c(n) > 0$更大的运算。

本节首先介绍密钥同态，然后构造门限加密方案，最后证明该方案能抵抗密钥泄露攻击。

假设密钥, 选取$\mathit{\boldsymbol{A}}\leftarrow \mathbb{Z}_{q}^{m\times n}$, ${{\mathit{\boldsymbol{X}}}_{i}}\leftarrow {{\chi }^{n\times n}}$，令：

那么，$i = 1, 2$。因为：

所以得到了对应于结合密钥的结合公钥，这就是密钥同态。

类似于文献[8]，本文也假设存在一个可信第三方F，F计算结合公钥、密钥，然后把计算后的结果发送给各个参与者(假设共k个参与者)，并同时保证密钥的安全性。为了保证语义安全，本文同样加入了干扰噪音。

密钥生成算法TE.SecretKeygen(1ⁿ)：取${{\mathit{\boldsymbol{S}}}_{i}}\leftarrow \mathbb{Z}_{q}^{n\times m}$，输出, $ i\in [k] $。

公钥生成算法TE.PublicKeygen(S)：取$\mathit{\boldsymbol{A}}\leftarrow \mathbb{Z}_{q}^{m\times n}$，${{\mathit{\boldsymbol{X}}}_{i}}\leftarrow {{\chi }^{n\times n}}$，计算${{\mathit{\boldsymbol{B}}}_{i}}={{[{{\mathit{\boldsymbol{S}}}_{i}}\mathit{\boldsymbol{A}}+2{{\mathit{\boldsymbol{X}}}_{i}}]}_{q}}$，输出，$ i\in [k] $。

当F从k个参与者中接收到$ {\rm{p}}{{\rm{k}}_i} $后诚实地计算$\mathit{\boldsymbol{B}} = \sum\limits_{i = 1}^k {{\mathit{\boldsymbol{B}}_i}} $。故结合公钥为：。

加密算法TE.Enc(pk，M)：对于明文$\mathit{\boldsymbol{M}} \in {\{ 0, 1\} ^{n \times n}}$及公钥，均匀取$\mathit{\boldsymbol{R}} \in {\{ 0, 1\} ^{n \times n}}$及干扰噪音${\mathit{\boldsymbol{X}}^*}$，输出密文。

解密算法TE.Dec(sk, C)：各参与者把解密共享发送给F，F诚实地计算。并输出明文M。

正确性可由以下运算得出。

可以仿照文献[8]的游戏来证明结合密钥的安全性，即攻击者不能以显著优势区分在诚实公钥下的加密密文与均匀选取的假密文，证明省略。

本文基于BGV12，设计了一种基于LWE的BGN加密方案。与GHV10比较，有较好的参数规模，即对于任意的$c = c(n) > 0$，GHV10要求$q > {2^{20}}{(c + 4)^3}{n^{3c + 4}}{\rm{lo}}{{\rm{g}}^5}n$为素数，而本文仅要求$ q > 6{n^{2c + 6}} $为素数。与BGV12比较，因为不再需要用到密钥交换、模转换等技术，一次乘法同态运算更高效。与ZXJXZ14类似，将BGN加密也扩展成一种门限加密方案，允许所有参与者共同解密一个密文而没有泄露明文的任何信息，并且能抵抗密钥泄露攻击。最后值得注意的是，类似于GHV10中的扩展及应用，同样可以把本文的加密方案扩展成身份基加密(也需要利用陷门T)、Two-Out-of-Two加密等。

本文得到信息安全国家重点实验室开放课题(2016-MS-10)的资助，在此表示感谢。