A Publicly Verifiable Multiple Secret Sharing Threshold Scheme

定义 1(拉格朗日插值多项式)  设(x₀，y₀)，(x₁，y₁)，…，(x_t-1，y_t-1)是二维平面上任意给定的t个点的坐标，则有且仅有一个与这t个点的坐标对应的t-1次多项式p(x)，满足p(x_i)=y_i，0≤i＜t.

p(x)可以通过下面的公式计算得到：

身份识别的目的是使某人的身份被确认. 下面介绍Schnorr身份认证方案，该方案需要一个可信第三方发放证书和选择系统参数.

定义 2(Schnorr身份认证方案)  设p是一个大素数，α是Z_p^*中的一个元素，阶q＞2^t，t是安全参数，则对任意的β∈〈α〉，有0≤log_αβ≤q-1，参数p，q，α，t是公开的. 系统中的每个用户选择自己的私钥a，0≤a≤q-1，并计算相应的公钥ν=α^-amodp.

(i) Alice随机选择一个整数k，0≤k≤q-1，计算γ=α^kmodp. Alice传送Cret_Alice和γ给Bob.

(ii) Bob利用证书Cret_Alice验证Alice的公钥ν. Bob随机选择一个整数r，1≤r≤2^t，并传送r给Alice.

(iii) Alice计算y=k+armodq，并传送y给Bob.

(iv) Bob验证y≡α^yν^rmodp. 如果成立，Bob“接受”；否则，Bob“拒绝”.

下面的同余式成立说明Alice能够向Bob证明自己的身份

在上述的方案中需要证明者和验证者交互才能证实证明者的身份，显然满足不了本文所构造方案中非交互身份认证的需求，因此建立了一个非交互的身份认证方案.

定义 2(非交互身份认证方案)  设p是一个大素数，g₁，g₂是Z_p的两个生成元，hash()是一个安全的密码学Hash函数. 假设某证明者拥有私钥α，记h₁=g₁^α，h₂=g₂^α.

(i) 证明者任选w∈_RZ_q，然后计算a₁=g₁^w，a₂=g₂^w，c=hash(h₁，h₂，a₁，a₂)，r=w-cαmodq；

(ii) 证明者用(c，r)应答；

(iii) 验证者计算a₁=g₁^rh₁^c和a₂=g₂^rh₂^c，c^′=hash(h₁，h₂，a₁，a₂). 检查c=c^′是否成立.

验证通过，则证明者拥有私钥α，使得h₁=g₁^α，h₂=g₂^α成立.

设P={P₁，P₂，…，P_n}是n个参与者的集合，Dealer是秘密分发者. 该方案在系统中需要一个公告牌，只有Dealer可以修改、更新公告牌上的内容，其他人只能阅读和下载. hash()是一个安全的密码学Hash函数.

方案运行前做以下准备工作，设g是q阶群G_q的生成元，q是一个素数，使得在Z_q^*上的离散对数问题是难解的. 参与者P_i选择自己的私钥x_i∈_RZ_q^*(x_i互不相同)，并在系统中注册y_i=g^x_imodq作为自己的公钥，i=1，2，…，n.

1) 秘密份额分发

(i) Dealer选择一个t-1次的多项式

Dealer保存p(x)，在公告牌上发布相关系数C_i=g^α_imodq，i=0，1，…，t-1.

(ii) Dealer计算份额Y_i=y_i^p(i)modq，设${{X}_{i}}=\prod\limits_{j=1}^{t-1}{C_{j}^{{{i}^{j}}}}\bmod q$. Dealer要为每一个p(i)产生一个承诺，满足X_i=g^p(i)modq，Y_i=y_i^p(i)modq，i=1，2，…，n. 承诺中包含挑战c_i和应答r_i以及子秘密密文d_i，具体步骤如下：Dealer选取w_i∈_R Z_q，计算a_1i=g^w_imodq，a_2i=y_i^w_imodq，c_i=hash(X_i，Y_i，a_1i，a_2i)，r_i=(w_i-c_ip(i))modq，d_i=p(i)a_2imodq. Dealer在公告牌上发布Y_i及其对应的承诺(c_i，r_i，d_i)，i=1，2，…，n.

2) 秘密份额的验证

验证者运行非交互式认证协议. 验证者首先计算${{X}_{i}}=\prod\limits_{j=1}^{t-1}{C_{j}^{{{i}^{j}}}}\bmod q$，然后以g，X_i，y_i，Y_i，c_i，r_i为输入，计算a_1i=g^r_iX_i^c_imodq，a_2i=y_i^r_iY_i^c_imodq，接下来检验c_i^′=hash(X_i，Y_i，a_1i，a_2i)是否与承诺c_i相等. 若相等，接收；否则，拒绝.

设K={K₁，K₂，…，K_r}是共享的秘密集，Dealer随机选取m_j∈_R Z_q^*，j=1，2，…，r，其中m_j和K_j对应. 为了使n个参与者中任意t个及t个以上的参与者能够重构K_j，Dealer计算T_j=(K_j-m_j^lα₀)modq，其中l=n!. Dealer在公告牌上公布(T_j，m_j).

1) 秘密份额解密

不失一般性，假设一个最小授权子集A={P₁，P₂，…，P_t}. P_i验证Y_i对应的承诺通过之后，计算a_1i与d_i的乘积即可得到p(i). 因为a_1i=g^w_imodq，d_i=p(i)a_2imodq，a_2i=y_i^w_imodq，y_i=g^x_imodq，所以

然后计算S_ij=m_j^p(i)modq. 此时有g^p(i)=X_imodq，m_j^p(i)=S_ijmodq，P_i对解密得到的S_ij产生一个承诺，具体步骤如下：P_i随机选取v_i∈_R Z_q，计算b_1i=g^v_imodq，a_2i=m_j^v_imodq，e_i=hash(y_i，S_ij，b_1i，b_2i)，μ_i=(v_i-e_ip(i))modq. P_i把(m_j，S_ij)及其对应的承诺(e_i，μ_i)，i=1，2，…，t，发送给指定解密者B，解密者可以是系统中的某个参与者，也可以是其他人.

2) 联合解密

解密者B要对收到可行集合A中参与者发送的秘密份额进行验证. 首先，以g，X_i，m_j，S_ij，e_i，μ_i为输入，计算b_1i=g^μ_iX_i^e_imodq，b_2i=m_j^μ_iS_ij^e_imodq，然后检验e_i^′=hash(g，S_ij，b_1i，b_2i)是否与承诺中的e_i相等，i=1，2，…，t. 若相等，接收；否则，拒绝并停止解密. 若验证都通过，B利用收到的解密份额恢复秘密：取l=n!，在整数环Z上计算拉格朗日系数

B可以计算

从而K_j=(T_j-m_j^lα₀)modq，j=1，2，…，r. 若Dealer想在参与者集P中共享新的秘密K_r+1，则只需要重新选择m_r+1∈_R Z_q^*，计算T_r+1=K_r+1-m_r+1^lα₀，在公告牌上发布(T_r+1，m_r+1)即可.

Shamir门限方案共享一次秘密之后就会暴露插值多项式的系数，因此不能继续使用该多项式共享新的秘密. 若Dealer要共享新的秘密，则只能重新构造多项式. 一个直观的思想就是隐藏插值多项式的系数，本方案采用的思想是找一个计算离散对数困难的群Z_q^*，计算参数C_i=g^α_i，而攻击者在知道g和C_i的情况下是无法计算插值系数α_i的. 下面通过两个定理来证明本方案是安全的.

定理 1  攻击者无法从Y_i或S_ij中计算得到p(i).

证  在本方案中，p(i)非常重要，需要每个参与者秘密保存. Y_i=g^p(i)modq，S_ij=m_j^p(i)modq，而在Z_q^*中计算离散对数是困难的，所以攻击者无法从Y_i或S_ij中计算得到p(i).

定理 2  若参与者数量少于门限值t则不能从T_j，m_j得到共享秘密K_j.

证  根据计算公式T_j=K_j-m_j^lα₀可知，若要计算K_j，则先要计算m_j^lα₀. 不失一般性，设1≤j≤t-1

而p(i)是一个t-1次多项式，需要t个点才能确定p(i)，所以若参与者数量少于t则无法从T_j，m_j得到共享秘密K_j.

在解密的过程中，没有直接用到p(i)，也无法从解密参数中获取p(i)，可以保证p(x)安全，所以可以用设定的参数安全共享多个秘密.

本文构造了一个可公开验证的门限多重秘密共享方案.

该方案基于拉格朗日插值多项式，且采用两次非交互的验证协议，第一次验证是为了防止Dealer作弊或信息在传递过程中受到信道中噪音的干扰而出现错误；第二次验证是检测参与解密的参与者提供的秘密份额是否为Dealer发送. 只有通过两次验证的秘密份额才能作为重构秘密的份额.

共享多个秘密的思想是将秘密和一个随机参数作二进制加法隐藏起来，只有达到或超过门限值个数的参与者联合才能计算得到这个随机参数. 共享新的秘密只需选择新的参数，因此可以共享任意多个秘密.

本文所构造的方案是将可公开验证和可共享多个秘密这两个优点相结合，是对秘密共享作了进一步研究.