可验证的Asmuth-Bloom秘密共享方案

于 洋，刘焕平

(哈尔滨师范大学)

0 引言

秘密共享方案是信息安全与数据保密的重要手段，在一个秘密共享方案中，只有授权的参与者集合才可以恢复秘密 ，而非授权集合中的成员则得不到关于秘密S的任何信息.1979年，Shamir和Blakley分别基于Lagrange插值法和多维点空间的性质提出了(t，n)门限秘密共享概念.1983年Asmuth和Bloom基于中国剩余定理和模数运算提出Asmuth-Bloom门限方案，其构造新颖，设计简明.但是，在实际应用之后，会带来三个问题(1)能否通过公共信道传输，使其在应用上更具有可行性，减少成本，提高使用价值(2)能否有效防止分发者的欺骗行为(3)能否有效检测参与者之间的欺骗行为.

该文构造了一种可验证的Asmuth-Bloom门限秘密共享方案，该方案中，秘密份额由秘密分发者和参与者协同产生，不仅能防止秘密分发者的欺骗，而且能够检测参与者之间的相互欺诈，并通过公共信道发送秘密数据和秘密份额.

1 Asmuth-Bloom秘密共享方案

1.1 准备工作

设秘密分发者为D，n个参与者的集合P={P1，P2，…，Pn}门限值为 t，共享秘密为 S，D 选取大素数p(p＞S)，n个正整数序列m=(m1，m2，…，mn)满足如下条件:

1.2 秘密份额分发

D 计算 x=S+Ap，xi=x(mod mi)(i=1，2，…，n)，将(xi，mi)作为秘密份额秘密发给参与者 Pi(i=1，2，…，n)

1.3 秘密恢复

t个参与者交换各自秘密份额后，应用中国剩余定理解得唯一的x，则S=x(modp).

2 可验证的Asmuth-Bloom秘密共享方案

2.1 方案初始化

设秘密分发者为D，n个参与者的集合P={P1，P2，…，Pn}，门限值为 t，共享秘密为 S，D 选取大素数p(p＞S)，整数A，n个正整数序列m=(m1，m2，…，mn)，p，A，m满足Asmuth-Bloom 秘密共享方案条件.在有限域Zp上选取一生成元g，使得Zp中计算以g为底的离散对数困难.D任选取一随机数c∈Zp，计算y=gc(modp)，D以c作为私钥.参与者Pi(i=1，2，…，n)分别为自己选取一个整数 si∈ Zp(i=1，2，…，n)，满足(si，p-1)=1(i=1，2，…，n)，Pi计算ai=gsi发给D(i=1，2，…，n)，D 将(p，g，y，m，ai)(i=1，2，…，n)公布在公告板上.

2.2 秘密份额及验证信息的产生

D计算秘密数据X=S+Ap，将X随机分解为 n个不为0的正整数 X1，X2，…，Xn之和，即X=X1+X2+…+Xn.

(1)D计算bi=Xi*(i=1，2，…，n)将其公布在公告板上，参与者Pi(i=1，2，…，n)在公告板上读取 bi(i=1，2，…，n).

(2)参与者Pi产生秘密份额，并通过公共信道向 Pj(j≠ i，j=1，2，…，n)发送秘密数据参与者 Pi在公告板上读取 bi(i=1，2，…，n)，计算Xi=bi*(ysi)-1(i=1，2，…，n)，再计算 aij=Xi(mod mj)(j=1，2，…，n)，Pi将 aii保留，然后Pi计算 bij=aij*发给 Pj(j≠ i，j=1，2，…，n)，Pj收到 bij计算 aij=bij*()-1.

(3)防止参与者的欺骗，Pi(i=1，2，…，n)计算验证信息:

Pi(i=1，2，…，n)将αi、βij通过公共信道传输给分发者D，D在公告板上公开αi，βij.

(4)完成上述过程后，参与者Pi(i=1，2，…，n)的秘密份额为 Si={aji|j=1，2，…，n}.

2.3 秘密份额的验证

恢复秘密前，t个参与者集合在一起交换秘密份额，不失一般性，设 t个参与者为{P1，P2，…，Pt}.为防止参与者之间的欺骗行为，参与者Pk收到参与者Pj的秘密份额Sj后，对其中n个分量aij进行验证，验证公式如下:

若上式成立，则秘密份额Sj有效;否则Sj无效，即Pj提供了假的秘密份额.

2.4 秘密的恢复

t个参与者集合在一起交换并验证各自的秘密份额后，任意参与者Pi(i=1，2，…，n)拥有了t个秘密份额:

然后建立n个同余方程组如下:

(2)根据中国剩余定理求解这n个方程组可得唯一的 X1，X2，…，Xn，计算X=X1+X2+ … +Xn，再由式X=S+Ap即可解得共享秘密S=X(mod p).

3 方案分析

3.1 方案正确性分析

(1)验证式(2-1)的正确性

参与者 Pi(i=1，2，…，n)在把 aij发送给Pj(j≠i)的同时，Pi(i=1，2，…，n)通过公共信道将αi、βij传输给分发者D，D在公告板上公开αi、βij，Pj(j≠i)，根据式(1)可验证aij的真实性.

故验证式(1)是正确的.

(2)秘密恢复的正确性.

参与者集合P中前t个参与者{P1，P2，…，Pt}恢复秘密时:由于S＜p，故X=S+Ap＜p+Ap=(A+1)p.

当参与者集合P中任意t个参与者恢复秘密时，令N'表示m中任意t个数的乘积，可知:N ＜N'，所以Xi＜X ＜N ＜N'.

P中任意t个参与者交换各自的秘密份额后，建立形如式(2)的n个同余方程组，根据中国剩余定理也可解得唯一的Xi(i=1，2，…，n)，因此任意t个参与者能恢复共享秘密S.

3.2 方案安全性分析

(1)防止秘密分发者D的欺骗

该方案的秘密份额是由秘密分发者D和参与者集合 P={P1，P2，…，Pn}协同产生，能够有效防止D的欺骗.

D将包含共享秘密S的秘密数据X分解为X=X1+X2+… +Xk+… +Xn，然后D计算将其公布在公告板上，参与者 Pi(i=1，2，…，n)在公告板上读取bi(i=1，2，…，n).假设D伪造的秘密数据，然后计算=，将公布在公告板上.那么Pk在秘密份额的产生过程中首先在公告板读取，然后计算:

(j=1，2，…，n)，Pk计算 bkj=akj*发送给Pj(j≠k)，Pj收到bkj计算akj=bkj*()-1.t个参与者{P1，P2，…，Pt}集合在一起交换各自的秘密份额后，建立形如式(2)的n个方程组，其中关于Xk的方程组变为:

由于该方程组无法计算出Xk，因此无法计算出X和共享秘密S，所以任何参与者无法恢复出S.由以上分析可知，若D向任意一个参与者发送假的秘密数据，则导致其他所有参与者无法恢复共享秘密，因此，D的欺骗行为没有任何意义，从而保证了本方案的公正性.

(2)识别参与者之间的相互欺骗

任意t个参与者在恢复秘密之前集合在一起交换各自的秘密份额.参与者Pk收到其他参与者Pj的秘密份额Sj后，通过式(1)验证Sj中n个分量的正确性，若Pj提供假的秘密份额，将被检测出来.因此，本方案能够识别参与者之间的欺骗行为.

(3)验证过程是安全的

首先本方案在由分发者D公布秘密数据时，Pi发送ai给D，根据ai求得si属于离散对数求解困难问题，因此ai是安全的.D将bi公布在公告板上，根据bi求得Xi属于离散对数求解困难问题，因此bi是安全的.故秘密数据 Xi(i=1，2，…，n)是安全的.其次本方案在参与者之间互相交换时，同理，发送秘密份额也是安全的.最后在验证参与者交换的秘密份额是否正确时，每个参与者Pi发送给D验证信息αi=gXi(mod p)和βij=gkij(modp)，根据αi求得Xi属于离散对数求解困难问题，因此αi是安全的，同理，kij也是安全的.所以验证过程式安全的.

(4)若再次分发秘密S'，分发者的私钥c以及每个参与者Pi的秘密数据si(i=1，2，…，n)皆可重复使用，提高了秘密共享的实用性及价值.

4 结束语

基于中国剩余定理，结合模运算性质提出了一种可验证的门限秘密共享方案，该方案能够不仅可以通过公共信道传输秘密数据和秘密份额，并且还有效地防止秘密分发者的欺骗并识别参与者之间的欺诈行为，其验证过程的安全性基于离散对数的难解性.本方案中，秘密分发者D的欺骗行为将导致任何参与者均无法恢复秘密，因此，D的欺骗行为没有任何意义.在恢复秘密时，t个参与者集合在一起交换各自的秘密份额后，能够通过验证式(1)识别任一参与者的欺诈行为.方案利用模运算的相关性质验证秘密份额的有效性，验证过程简单、高效，并且再次分发秘密时，参与者与分发者的私钥也可重复使用，更加提高了该秘密共享方案的实用价值.

［1］ Shamir A.How to share a secret［J］.Communication of the ACM，1979，22(11):612-613.

［2］ Blakley G R.Safeguarding cryptographic key［A］.Proceedings of AFIPS，1979 National Computer Conference［C］.New York:AFIPS，1979，48:313-317.

［3］ Asmuth C A ，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory IT-29，1983，208–210.

［4］ Ore O.The general Chinese remainder theorem［J］.American Mathematical Monthly，1952:9:365–370.

［5］ 唐春明，刘卓军，王明生.一种实用的可验证秘密共享方案.计算机工程与应用2006，15:129-133.

［6］ 庞辽军，李慧贤，王育民.可验证的(t，n)门限秘密共享方案及其安全性.华南理工大学学报:自然科学版，2007，35(1):102-105.

［7］ Mignotte M.How to share a secret?［J］In:Proc.of the Workshop on Cryptography，Springer.Heidelberg，1983:371–375.