1. 定义

门限密码系统由分布式密钥生成算法、加密算法、门限解密算法三部分构成，定义如下：

（1）分布式密钥生成：这是一个由参与者共同生成公钥$y$的协议，协议运行结束后，每个参与者将获得一个关于私钥$x$的碎片、对应于该碎片的公钥密钥 y i y_i yi​，以及与私钥$x$相对应的公钥$y$。

（2）加密算法：该算法的输入为公钥$y$和待加密的消息$m$，其输出为在公钥$y$下明文$m$对应的密文$c$。

（3）门限解密: 这是一个由任意$t$个参与者 P i 1 ′ , P i 2 ′ , … , P i t P_{i_1^{prime}}, P_{i_2^{prime}}, ldots, P_{i_{t}} Pi1′​​,Pi2′​​,…,Pit​​ 运行的协议, 对于给定输人密文$c$ 、$t$个公开验证密钥 h i 1 ′ , h i 2 ′ , … , h i t h_{i_1^{prime}},h_{i_2^{prime}}, ldots, h_{i_{t}} hi1′​​,hi2′​​,…,hit​​ 以及 $t$ 个碎片 x i 1 ′ x i 2 ′ , … , x i t x_{i_1^{prime}} x_{i_2^{prime}}, ldots, x_{i_{t}} xi1′​​xi2′​​,…,xit​​, 协议运行结束后将输出 密文 $c$ 和对应的明文 $m$ 。

2. 分布式ElGamal加密

系统参数: $p、q$是大素数, 且$q/p-1$, 满足 Z p Z_{p} Zp​中离散对数问题是难解的,$g$ 是 Z p ∗ Z_{p}^{*} Zp∗​的本原元,$M$ 为明文消息。

$n$个参与者 P 1 , P 2 , … , P n P_{1}, P_{2}, ldots, P_{n} P1​,P2​,…,Pn​分别选取一个随机数 x i ∈ Z p , i = 1 , 2 , … , n x_{i} in Z_{p},i=1,2, ldots, n xi​∈Zp​,i=1,2,…,n 计算 y i = g x i   m o d   p y_{i}= g^{x_{i}} bmod p yi​=gxi​modp并公布。

私钥: x = ∑ i = 1 n x i   m o d   p x=sum_{i=1}^{n} x_{i} bmod p x=i=1∑n​xi​modp公钥: y = ∏ i = 1 n y i   m o d   p = g ∑ i = 1 n x i   m o d   p = g x   m o d   p y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p y=i=1∏n​yi​modp=g∑i=1n​xi​modp=gxmodp

加密: 选取随机数 r ∈ Z p r in Z_{p} r∈Zp​, 计算 E ( M ) = ( α , β ) = ( g r   m o d   p , y r M   m o d   p ) E(M)=(alpha, beta) = (g^{r} bmod p, y^{r} M bmod p) E(M)=(α,β)=(grmodp,yrMmodp)解密: $n$个参与者首先分别计算 α x i   m o d   p alpha^{x_{i}}bmod p αxi​modp并公布, 然后共同计算出 ∏ i = 1 n α x i prod_{i=1}^{n} alpha^{x^{i}} ∏i=1n​αxi, 从而解出$M$: M = β ∏ i = 1 n α x i   m o d   p = β α ∑ i = 1 n x i   m o d   p = β α x   m o d   p M=frac{beta}{prod_{i=1}^{n} alpha^{x^{i}}} bmod p =frac{beta}{alpha^{sum_{i=1}^{n} x^{i}}} bmod p =frac{beta}{alpha^x} bmod p M=∏i=1n​αxiβ​modp=α∑i=1n​xiβ​modp=αxβ​modp

推广

令消息 M = M 1 M 2 ⋯ M n M=M_{1} M_{2} cdots M_{n} M=M1​M2​⋯Mn​, $n$个参与者 P 1 , P 2 , … , P n P_{1}, P_{2}, ldots, P_{n} P1​,P2​,…,Pn​分别对消息 M 1 , M 2 , … , M n M_{1}, M_{2}, ldots, M_{n} M1​,M2​,…,Mn​ 加密。

系统参数: $p、q$是大素数, 且$q/p-1$, 满足 Z p Z_{p} Zp​中离散对数问题是难解的,$g$ 是 Z p ∗ Z_{p}^{*} Zp∗​的本原元,$M$ 为明文消息。

利用分布式 ElGamal 加密方式产生私钥/公钥对：$n$个参与者分别选取一个随机数 x i ∈ Z p , i = 1 , 2 , … , n x_{i}in Z_{p},i=1,2, ldots,n xi​∈Zp​,i=1,2,…,n 计算 y i = g x i   m o d   p y_{i}=g^{x_{i}} bmod p yi​=gxi​modp 并公布。

私钥: x = ∑ i = 1 n x i   m o d   p x=sum_{i=1}^{n} x_{i} bmod p x=i=1∑n​xi​modp公钥: y = ∏ i = 1 n y i   m o d   p = g ∑ i = 1 n x i   m o d   p = g x   m o d   p y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p y=i=1∏n​yi​modp=g∑i=1n​xi​modp=gxmodp

加密: $n$个参与者分别选取随机数 r 1 , r 2 , … , r n ∈ Z p r_{1}, r_{2}, ldots, r_{n} in Z_{p} r1​,r2​,…,rn​∈Zp​, 对消息 M i M_{i} Mi​ 加密 E ( M i ) = ( α i , β i ) = ( g r i   m o d   p , y r i M i   m o d   p ) Eleft(M_{i}right)= left(alpha_i ,beta_iright) =(g^{r_{i}} bmod p, y^{r_{i}} M_{i} bmod p) E(Mi​)=(αi​,βi​)=(gri​modp,yri​Mi​modp)

根据同态性计算 E ( M ) = E ( M 1 M 2 ⋯ M n ) = E ( M 1 ) E ( M 2 ) ⋯ E ( M n ) = ( α , β ) E(M)=Eleft(M_{1} M_{2} cdots M_{n}right)= E(M_{1})E(M_{2}) cdots E(M_{n})= (alpha, beta) E(M)=E(M1​M2​⋯Mn​)=E(M1​)E(M2​)⋯E(Mn​)=(α,β)其中， α = ∏ i = 1 n α i = g ∑ i = 1 n r i   m o d   p , β = ∏ i = 1 n β i = y ∑ i = 1 n r i M   m o d   p alpha=prod_{i=1}^{n} alpha_{i}=g^{sum_{i=1}^{n} r_{i}} bmod p,beta = prod_{i=1}^{n} beta_{i}=y^{sum_{i=1}^{n} r_{i}} M bmod p α=i=1∏n​αi​=g∑i=1n​ri​modp,β=i=1∏n​βi​=y∑i=1n​ri​Mmodp

解密: $n$ 个参与者首先分别计算 α x i   m o d   p alpha^{x_{i}} bmod p αxi​modp 并公布, 来共同计算出 ∏ i = 1 n α x i prod_{i=1}^{n} alpha^{x_{i}} ∏i=1n​αxi​, 从而解出$M$: M = β ∏ i = 1 n α x i   m o d   p β α ∑ i = 1 n x i   m o d   p = β α x   m o d   p quad M=frac{beta}{prod_{i=1}^{n} alpha^{x_{i}}} bmod p frac{beta}{alpha^{sum_{i=1}^{n} x_{i}}} bmod p=frac{beta}{alpha^x} bmod p M=∏i=1n​αxi​β​modpα∑i=1n​xi​β​modp=αxβ​modp

3.有可信中心的门限ElGamal密码

(1) 分布式密钥生成

可信中心产生一个密钥$x$, 对应的公钥为 y = g x   m o d   p y=g^{x} bmod p y=gxmodp，使用 $(t,n)$ 门限方案在协议参与者中分享私钥$x$ : 选择随机多项式 f ( u ) = a t − 1 u t − 1 + … + a 2 u 2 + a 1 u + a 0 ∈ G F ( q ) [ u ] f(u)=a_{t-1} u^{t-1}+ldots+a_{2} u^{2}+ a_{1} u+a_{0} in G F(q)[u] f(u)=at−1​ut−1+…+a2​u2+a1​u+a0​∈GF(q)[u] P i P_{i} Pi​ 得到 x i = f ( u i ) , i = 1 , 2 , … , n x_{i}=fleft(u_{i}right), i=1,2, ldots, n xi​=f(ui​),i=1,2,…,n 。

(2) 加密

选取随机数 k ∈ Z p k in Z_{p} k∈Zp​计算： E ( M ) = ( α , β ) = ( g k   m o d   p , y k M   m o d   p ) E(M)=(alpha, beta)= (g^{k} bmod p, y^{k} M bmod p) E(M)=(α,β)=(gkmodp,ykMmodp)

(3) 解密

P i P_{i} Pi​ 计算 α i = α x i alpha_{i}=alpha^{x_{i}} αi​=αxi​并公布, 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择$t$ 个 α i 1 , α i 2 , … , α i t alpha_{i_1}, alpha_{i_2}, ldots, alpha_{i_t} αi1​​,αi2​​,…,αit​​, 则 M = β α x = β ∏ s = 1 t α i s λ i s M=frac{beta}{alpha^{x}}=frac{beta}{prod_{s=1}^{t} alpha_{i_s}^{lambda_{i_s}}} M=αxβ​=∏s=1t​αis​λis​​​β​ λ i s lambda_{i_s} λis​​ 为 Lagrange 揷值系数, 满足 x = λ i 1 x i 1 + ⋯ + λ i t x i t x=lambda_{i_1} x_{i_1}+cdots+lambda_{i_t} x_{i_t} x=λi1​​xi1​​+⋯+λit​​xit​​ .

有可信中的门限ElGamal密码不能算严格意义上的门限密码，存在第三方可心中，参加密钥分享的用户必须完全信任分发者，相信其不会对加密数据执行解密操作。

4. 无可信中心的门限ElGamal密码

（1）分布式密钥生成

每个参与者 P i P_{i} Pi​ 选择择随机数 x i x_{i} xi​ 作为私钥, 计算 y i = g x i   m o d   p y_{i}=g^{x_{i}} bmod p yi​=gxi​modp, 并公布;
每个参与者收到广播的值后, 计算公钥: y = ∏ i = 1 n y i   m o d   p = g ∑ i = 1 n x i   m o d   p = g x   m o d   p y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p y=i=1∏n​yi​modp=g∑i=1n​xi​modp=gxmodp每个参与者 P i P_{i} Pi​以秘密分发者身份执行 Feldman 的 VSS 方案, 在 P 1 , P 2 , … , P n P_{1}, P_{2}, ldots, P_{n} P1​,P2​,…,Pn​ 之间分享秘密 x i x_{i} xi​ : 选择 $t-1$ 次随机多项式, f i ( u ) = a i , t − 1 u t − 1 + … + a i 2 u 2 + a i 1 u + a i o ∈ G F ( q ) [ u ] f_{i}(u)=a_{i, t-1} u^{t-1}+ldots+a_{i 2} u^{2}+a_{i 1} u+a_{i o} in G F(q)[u] fi​(u)=ai,t−1​ut−1+…+ai2​u2+ai1​u+aio​∈GF(q)[u]其中 x i = a i 0 = f i ( 0 ) x_{i}=a_{i 0}=f_{i}(0) xi​=ai0​=fi​(0)

P i P_{i} Pi​ 计算 x i j = f i ( u j ) x_{i j}=f_{i}left(u_{j}right) xij​=fi​(uj​) , 发送给 P j , j = 1 , 2 … , n P_{j}, j=1,2 ldots, n Pj​,j=1,2…,n ; P j P_{j} Pj​ 收到其他参与者的值 x i j = f i ( u j ) , i = 1 , 2 … , n x_{i j}=f_{i}left(u_{j}right), i=1,2 ldots, n xij​=fi​(uj​),i=1,2…,n, 计算 s j = ∑ i = 1 n x i j = ∑ i = 1 n f i ( u j ) s_{j}=sum_{i=1}^{n} x_{i j}=sum_{i=1}^{n} f_{i}left(u_{j}right) sj​=∑i=1n​xij​=∑i=1n​fi​(uj​) 作为自己最终分享得到的关于私钥$x$的秘密碎片, 其验证公钥为 y j = g s j   m o d   p = g ∑ i = 1 n x i j   m o d   p y_{j}=g^{s_{j}} bmod p=g^{sum_{i=1}^{n} x_{i j}} bmod p yj​=gsj​modp=g∑i=1n​xij​modp(2) 加密

选取随机数 k ∈ Z p k in Z_{p} k∈Zp​,计算 E ( M ) = ( α , β ) = ( g k   m o d   p , y k M   m o d   p ) E(M)=(alpha, beta) =(g^{k} bmod p, y^{k} M bmod p) E(M)=(α,β)=(gkmodp,ykMmodp)(3) 门限解密

每个参与者 P i P_{i} Pi​ 计算 α i = α s i alpha_{i}=alpha^{s_{i}} αi​=αsi​ , 并公布. 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择 $t$ 个 α i 1 , α i 2 , … , α i t alpha_{i_1}, alpha_{i_2}, ldots, alpha_{i_t} αi1​​,αi2​​,…,αit​​, 则 M = β α x = β ∏ s = 1 t α i s λ i s M=frac{beta}{alpha^{x}}=frac{beta}{prod_{s=1}^{t} alpha_{i_s}^{lambda_{i_s}}} M=αxβ​=∏s=1t​αis​λis​​​β​ λ i s lambda_{i_s} λis​​ 为 Lagrange 揷值系数, 满足 x = λ i 1 s i 1 + ⋯ + λ i t s i t x=lambda_{i_1} s_{i_1}+cdots+lambda_{i_t} s_{i_t} x=λi1​​si1​​+⋯+λit​​sit​​ .