0 引言

在RSA(Rivest, Shamir, Adelman)公钥密码系统提出后不久，人们就提出了全同态加密(Fully Homomorphic Encryption, FHE)体制的思想^[1]。在全同态加密体制中，有Dec(f(Enc(μ₁), Enc(μ₂), …, Enc(μ_k)))=f(μ₁, μ₂, …, μ_k)，其中f为任意函数/电路。在分级全同态加密(leveled FHE)体制中，系统参数不仅依赖于安全参数λ还依赖于电路深度L∈Z⁺。借助于全同态加密体制，人们可把计算外包给不可信的服务器，而不必担心个人隐私泄露问题。

2009年Gentry^[2]基于格理论构造了第一个全同态加密方案。2011年Brakerski等^[3]基于环上带误差学习(ring Learning With Errors, ring-LWE)问题^[4]构造了一个全同态加密方案；Brakerski等^[5]基于LWE问题^[6]又构造了一个全同态加密方案。2012年Brakerski等^[7]基于环上LWE问题构造了一个高效的分级全同态加密方案。2013年Gentry等^[8]基于LWE问题构造了一个简单自然的分级全同态加密方案。

Banerjee等^[9]在Eurocrypt 2012上定义了带舍入学习(Learning With Rounding, LWR)问题以及环上LWR(ring-LWR)问题，并在一定参数条件下给出了从LWE问题到LWR问题的归约，以及从环上LWE问题到环上LWR问题的归约。LWR问题是LWE问题的变型，它们的区别主要在于LWE问题需要进行高斯噪声抽样，而LWR问题不需要进行高斯噪声抽样。后来，Bogdanov等^[10]又改进了从LWE问题到LWR问题的归约。目前，人们基于LWR问题已构造了一些公钥密码方案，如公钥加密方案^[11]、身份基加密方案^[12]等。

人们基于LWE问题已构造了许多全同态加密方案^{[3, 5, 7-8]}，然而这些方案都需要进行高斯噪声抽样。因为高斯噪声抽样的计算开销很大，所以高斯噪声抽样是制约这些方案计算性能的瓶颈因素。而LWR问题无需进行高斯噪声抽样，故基于LWR问题构造全同态加密方案，从而摒弃耗时的高斯噪声抽样，不失为改善全同态加密方案计算性能的一条有效途径。因为LWR问题是LWE问题的变型，所以可比照现有基于LWE问题的全同态加密方案，而构造基于LWR问题的全同态加密方案。

最近，Costache等^[13]比照Brakerski等^[7]提出的方案构造了一个基于环上LWR问题的分级全同态加密方案。Costache等之所以比照Brakerski等^[7]提出的方案，主要是考虑到在基于LWE的全同态加密方案中，Brakerski等^[7]所提方案的计算效率是比较高的。在基于LWE的全同态加密方案中，Gentry等^[8]所提方案适用于比较多的场合，例如：基于Gentry等^[8]提出的方案，人们构造了身份基全同态加密方案^[14-17]、多密钥全同态加密方案^[18-19]等；基于多密钥全同态加密方案^[18-19]，研究者们又进一步构造了属性基全同态加密方案^[20-21]。故而本文基于Gentry等^[8]提出的方案构造了一个基于LWR问题的分级全同态加密方案。Gentry等^[8]所提方案之所以比其他全同态加密方案适用于更多场合，主要是因为它在同态运算时不需要运算密钥evk参与，而其他全同态加密方案在同态运算时都需要运算密钥evk协助。本文所构造的全同态加密方案亦不需要运算密钥evk，因此基于本文所构造的方案，可以进一步构造身份基全同态加密方案、多密钥全同态加密方案以及属性基全同态加密方案等。

1 预备知识

本文向量如a等都为行向量，〈a, b〉=a·b^T表示向量a与b的内积，其中b^T表示向量b的转置。‖a‖_k=${{\left( \sum\limits_{i}{a_{i}^{k}} \right)}^{1/k}}$表示向量a的l_k范数。对向量a的范数来说，显然有‖a‖₁≥‖a‖₂≥‖a‖_∞。(A|B)表示矩阵A与B的连接，A^T表示矩阵A的转置，I_k表示大小为k的单位矩阵。$\left\lceil \cdot \right\rceil $表示向上取整，$\left[\!\left[\cdot \right]\!\right]$表示四舍五入取整, negl(·)表示在计算上可忽略的函数。Z表示整数环，Z_q表示模q剩余类环。本文中的对数运算为log的底为2。

1.1 困难问题

定义1  LWE问题^[6]。令n和q≥2为整数。对向量s∈Z_qⁿ，定义A_{s, χ}为Z_qⁿ×Z_q上的分布，它是通过均匀选取a_i←Z_qⁿ，输出(a_i, b_i=〈a_i, s〉+e_i)∈Z_qⁿ×Z_q而获得的，其中e_i←χ，χ为Z_q上的误差分布，通常χ为离散高斯分布。对某一分布之上的s∈Z_qⁿ，LWE_{n, q, χ}问题是区分若干抽样(a_i, b_i)←A_{s, χ}与等量的均匀抽样(c_i, d_i)←Z_qⁿ×Z_p。

定义2  B有界分布。一族Z上的分布{χ_n}_{n∈ N} ，如果Pr_e←χn[|e|>B]≤negl(n)，其中B=B(n)，则称它为B有界分布。

定理1^{[6, 22-24]}  令q=q(n)为素数的幂q=a^r或小素数的积$q=\prod\limits_{i}{{{q}_{i}}}$，令$B\ge \omega \left( \sqrt{\operatorname{lb}\ n} \right)\cdot \sqrt{n}$，则存在B有界分布χ，该分布可有效抽样，且满足如果存在求解平均情况LWE_{n, q, χ}问题的有效算法，则：①存在求解最差情况$\rm{GapSV}{{\rm{P}}_{\tilde{O}\left( {nq}/{B}\; \right)}}$问题的有效量子算法；②如果$q\ge \tilde{O}\left( {{2}^{{n}/{2}\;}} \right)$，则存在求解最差情况$\rm{GapSV}{{\rm{P}}_{\tilde{O}\left( {nq}/{B}\; \right)}}$问题的有效经典算法。在这两种情形下，如果在LWE_{n, q, χ}问题中考虑次多项式优势，则需令B≥Õ(n)，而作为结果的近似因子亦稍大于Õ(n^1.5q/B)。

定义3  取整函数。定义取整函数${{\left[\!\left[\cdot \right]\!\right]}_{p}}:\, \ {{\bf{Z}}_{q}}\to {{\bf{Z}}_{p}}$，其中q≥p≥2，即对x∈Z_q，${{\left[\!\left[x \right]\!\right]}_{p}}=\left[\!\left[\frac{p}{q}\cdot x \right]\!\right]$。

定义4  LWR问题^[9]。令n和q≥p≥2为整数。对向量s∈Z_qⁿ，定义A_{s, p}为Z_qⁿ×Z_p上的分布，它是通过均匀选取a_i←Z_qⁿ，输出$\left( {{\mathit{\boldsymbol{a}}}_{i}}, \ {{b}_{i}}={{\left[\!\left[\left\langle {{\mathit{\boldsymbol{a}}}_{i}}, \ \mathit{\boldsymbol{s}} \right\rangle \right]\!\right]}_{p}} \right)\in {\bf{Z}}_{q}^{n}\times {{\bf{Z}}_{p}}$而获得的。对某一分布之上的s∈Z_qⁿ，LWR_{n, q, p}问题是区分若干抽样(a_i, b_i)←A_{s, p}与等量的均匀抽样(c_i, d_i)←Z_qⁿ×Z_p。

定理2^[9]  令χ是任意Z_q上的B有界分布，且χ可有效抽样。令$q\ge p\cdot B\cdot {{n}^{\omega \left( 1 \right)}}$，于是，求解针对任一分布之上s∈Z_qⁿ的LWR_{n, q, p}问题，至少与求解针对同一分布之上s∈Z_qⁿ的LWE_{n, q, χ}问题一样困难。

对于从LWE问题到LWR问题的归约，Bogdanov等^[10]又给出了一个比定理2更佳的归约结果。

1.2 向量分解技术

向量分解技术能保持向量的內积不发生变化。它包括以下转换操作：

BitDecomp_q(x)：例如对x∈Z_q^k，输出$\left( {{x}_{1, \ 0}}, \ {{x}_{1, \ 1}}, \ \ldots, \ {{x}_{1, \ \left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}}, \ \ldots, \ {{x}_{k, \ 0}}, \ {{x}_{k, \ 1}}, \ \ldots, \ {{x}_{k, \ \left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}} \right)\in {{\left\{ 0, \ 1 \right\}}^{k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil }}$，其中${{x}_{i, \ 0}}, \ {{x}_{i, \ 1}}, \ \ldots, \ {{x}_{i, \ \left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}}$为x_i∈Z_q的二进制形式，且x_{i, 0}是最低有效位，${{x}_{i, \ \left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}}$是最高有效位。

BitDecomp_q^-1(x′)：例如对$\mathit{\boldsymbol{x}}' \in {{\left\{ 0, \ 1 \right\}}^{k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil }}$，输出$\left( \sum\limits_{j=0}^{\left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}{{{2}^{j}}\cdot {{x}_{1, \ j}}}, \sum\limits_{j=0}^{\left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}{{{2}^{j}}\cdot {{x}_{2, \ j}}}, \ldots, \ \sum\limits_{j=0}^{\left\lceil \operatorname{l}\rm{b}\ q \right\rceil -1}{{{2}^{j}}\cdot {{x}_{k, \ j}}} \right)\in {\bf{Z}}_{q}^{k}$。该定义对于非0/1向量$\mathit{\boldsymbol{{x}'}}\in {{\bf{Z}}^{k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil }}$也是成立的。

Flatten_q(x′)：例如对x′∈Z^{$k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil $}，输出BitDecomp_q(BitDecomp_q^-1(x′))∈{0, 1}^{$k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil $}。

PowersOfTwo_q(y)：例如对y∈Z_q^k，输出$\left( {{y}_{1}}, \ 2{{y}_{1}}, \ \ldots, \ {{2}^{\left\lceil \operatorname{l}\rm{b}\ q \right\rceil-1}}{{y}_{1}}, \ \ldots, \ {{y}_{k}}, \ 2{{y}_{k}}, \ \ldots, \ {{2}^{\left\lceil \operatorname{l}\rm{b}\ q \right\rceil-1}}{{y}_{k}} \right)\in {\bf{Z}}_{q}^{k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil }$。

对上述这些操作来说，显然有:

①〈BitDecomp_q(x), PowersOfTwo_q(y)〉=〈x, y〉；

② 对任意x′∈Z^{$k\cdot \left\lceil \operatorname{l}\rm{b}\ q \right\rceil $}，有〈x′, PowersOfTwo_q(y)〉=〈BitDecomp_q^-1(x′), y〉=〈Flatten_q(x′), PowersOfTwo_q(y)〉。

而且，对于矩阵A，令BitDecomp_q(A)、BitDecomp_q^-1(A)和Flatten_q(A)皆为矩阵，且是通过分别处理A的每一行而得到的。

许多全同态加密方案^{[7-8, 25]}都应用了向量分解技术。

1.3 密码定义

一个分级全同态加密方案包括密钥生成KeyGen、加密Enc、解密Dec和同态运算Eval四个多项式时间算法。其中，(pk, sk)←KeyGen(1^λ, 1^L)输入安全参数λ和电路深度L，输出公钥pk和私钥sk；c←Enc(pk, μ)应用公钥pk加密消息μ∈{0, 1}生成密文c；μ←Dec(sk, c)应用私钥sk解密密文c恢复消息μ∈{0, 1}；c_f←Eval(f, c₁, c₂, …, c_k)输入电路f:{0, 1}^k→{0, 1}和密文c₁, c₂, …, c_k，输出密文c_f。

通常，f为有限域GF(2)上的算术电路，只包含加法门和乘法门两种门电路，因而人们习惯上把Eval分成同态加法c_add←Add(c₁, c₂)和同态乘法c_mult←Mult(c₁, c₂)。

分级全同态加密方案的标准安全性为语义安全性，即在选择明文攻击下的不可区分性(INDistinguishability under Chosen Plaintext Attack, IND-CPA)。

定义3   紧致性。如果一个分级全同态加密方案的解密电路不依赖于运算函数f，则称它是紧致的。

2 基础加密方案

首先，基于LWR问题构造一个标准公钥加密方案。

2.1 构造

KeyGen(1^λ, 1^L)：选择参数n=n(λ, L)，选择参数q与p，并且q≥p≥2。这些参数应使得LWR_{n, q, p}问题至少为2^λ安全的。选择参数m=m(λ, L)=O(n lb q+lb p)。令l₁=$\left\lceil \operatorname{l}\rm{b}\ q \right\rceil $，l₂=$\left\lceil \operatorname{l}\rm{b}\ q \right\rceil $，N=nl₁+l₂。均匀选择向量d←Z_qⁿ，令s=(1, -p·d/q)。并令z=(PowersOfTwo_p(1), -p PowersOfTwo_q(d)/q)。对于1≤k≤m，均匀选择向量v_k←Z_qⁿ，令${{u}_{k}}\leftarrow {{\left[\!\left[{{\mathit{\boldsymbol{v}}}_{k}}\cdot {{\mathit{\boldsymbol{d}}}^{\rm{T}}} \right]\!\right]}_{p}}$。令u^T=(u₁, u₂, …, u_m)^T∈Z_p^m×1，B=(v₁^T|v₂^T|…|v_m^T)^T∈Z_q^m×n，A=(u^T|B)∈(Z_p^m×1|Z_q^m×n)。最后，设定公钥pk=A=(u^T|B)，私钥sk=s。

Enc(pk, μ∈{0, 1})：对于消息μ∈{0, 1}，均匀选择矩阵R←{0, 1}^N×m，并输出密文C，即:

$ \begin{array}{l} \mathit{\boldsymbol{C}} = \left( {\left. {{\rm{Flatte}}{{\rm{n}}_p}\left( {{{\left( {\mu \cdot {\mathit{\boldsymbol{I}}_{{l_2}}}\left| 0 \right.} \right)}^{\rm{T}}} + {\rm{BitDecom}}{{\rm{p}}_p}\left( {\mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}}} \right)} \right)\;} \right|} \right.\\ \;\;\;\;\;\;\;\left. {{\rm{Flatte}}{{\rm{n}}_q}\left( {{{\left( {0\left| {\mu \cdot {\mathit{\boldsymbol{I}}_{n{l_1}}}} \right.} \right)}^{\rm{T}}} + {\rm{BitDecom}}{{\rm{p}}_q}\left( {\mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}}} \right)\;} \right)} \right) \in \\ \;\;\;\;\;\;\;\left( {{\bf{Z}}_p^{N \times {l_2}}\left| {\, {\bf{Z}}_q^{N \times n{l_1}}} \right.} \right) \end{array} $

Dec(sk, C)：易见，密钥z的前l₂个分量为(1, 2, …, 2^l₂-1)，其中有z_i=2ⁱ∈(p/4, p/2]。计算x_i←C_i·z^T，其中C_i为C的第i行，并且输出$\mu ' = \left[\kern-0.15em\left[{\;{x_i}/{z_i}} \right]\kern-0.15em\right]$。

2.2 正确性

在密钥生成算法KeyGen中，有:

$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{A}} \cdot {\mathit{\boldsymbol{s}}^{\rm{T}}} = \left( {{\mathit{\boldsymbol{u}}^{\rm{T}}}|\mathit{\boldsymbol{B}}} \right) \cdot {{\left( {1, \;-\frac{p}{q} \cdot \mathit{\boldsymbol{d}}} \right)}^{\rm{T}}} = {\mathit{\boldsymbol{u}}^{\rm{T}}}-\frac{p}{q} \cdot \mathit{\boldsymbol{B}} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}} = }\\ {\left( {\begin{array}{*{20}{c}} {{u_1}-\frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_1} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}}\\ {{u_2} - \frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_2} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}}\\ \vdots \\ {{u_m} - \frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_m} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{e_1}}\\ {{e_2}}\\ \vdots \\ {{e_m}} \end{array}} \right)} \end{array} $

令e^T=(e₁, e₂, …, e_m)^T，其中e_k=u_k-${\frac{p}{q}}$·v_k·d^T=${\left[\kern-0.15em\left[{{\mathit{\boldsymbol{v}}_k} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}} \right]\kern-0.15em\right]_p} - \frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_k} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}} = \left[\kern-0.15em\left[{\frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_k} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}} \right]\kern-0.15em\right] -\frac{p}{q} \cdot {\mathit{\boldsymbol{v}}_k} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}} \in \left( { -1/2, \;1/2} \right]$。在解密算法Dec中，有:

$ \begin{array}{l} \mathit{\boldsymbol{C}} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = \left( {\left. {{\rm{Flatte}}{{\rm{n}}_p}\left( {\left( {\begin{array}{*{20}{c}} {\mu \cdot {\mathit{\boldsymbol{I}}_{{l_2}}}}\\ 0 \end{array}} \right) + {\rm{BitDecom}}{{\rm{p}}_p}\left( {\mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}}} \right)} \right)\;} \right|} \right.\\ \;\;\;\;\left. {{\rm{Flatte}}{{\rm{n}}_q}\left( {\left( {\begin{array}{*{20}{c}} 0\\ {\mu \cdot {\mathit{\boldsymbol{I}}_{n{l_1}}}} \end{array}} \right) + {\rm{BitDecom}}{{\rm{p}}_q}\left( {\mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}}} \right)\;} \right)} \right) \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = \\ \;\;\;\;{\rm{Flatte}}{{\rm{n}}_p}\left( {\left( {\begin{array}{*{20}{c}} {\mu \cdot {\mathit{\boldsymbol{I}}_{{l_2}}}}\\ 0 \end{array}} \right) + {\rm{BitDecom}}{{\rm{p}}_p}\left( {\mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}}} \right)} \right) \cdot \\ \;\;\;\;{\left( {{\rm{PowersOfTw}}{{\rm{o}}_p}\left( 1 \right)} \right)^{\rm{T}}} + {\rm{Flatte}}{{\rm{n}}_q}\left( {\left( {\begin{array}{*{20}{c}} 0\\ {\mu \cdot {\mathit{\boldsymbol{I}}_{n{l_1}}}} \end{array}} \right) + } \right.\\ \;\;\;\;\;\left. {{\rm{BitDecom}}{{\rm{p}}_q}\left( {\mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}}} \right)} \right) \cdot {\left( {-\frac{p}{q}{\rm{PowersOfTw}}{{\rm{o}}_q}\left( \mathit{\boldsymbol{d}} \right)} \right)^{\rm{T}}} = \\ \;\;\;\;\;\left( {\begin{array}{*{20}{c}} {\mu \cdot {{\left( {{\rm{PowersOfTw}}{{\rm{o}}_p}\left( 1 \right)} \right)}^{\rm{T}}}}\\ 0 \end{array}} \right) + \mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}} + \\ \;\;\;\;\;\;\left( {\begin{array}{*{20}{c}} 0\\ {\mu \cdot {{\left( {-\frac{p}{q}{\rm{PowersOfTw}}{{\rm{o}}_q}\left( \mathit{\boldsymbol{d}} \right)} \right)}^{\rm{T}}}} \end{array}} \right)-\frac{p}{q} \cdot \mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}} = \\ \;\;\;\;\;\;\left( {\begin{array}{*{20}{c}} {\mu \cdot {{\left( {{\rm{PowersOfTw}}{{\rm{o}}_p}\left( 1 \right)} \right)}^{\rm{T}}}}\\ {\mu \cdot {{\left( { - \frac{p}{q}{\rm{PowersOfTw}}{{\rm{o}}_q}\left( \mathit{\boldsymbol{d}} \right)} \right)}^{\rm{T}}}} \end{array}} \right) + \mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}} - \\ \;\;\;\;\;\;\;\frac{p}{q} \cdot \mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}} = \mu \cdot \left( {\begin{array}{*{20}{c}} {{{\left( {{\rm{PowersOfTw}}{{\rm{o}}_p}\left( 1 \right)} \right)}^{\rm{T}}}}\\ {{{\left( { - \frac{p}{q}{\rm{PowersOfTw}}{{\rm{o}}_q}\left( \mathit{\boldsymbol{d}} \right)} \right)}^{\rm{T}}}} \end{array}} \right) + \\ \;\;\;\;\;\;\mathit{\boldsymbol{R}} \cdot \left( {{\mathit{\boldsymbol{u}}^{\rm{T}}} - \frac{p}{q} \cdot \mathit{\boldsymbol{B}} \cdot {\mathit{\boldsymbol{d}}^{\rm{T}}}} \right) = \mu \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{e}}^{\rm{T}}} \end{array} $

故有x_i=C_i·z^T=μ·z_i+R_i·e^T，即$\frac{{{x_i}}}{{{z_i}}} = \mu + \frac{{{\mathit{\boldsymbol{R}}_i} \cdot {\mathit{\boldsymbol{e}}^{\rm{T}}}}}{{{z_i}}}$，其中${z_i} = {2^i} \in \left( {\frac{p}{4}, \;\frac{p}{2}} \right]$。因此当$\frac{{{\mathit{\boldsymbol{R}}_i} \cdot {\mathit{\boldsymbol{e}}^{\rm{T}}}}}{{{z_i}}} < \frac{1}{2}$，即R_i·e^T≤$\frac{p}{8}$时，Dec能利用取整而输出正确的μ。因为有R_i·e^T≤‖R·e^T‖_∞≤‖e^T‖₁≤$\frac{m}{2}$，所以如果$\frac{m}{2} \le \frac{p}{8}$，即p≥4m，Dec即能实现正确解密。

2.3 安全性

定理3  假设LWR问题是难解的，那么上述加密方案是IND-CPA安全的。

证明  考虑下列游戏，其中Adv_Gamei($\mathcal{A} $)代表敌手$\mathcal{A} $在游戏i中的优势。

Game 0  该游戏为标准的IND-CPA游戏。

Game 1  与Game 0相比，Game 1修改了密钥生成算法。挑战者不是调用KeyGen生成公钥，它是通过随机均匀选择u←Z_p^m和B←Z_q^m×n，而令pk=A=(u^T|B)∈(Z_p^m×1|Z_q^m×n)。因为假设LWR问题是难解的，所以Game 0与Game 1在计算上是不可区分的，即有|Adv_{Game 0}($\mathcal{A}$)-Adv_{Game 1}($\mathcal{A}$)|≤nelg(λ)。对于挑战者在该游戏中调用Enc所产生的密文C=(C_p|C_q)∈(Z_p^N×l₂|Z_q^N×nl₁)，令$\left( {{\rm{BitDecomp}}_p^{-1}\left( {{\mathit{\boldsymbol{C}}_p}} \right)\left| {\, {\rm{BitDecomp}}_q^{-1}\left( {{\mathit{\boldsymbol{C}}_q}} \right)} \right.} \right) = \left( {\left. {\left( {\left( {\begin{array}{*{20}{c}} {\mu {\mathit{\boldsymbol{G}}_p}}\\ 0 \end{array}} \right) + \mathit{\boldsymbol{R}} \cdot {\mathit{\boldsymbol{u}}^{\rm{T}}}} \right)\;} \right|} \right.$$\left. {\left( {\left( {\begin{array}{*{20}{c}} 0\\ {\mu {\mathit{\boldsymbol{G}}_q}} \end{array}} \right) + \mathit{\boldsymbol{R}} \cdot \mathit{\boldsymbol{B}}} \right)} \right) \in \left( {\mathit{\boldsymbol{Z}}_p^{N \times 1}\left| {\, \mathit{\boldsymbol{Z}}_q^{N \times n}} \right.} \right)$，其中G_p=BitDecomp_p^-1(I_l2)，G_q=BitDecomp_q^-1(I_nl1)。

Game 2  与Game 1相比，Game 2修改了加密算法。挑战者不是调用Enc产生密文，而是随机均匀选择Ĉ=(Ĉ_p|Ĉ_q)←(Z_p^N×l₂|Z_q^N×nl₁)。由剩余哈希引理(leftover hash lemma)^[26]可知，(BitDecomp_p^-1(C_p)|BitDecomp_q^-1(C_q))与(BitDecomp_p^-1(Ĉ_p)|BitDecomp_q^-1(Ĉ_q))是统计不可区分的。即Game 1与Game 2是统计不可区分的，即有|Adv_{Game 1}($\mathcal{A}$)-Adv_{Game 2}($\mathcal{A}$)|≤nelg(λ)。

在Game 2中，挑战者所给出的公钥和密文都是均匀随机的，且与消息μ∈{0, 1}无关，因此Adv_{Game 2}($\mathcal{A}$)=0。故在Game 0中有Adv_{Game 0}($\mathcal{A}$)≤nelg(λ)。即在LWR问题难解的假设下，上述加密方案满足IND-CPA安全性要求。

3 同态运算

接下来，分析有限域GF(2)上的同态加法和同态乘法运算。

如果给定密文C₁=(C_{1, p}|C_{1, q})∈(Z_p^N×l₂|Z_q^N×nl₁)，C₂=(C_{2, p}|C_{2, q})∈(Z_p^N×l₂|Z_q^N×nl₁)，则有:

1) Add(C₁, C₂)：输出密文C₁与C₂的和C_add，即:

$ \begin{array}{l} {\mathit{\boldsymbol{C}}_{{\rm{add}}}} = \left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_{{\rm{add}}, \;p}}} \right)\, \left| {\, {\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_{{\rm{add, }}\;q}}} \right)} \right.} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_{1, \;p}} + {\mathit{\boldsymbol{C}}_{2, \;p}}} \right)\, \left| {\, {\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_{1, \;q}} + {\mathit{\boldsymbol{C}}_{2, \;q}}} \right)} \right.} \right) \end{array} $

2) Mult(C₁, C₂)：输出密文C₁与C₂的积C_mult，即:

$ \begin{array}{l} {\mathit{\boldsymbol{C}}_{{\rm{mult}}}} = \left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_{{\rm{mult, }}\;p}}} \right)\, \left| {\, {\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_{{\rm{mult, }}\;q}}} \right)} \right.} \right) = \\ \;\;\;\;\;\;\;\;\;\;\left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_{2, \;p}}} \right)\, \left| {\, {\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_{2, \;q}}} \right)} \right.} \right) \end{array} $

已知道，C₁·z^T=μ₁·z^T+e₁^T，C₂·z^T=μ₂·z^T+e₂^T，其中e₁和e₂为误差。若记z=(z_p, z_q)，则有：

$ \begin{array}{l} {\mathit{\boldsymbol{C}}_{{\rm{add}}}} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = \left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_{1, \;p}} + {\mathit{\boldsymbol{C}}_{2, \;p}}} \right)|} \right.\\ \;\;\;{\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_{1, \;q}} + {\mathit{\boldsymbol{C}}_{2, \;q}}} \right) \cdot {\left( {{\mathit{\boldsymbol{z}}_p}, \;{\mathit{\boldsymbol{z}}_q}} \right)^{\rm{T}}}{\rm{ = }}\\ \;\;\;\left( {{\mathit{\boldsymbol{C}}_{1, \;p}} + {\mathit{\boldsymbol{C}}_{2, \;p}}} \right) \cdot {\mathit{\boldsymbol{z}}_p}^{\rm{T}} + \left( {{\mathit{\boldsymbol{C}}_{1, \;q}} + {\mathit{\boldsymbol{C}}_{2, \;q}}} \right) \cdot {\mathit{\boldsymbol{z}}_q}^{\rm{T}} = \\ \;\;\;\;\left( {{\mathit{\boldsymbol{C}}_{1, \;p}} \cdot {\mathit{\boldsymbol{z}}_p}^{\rm{T}} + {\mathit{\boldsymbol{C}}_{1, \;q}} \cdot {\mathit{\boldsymbol{z}}_q}^{\rm{T}}} \right) + \left( {{\mathit{\boldsymbol{C}}_{2, \;p}} \cdot {\mathit{\boldsymbol{z}}_p}^{\rm{T}} + {\mathit{\boldsymbol{C}}_{2, \;q}} \cdot {\mathit{\boldsymbol{z}}_q}^{\rm{T}}} \right) = \\ \;\;\;\;\;{\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + {\mathit{\boldsymbol{C}}_2} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = {\mu _1} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \mathit{\boldsymbol{e}}_1^{\rm{T}} + {\mu _2} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \mathit{\boldsymbol{e}}_2^{\rm{T}} = \\ \;\;\;\;\;\left( {{\mu _1} + {\mu _2}} \right) \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \left( {\mathit{\boldsymbol{e}}_1^{\rm{T}} + \mathit{\boldsymbol{e}}_2^{\rm{T}}} \right) \end{array} $

$ \begin{array}{l} {\mathit{\boldsymbol{C}}_{{\rm{mult}}}} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = \left( {{\rm{Flatte}}{{\rm{n}}_p}\left( {{\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_{2, \;p}}} \right)|} \right.\\ \;\;\;\;\;{\rm{Flatte}}{{\rm{n}}_q}\left( {{\mathit{\boldsymbol{C}}_\mathit{\boldsymbol{1}}} \cdot {\mathit{\boldsymbol{C}}_{2, \;q}}} \right) \cdot {\left( {{\mathit{\boldsymbol{z}}_p}, \;{\mathit{\boldsymbol{z}}_q}} \right)^{\rm{T}}} = \\ \;\;\;\;\;{\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_{2, \;p}} \cdot {\mathit{\boldsymbol{z}}_p}^{\rm{T}} + {\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_{2, \;q}} \cdot {\mathit{\boldsymbol{z}}_q}^{\rm{T}} = \\ \;\;\;\;\;{\mathit{\boldsymbol{C}}_1} \cdot \left( {{\mathit{\boldsymbol{C}}_{2, \;p}} \cdot {\mathit{\boldsymbol{z}}_p}^{\rm{T}} + {\mathit{\boldsymbol{C}}_{2, \;q}} \cdot {\mathit{\boldsymbol{z}}_q}^{\rm{T}}} \right) = {\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{C}}_2} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} = \\ \;\;\;\;\;\;{\mathit{\boldsymbol{C}}_1} \cdot \left( {{\mu _2} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \mathit{\boldsymbol{e}}_2^{\rm{T}}} \right) = {\mu _2} \cdot {\mathit{\boldsymbol{C}}_1} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + {\mathit{\boldsymbol{C}}_1} \cdot \mathit{\boldsymbol{e}}_2^{\rm{T}} = \\ \;\;\;\;\;\;{\mu _2} \cdot \left( {{\mu _1} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \mathit{\boldsymbol{e}}_1^{\rm{T}}} \right) + {\mathit{\boldsymbol{C}}_1} \cdot \mathit{\boldsymbol{e}}_2^{\rm{T}} = \\ \;\;\;\;\;\;{\mu _1} \cdot {\mu _2} \cdot {\mathit{\boldsymbol{z}}^{\rm{T}}} + \left( {{\mu _2} \cdot \mathit{\boldsymbol{e}}_1^{\rm{T}} + {\mathit{\boldsymbol{C}}_1} \cdot \mathit{\boldsymbol{e}}_2^{\rm{T}}} \right) \end{array} $

所以C_add为消息μ₁+μ₂的密文，其误差为e_add^T=e₁^T+e₂^T；C_mult为消息μ₁·μ₂的密文，其误差为e_mult^T=μ₂·e₁^T+C₁·e₂^T。而且，不难看出，‖e_add^T‖_∞≤‖e₁^T‖_∞+‖e₂^T‖_∞；‖e_mult^T‖_∞≤‖μ₂·e₁^T‖_∞+‖C₁·e₂^T‖_∞≤‖e₁^T‖_∞+N·‖e₂^T‖_∞，因为其中μ₂∈{0, 1}，C₁∈{0, 1}^N×N。

通过迭代调用以上加法和乘法，可完成电路f的运算。因为C_mult的误差e_mult^T比C_add的误差e_add^T大得多，所以电路f的深度主要是由乘法运算决定的。若令初始密文的误差‖e^T‖_∞≤E，则f输出密文C_f的误差‖e_f‖_∞≤(N+1)^L·E，其中L为f的电路深度。若有‖e_f‖_∞≤(N+1)^L·E≤p/8，则f输出的密文C_f能够被正确解密。

根据定理2知道，在LWR_{n, q, p}问题中有$q \ge p \cdot B \cdot {n^{\omega \left( 1 \right)}}$。为正确解密C_f，有p≥8(N+1)^L·E，所以q≥8(N+1)^L·E·B·n^ω(1)，即q/B≥8(N+1)^L·E·n^ω(1)。又LWE_{n, q, χ}问题在q/B=2^o(n)时，仍旧是难解的^[27]，所以有L=o(n)，即L为多项式深度。即在LWR_{n, q, p}问题难解的假设下，存在分级全同态加密方案。

显然，对构造的分级全同态加密方案来说，电路f输出的密文C_f∈(Z_p^N×l₂|Z_q^N×nl₁)。所以C_f的规模与电路f的大小无关，即构造的分级全同态加密方案满足紧致性要求。

4 性能比较

Costache等^[13]提出的基于环上LWR的全同态加密方案，是比照Brakerski等^[7]的基于环上LWE的全同态加密方案构造的。在Brakerski等^[7]的方案中，不仅要生成公钥，还要生成同态运算密钥evk。而evk是对私钥进行加密的结果，其不能由用户的身份信息计算出来，因此，由Brakerski等^[7]的方案无法进而构造身份基全同态加密方案等。本文提出的基于LWR的全同态加密方案，是比照Gentry等^[8]的基于LWE的全同态加密方案构造的。在Gentry等^[8]的方案中，不需要生成同态运算密钥evk。基于此，基于Gentry等^[8]的方案能进而构造身份基全同态加密方案等。目前人们基于Gentry等^[8]的全同态加密方案，已构造了身份基全同态加密方案^[14-17]、多密钥全同态加密方案^[18-19]和属性基全同态加密方案^[20-21]等。因此Gentry等^[8]的全同态加密方案比Brakerski等^[7]的全同态加密方案应用场合更多。Costache等^[13]所提的全同态加密方案亦要生成同态运算密钥evk，因此由Costache等^[13]所提方案亦无法进而构造身份基全同态加密方案等。本文所提的全同态加密方案亦不需要生成同态运算密钥evk，由此基于本文所提方案亦能进而构造身份基全同态加密方案、多密钥全同态加密方案和属性基全同态加密方案等。因此本文所提方案比Costache等^[13]所提方案应用场合更多。

5 结语

本文借鉴Gentry等^[8]的全同态加密方案，构造了一个基于LWR的分级全同态加密方案，并证明了它的正确性、IND-CPA安全性和紧致性。目前Costache等^[13]参照Brakerski等^[7]的全同态加密方案，已构造了一个基于环上LWR的分级全同态方案。本文所提方案比Costache等^[13]的方案应用场合更多。不过，由于Gentry等^[8]的全同态加密方案比Brakerski等^[7]的全同态加密方案的计算效率差一些，故而本文所提方案比Costache等^[13]的方案的计算效率也差一些。因此，下一步致力于：1)以本文所构造的方案为基础，构造基于LWR问题的身份基分级全同态加密方案、多密钥分级全同态加密方案和属性基分级全同态加密方案；2)利用有关全同态加密性能优化技术，提高本文所构造的方案的计算性能。