门限密码学是密码学的一个重要分支，是门限方案与密码方案(如加密和签名)的有机集成.秘密共享和门限密码的主要思想是将一个密钥分割成若干份额(share)分散存储于多个服务器成员，当需要重构密钥或使用它进行某种密码运算时，必须多于特定数量的成员联合才能共同完成，少于特定数量的任何成员组都不能计算得到此密钥.也就是说，少数成员的秘密份额泄露不会影响整个系统密钥的安全.这种方法直接降低了密钥泄露的可能性.例如，(k, u)门限公钥加密需要一个私钥被u个解密服务器共享，且至少有k个解密服务器被要求解密密文.该方案可看作委托计算中委托者(dealer)希望通过解密服务器(worker)解密密文c，委托者将密文发送给k个解密服务器，解密服务器拿到密文c的部分解密，并将其发送给委托者.如果委托者收到至少k个c的解密共享，即可恢复出密文c的解密.

2010年，Bendlin等^[1]给出基于Regev密码系统^[2]的一种能够抵抗强敌手攻击的门限密码方案. 2011年Frederiksen^[3]在文献[1]的基础上给出了一种基于Regev公钥加密方案的门限多比特公钥加密方案，但方案本身并不完善. Li和Brakerski等^[4-6]则分别指出基于Regev构造门限密码系统存在泄露私钥的风险.近年来，Boneh等^[7-8]利用全同态加密技术，给出了基于格的秘密共享系统.但是，这些方案都是基于Regev加密方案的.

基于此，提出一种基于Gentry-Peikert-Vaikuntanathan (GPV)^[9]的非交换门限公钥加密方案(TGPV, threshold-based GPV). TGPV方案具有一个分布式密钥生成协议和一个有效非交互的解密协议，使其能够抵抗静态且被动敌手的收买.最后，在通用可组合(UC，universal composability)框架下对方案的密钥生成协议及分布式解密协议进行安全性证明.

1 GPV公钥加密方案

Regev在2005年首次给出基于容错学习(LWE，learning with errors)假设的格公钥加密算法^[2].随后，Gentry等^[9]在2008年提出一种对偶格(Dual Regev)的加密算法，即GPV公钥加密方案.其区别在于，GPV公钥加密方案将Regev方案私钥的随机数充当加密的随机数；在LWE假设中，Regev方案的密文尺寸依赖于参数m≥n$\lceil\log q\rceil$+2λ，为O(nlog²q)，而GPV方案的密文尺寸则为O(mlog²q).

GPV方案的构造、安全性、正确性证明可参考文献[9]，此处不再赘述.

2 基于门限的GPV公钥加密方案

下面将分别介绍基于GPV方案的门限加密TGPV方案初始化、密钥生成、加密和解密算法设计思路.

2.1 初始化算法

${\rm{params}} \leftarrow {\rm{TGPV}}.{\mathop{\rm Setup}\nolimits} \left( {{1^\lambda }, n, m, q, u, k} \right) $

(1)

算法输入安全参数1^λ, 输出参数params.参数m、n、u和k，分别表示游戏参与者的总数以及解密时所需参与者的个数.

2.2 密钥生产算法

$({\rm{pk}}, {\rm{sk}}) \leftarrow {\rm{TGPV}}.\;\;{\rm{KeyGen}}({\rm{params}}) $

(2)

假设每个参与者参与游戏的序号是唯一且在范围[1, u]内，其主要功能是能够诚实且无偏向地生成、分发密钥和密钥份额(key-shares)给参与者.

1) sk←TGPV. SecretKeyGen(params)

① 参与者允许以与GPV密码系统相同的方式来选取私钥共享.

② 调用Shamir秘密共享算法^[10]，以给定参与者的数量来确定拉格朗日多项式次数，同时共享参与方的私钥，对应的秘密共享作为输出向量，实际上，秘密共享输出向量由k-1个从被收买的参与者中得到的(p, e_i)_i=1ⁿ值和实际计算得到的1个(0, e_i)_i=1ⁿ值组成，其中，e=(e₁, e₂, …, e_n)，秘密e_i∈Z_q, i∈[n].因此，有n对候选者中的k对，所以通过拉格朗日插值可以得到次数至多为k-1的n元多项式，记这些多项式为q_i(x)_i=1ⁿ.

③ 使用多项式q_i(x)_i=1ⁿ为其他诚实的参与者生成私钥共享，编号为x的参与者，将会从多项式q_i(x)_i=1ⁿ中得到第y个向量.

④ 对于大小为k的$\left(\begin{array}{l}\eta \\ k\end{array}\right)$群组，可以选出η个参与者，并选取一个随机整数模q，记为K_A，其中，A∈$\left[1, \left(\begin{array}{l}\eta \\ k\end{array}\right)\right]$为群组编号.若每个参与者不在给定的组A内接收这个组的K_A值，这就意味着指定的参与者将会接收到$\left(\begin{array}{l}\eta \\ k\end{array}\right)(\eta-k) / \eta$值.这里参数η是为刻画秘密恢复阶段(即TGPV. Dec)被收买的参与者的数目.

2) pk←TGPV. PublicKeyGen(sk, params)

① 选取随机矩阵A∈Z_q^n×m公共参数，随机选取向量e∈Z_q^m为私钥.

② 计算u=f_A(e)=Ae(mod q)∈Z_qⁿ.

③ 输出pk=[A|u]∈Z^n×m×Zⁿ，并发送给所有的参与者.

2.3 加密算法

$\mathit{\boldsymbol{c}} \leftarrow {\rm{TGPV}}.{\rm{Enc}}({\rm{pk}}, {{m}}) $

(3)

与GPV. Enc(·)相同，故此处省略.

2.4 解密算法

$\mu \leftarrow {\rm{TGPV}}.\;{\mathop{\rm Dec}\nolimits} ({\rm{sk}}, c) $

(4)

解密协议执行步骤如下：

1) 所有参与者均计算c₁-e^Tc₀=e′，用于解密计算.其中，e是给所有参与者的私钥共享，c=(c₀, c₁)为密文.

2) 参与者均计算一个唯一值$x=\sum\limits_{A} \phi_{K_{A}}$(c₀, c₁)∈$[-\sqrt{q}, \sqrt{q}]$，并返回需要解密的部分x+e′.其中，函数ϕ_KA(c₀, c₁)定义为输入c₀、c₁、K_A的伪随机函数，并返回一个数r^ϕ，该函数的目的是获得一个伪随机秘密共享.

3) 当解密器从参与者收到至少k个解密部分时，使用参与者个数作为x值，使用他们的x+e′值作为y值，执行拉格朗日算法.

4) 计算合成拉格朗日多项式的q(0)值，则

$q(0) = \left\{ {\begin{array}{*{20}{l}} {0, }&{q(0) \approx 0}\\ {1, }&{q(0) \approx \left\lfloor {\frac{q}{2}} \right\rfloor } \end{array}} \right. $

3 性能分析 3.1 正确性证明

定理1 令$\left(\begin{array}{l}u \\ k\end{array}\right) < \frac{1}{2 t} \sqrt{q}-1$，假设在分布式解密协议中，利用$\left\lfloor{\frac{q}{t} \boldsymbol{u}}\right\rceil+\boldsymbol{x}_{2}-\boldsymbol{E}^{\mathrm{T}} \boldsymbol{x}_{1}+\boldsymbol{r}^{\phi}$重构向量，此外，对于矩阵向量x₁和x₂中的每一个值x，有Pr[|x|≥$\lceil\sqrt{q}\rceil$]≤2^-O(n)，那么解密错误的概率是可以忽略的.

证明 对于给定结果向量，这个向量中所有的值都是以与指定加密相同的方式构造的.

1) 给定一个0∈Z_t，其加密结果是通过给定c₁[i]-E_i^Tc₀+r_i^ϕ=x_2i-E_i^Tx_1i+$\left\lfloor{\frac{q}{t} \cdot 0} \right\rceil$+r_i^ϕ，其中，向量S_i^T为S的第i行.

2) 由假设$\left(\begin{array}{l}u \\ k\end{array}\right) < \frac{1}{2 t} \sqrt{q}-1$可知|r_i^ϕ| < $\frac{q}{2 t}-\sqrt{q}$，又因为对于每个ϕ_KA(c₀, c₁)∈$[-\sqrt{q}, \sqrt{q}]$，将这些$\left(\begin{array}{l}u \\ k\end{array}\right)$相加.现在结合对|x|的假设可以得到|x_i+r_i^ϕ| < $\frac{q}{2 t}$的概率至少为1-2^-O(n).在这种情形下，相比$\frac{q}{t}$的任意倍小于q，结果更接近于0，所以解密是正确的.

此外，若解密值在[1, t]也可进行类似证明. x的分布由分布χ^*∑r_i给出，密钥生成器KeyGen用于生成密钥.因此，由文献[1]中定理1可得，假设噪声的绝对值|x|具有至少1-2^-O(n)的概率小于$\sqrt[3]{q}$，那么同样可以假设，在解密向量中对于每个i值至少有1-2^-O(n)的概率使得$\left|x_{i}\right|<\lfloor\sqrt[3]{q}\rfloor$.因此，对于l个错误，若合理选择参数l和n，对于整个消息最终解密错误的概率为一个可忽略概率(1-2^-O(n))^l.

3.2 安全性分析

采用Canetti^[7]于2001年提出的建立在计算复杂性理论基础上的UC框架来证明.

定义1 真实协议π UC-仿真一个理想协议ξ.如果对于任意的函数F，存在一个仿真器函数S，使得对于任意的环境机M及其任意的输入，环境机M分别与执行真实协议的函数F和执行理想协议的仿真器函数S相互作用后输出的不同结果的概率是可忽略的.

为简单起见，引入一个虚拟的实体client，仅是希望帮助参与者解密密文的实体，因此，在真实环境中client可能也是参与者.

对于理想函数F_Gen-Dec，有如下特性：

1) 所有诚实参与者准备好选取的私钥和构建的公钥之后，将公钥发送给所有的参与者(包括client和敌手)；

2) 当client请求解密密文(c₀, c₁)时，密文被发送给所有的参与者及敌手；3)在解密过程中，明文被重构并发送给client和敌手.

所以函数F_Gen-Dec可以被看作一个执行密钥生成和解密的黑盒，而不需要知道私钥或者诚实参与者看到私钥.

定理2 给定密钥生成器KeyGen，并假设伪随机函数ϕ，那么可以使用函数F_Gen-Dec安全地解密.假设敌手是静态且被动的，在协议开始时就选取要收买的参与者，且被收买参与者的数目少于k个.

为证明(协议)安全性，需要构建一个工作在理想函数F_Gen-Dec之上的仿真器S，以至于敌手(将敌手定义为A)使用密钥生成器KeyGen无法区分出是处在具有理想函数的仿真器中还是处在真实环境的协议里.

这里需说明，仅通过使用理想函数F_Gen-Dec就可以仿真在真实协议中的一切，通过这种方式使敌手以可忽略的概率区分其不同.

另外可以知道，被动攻击者只是窃听参与者的输入输出，但是参与者还是按照协议规定的程序执行规定的程序；如果攻击者在协议一开始就确定买通任意的一组参与者(数量有一定限制)作为恶意被收买参与者，在协议执行以后就不再改变，则称这种攻击者是静态攻击者.定义的攻击者是静态被动攻击者.

1) 仿真密钥生成协议

定义集合B={被A收买的参与者}.

① 在真实协议中，敌手A将被收买的参与者选取的私钥发送给密钥生成器KeyGen.

② 当所有的参与者准备好时，诚实参与者的密钥生成器KeyGen使用拉格朗日插值(对从敌手A获得的共享份额和密钥生成器KeyGen随机选取的私钥)来计算秘密共享.密钥生成器KeyGen同样也计算公钥和需要的K_A值.

③ 密钥生成器KeyGen首先将公钥发送给所有的参与者、client及敌手A，然后发送给正确的参与者私钥共享和K_A值.

现在假设使用仿真器S替代敌手A与理想协议通信.

① 敌手A将从被收买参与者中选取的私钥发送给仿真器S，仿真器S继而将这个共享传递给理想函数F_Gen-Dec，而理想函数F_Gen-Dec充当密钥生成器KeyGen功能，并选取私钥进而计算公钥.

② 理想函数F_Gen-Dec发送公钥给client、所有的参与者，也包括仿真器S和敌手A.这里，仿真器S去仿真诚实参与者被认为具有的秘密共享，只需在Z_q^n×l中选取全0矩阵.仿真器S同样随机选取被收买的参与者，希望取回K_A值.

③ 仿真器S发送给被收买的参与者和敌手恰当的K_A值以及起初被收买的参与者发送给仿真器S的相同私钥共享.

2) 仿真解密协议

当client想要在真实协议下解密时，它将密文(c₀, c₁)发送给所有的参与者，在收到参与者的解密共享后，对其执行拉格朗日插值并获得明文u′进而获得明文u.

① 在理想环境下，client发送密文给理想函数F_Gen-Dec，之后发送密文给所有的参与者及敌手A和仿真器S.

② 理想函数F_Gen-Dec发送明文u.然而，由UC-仿真定义可以看出，敌手A是该环境的一部分，所以需要假设敌手能够看到client和诚实参与者之间的通信，因此，为证明安全性，需仿真该通信.故仿真器S的工作是仿真诚实参与者发送的解密共享，即给定一个解密共享r^ϕ+e′=(r_i^ϕ+e′_i)_i=1^l，其中，i∈[0, 1]，故e_i′=$\left\lfloor {\frac{q}{t}{\mu _i}} \right\rceil$+x₂-E_i^Tx₁的共享.

③ 对于r_i^ϕ，仿真器S形成y_i值作为ϕ_KA(c₀, c₁[i])的和，敌手A知道在$[-\sqrt{q}, \sqrt{q}]$间的一个均匀随机值，但不知道每一个K_A值.对于所有参与恢复秘密份额的参与者，即可以得到向量y.使用y+u′=$\left(y_{i}+\left\lfloor {\frac{q}{t} \mu_{i}} \right\rceil\right)_{i=1}^{l}$替换会在真实协议中被泄露的向量

$\begin{array}{l} {\mathit{\boldsymbol{r}}^\phi } + {\mathit{\boldsymbol{e}}^\prime } = {\mathit{\boldsymbol{r}}^\phi } + \underbrace {\left( {{\mathit{\boldsymbol{x}}_2} - {\mathit{\boldsymbol{E}}^{\rm{T}}}{\mathit{\boldsymbol{x}}_1}} \right) + {\mathit{\boldsymbol{u}}^\prime }}_{{e^\prime }} = \\ \left( {r_i^\phi + {x_{2i}} - \mathit{\boldsymbol{E}}_i^{\rm{T}}{x_{1i}} + \left\lfloor {\frac{q}{t}{v_i}} \right\rceil} \right)_{i = 1}^l \end{array} $

即在使用f^-1(·)前可得到明文.为简单起见，这里记ee:=(x₂-E^Tx₁).

④ 仿真器S计算被收买参与者发送的解密共享，使用步骤1)中的私钥共享.仿真器S使用拉格朗日插值计算多项式次数至多为k的多项式q_i(x)_i=1^l，包括q_i(0)_i=1^l=y_i+$\left\lfloor {\frac{q}{t}{v_i}} \right\rceil$和被收买参与者的解密共享.之后仿真器S利用这些多项式去计算诚实参与者的仿真共享.

定理3 对于任意的敌手A，存在一个仿真器S，对于任意的环境机M，不能区分真实的解密协议与仿真协议.

该定理可归结为证明能够恢复加密明文的解密协议，即真实协议与仿真解密共享分布的仿真协议是计算不可区分的.

证明 在密钥生成协议中，私钥共享在真实协议和理想协议下以相同的方式分布，显然这种情形下K_A值均为均匀选取.

注意到在真实协议和仿真协议中，可以确定密钥生成过程中发送的信息在解密步骤中被泄露共享，分别在理想协议向量y+u′和真实协议使用的r^ϕ+(x₂-E^Tx₁)+u′中，敌手A对这些值是计算不可区分的.

对此，注意到在真实的协议中并没有给敌手A所有的K_A值，所以通过使用伪随机函数ϕ和构造的向量y，在敌手A看来，y+u′与r^ϕ+(x₂-E^Tx₁)+u′计算不可区分.

由于每一个y_i至少包含在一个均匀值和为$2 \sqrt{q}$，指数大于每一个ee_i(ee:=(x₂-E^Tx₁))分布的区间$[-\sqrt[3]{q}, \sqrt[3]{q}]$中，因此可以发现y+u′与y+(x₂-E^Tx₁)+u′是统计不可区分的.

最后，在仿真协议中，将会输出构造正确的解密向量.

4 结束语

在Bendlin等^[1]的基础上，构造了基于GPV方案的门限公钥加密方案.门限密码的实质是引入一个可信第三方来执行密钥生成分发，并给出一个分布式解密协议，使之能够抵抗相对弱的被动敌手攻击，但不能够抵抗主动攻击.直接使用文献[1]方案的结果，可以推广得到抵抗强敌手的单比特门限加密方案.另外，非交互性和健壮性是门限密码系统需要的，方案对比如表 1所示.

健壮性问题并没有解决.在下一步工作中，将引入可验证加密机制，使委托者能够验证解密服务器发送的是有效还是无效的部分解密共享，从而健全所构造的多比特门限密码方案的健壮性.此外，基于容错学习问题构造全同态加密方案是当前公钥密码学领域研究的另外一个热点问题，但现有的全同态加密方案多集中在方案的优化效率的提升上，构造基于门限的全同态加密方案相对较少.提出的方案可以很容易地推广到基于门限的全同态加密方案，这也是下一步的主要工作^[13].