一类新的秘密共享方案安全性分析及其改进

庄锋茂，胡慧丹，林昌露

（1.福建体育职业技术学院 公共基础部，福建 福州 350003;2.福建师范大学 数学与信息学院，福建 福州 350117）

1979年，Shamir[1]利用拉格朗日插值多项式提出了（t，n）-门限的秘密共享方案.在该方案中，一个诚实的第三方将秘密拆分成n份共享,并将每一份共享秘密地分发给n位不同的参与者；其中，任意t个或大于t个参与者的合作能重构出秘密（正确性），而任意小于t个参与者的合作得不到关于秘密的任何消息（隐私性）.同年,Blakley[2]借助几何的方法提出了不同的秘密共享方案.1983年，Mignotte[3]和Asmuth-Bloom[4]借助中国剩余定理提出了新的门限秘密共享方案.

为了丰富秘密共享方案，许多的学者利用不同的数学工具，如：二进制序列，格，二元对称多项式，双线性映射，等等，分别地提出了各种秘密共享方案[5-9]，以满足不同的应用需求.2017年,Deepika和Sreekumar[10]基于格雷码和异或运算提出了一类新的秘密共享方案.其中利用格雷码技术实现秘密分发，而用异或运算实现安全的秘密重构.作者称该方案无信息丢失且可应用于视觉密码学中.显然，参与者仅仅需要进行异或运算就能还原出秘密，与传统的其他方案比较，该方按可大量地减少了参与者的计算量.通过详细的安全性分析发现，该方案存在安全漏洞并给出了具体的攻击方式，进而给出了一个改进的安全方案.在改进方案中，我们在共享生成阶段添加了随机值用以破坏共享之间的关联性；通过一些公开值实现了方案的正确性.

1 预备知识

1.1 格雷码

格雷码是一类循环二进制单位距离码，它是任意两个相邻的码字只有一位二进制数不同的编码,它与奇偶校验码同属可靠性编码.

1.2 异或运算

异或也叫半加运算，其运算法则相当于不带进位的二进制加法，二进制下1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=0⊕1=1，1⊕1=1.

1.3 二进制码转换成格雷码

二进制码转换成格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法类似.例如：

某二进制数为：Bn-1Bn-2…B2B1B0

其对应的格雷码为：Gn-1Gn-2…G2G1G0

具体地，最高位保留Gn-1=Bn-1，其他各位数Gi=Bi+1⊕Bi，其中 i=0，1，…，n-2.

2 Deepika-Sreekumar的秘密共享方案

Deepika和Sreekumar[10]借助格雷码与异或运算提出一类新的秘密共享方案，该方案不同于基于多项式的秘密共享方案和基于中国剩余定理的秘密共享方案.该方案利用简单的异或运算实现了秘密的重构，这可大量地减低了每位参与用户的计算量.本节主要简要回顾Deepika-Sreekumar的秘密共享方案.具体地，Deepika和Sreekumar给出了该类型秘密共享方案的两种构造：一种是（7,7）-门限秘密共享方案，即只有7个参与者都拿出他们的共享才能重构出秘密；另一种是（3,7）-门限秘密共享方案，即仅有三个特定的参与者就可还原秘密.这两种情形的秘密共享方案的共享的生成算法是一样的，但是它们的秘密恢复算法不一样.具体步骤如下所示.

2.1 共享的生成算法

第一步：输入主秘密S，将S转化为二进制数.

第二步：将秘密S转化成它所对应的格雷码G.

第二步：计算共享S1，S1=G；将秘密S1转化成它所对应的格雷码G1.

第三步：计算共享S2，S2=G1；将秘密S2转化成它所对应的格雷码G2.

第四步：计算共享S3，S3=G2；将秘密S3转化成它所对应的格雷码G3.

第五步：计算共享S4，S4=G3；将秘密S4转化成它所对应的格雷码G4.

第六步：计算共享S5，S5=G4；将秘密S5转化成它所对应的格雷码G5.

第七步：计算共享S6，S6=G5；将秘密S6转化成它所对应的格雷码G6.

第八步：计算共享S7，S7=G6

第九步：将二进制 S1，S2，S3，S4，S5，S6，S7转化为十进，输出十进制的 7 个共享 S1，S2，S3，S4，S5，S6，S7，并秘密地分发给7位不同的参与者.

2.2 （3，7）-门限秘密共享方案的重构算法

1）第一阶段

第一步：输入 S1，S2，S3，S4，S5，S6，S7.

第二步：判定共享的下标i是否整除2；如果i-2=0，则Si是授权集里的共享；否则Si不是授权集里的共享.

第三步：输出共享 S2，S4，S6.

2）第二阶段

第一步：输入 S2，S4，S6,并将 S2，S4，S6转化为二进制数.

第二步：计算S2⊕S4⊕S6.

第三步：将M转化为十进制数.

第四步：输出秘密S=M.

2.3 （7，7）-门限秘密共享方案的重构算法

第一步：输入 S1，S2，S3，S4，S5，S6，S7，并将 S1，S2，S3，S4，S5，S6，S7转化为二进制数.

第二步：计算 S1⊕S2⊕S3⊕S4⊕S5⊕S6⊕S7=M.

第三步：将M转化为十进制数.

第四步：输出秘密S=M.

3 安全漏洞分析

本节将通过具体实例来阐述Deepika和Sreekumar提出的两种情形的门限秘密共享方案存在严重的安全漏洞.将指出它们无法满足门限秘密共享方案的最基本的隐私性与正确性要求.不失一般性,假设秘密S=860，通过执行“共享的生成算法”得到秘密S的二进制形式S=1101011100，以及7个共享：S1=1011110010，S2=1110011011，S3=1001010110，S4=1101111101，S5=1011010011，S6=1110111010，S7=1001110111.

3.1 隐私性分析

将分析 Deepika 和 Sreekumar设计的 （3，7）-门限秘密共享方案与（7，7）-门限秘密共享方案均无法确保其隐私性：1）每个参与者利用所持有的一个共享都可以恢复秘密；2）参与者能获得其他参与者的共享.

3.1.1 参与者P1利用S1得到秘密S

参与者P1可通过执行以下的两个步骤成功地获得秘密.

第一步：P1可以得到S的格雷码G=S1=1011110010.

第二步：设 S=B9B8B7B6B5B4B3B2B1B0，G=G9G8G7G6G5G4G3G2G1G0,其中 B9=G9=1,B8=B9⊕G8=1⊕0=1，B7=B8⊕G7=1⊕1=0，B6=B7⊕G6=0⊕1=1，B5=B6⊕G5=1⊕1=0，B4=B5⊕G4=0⊕1=1，B3=B4⊕G3=1⊕0=1，B2=B3⊕G2=1⊕0=1，B1=B2⊕G1=1⊕1=0，B0=B1⊕G0=0⊕0=0， 易知，参

与者P1通过以上计算可获得秘密S.

3.1.2 参与者Pi获得其他参与者Pj的共享

参与者Pii=（2,3,…,7）不仅能得到秘密S，还能得到其他参与者Pj（j＜i）的共享.具体地，参与者 Pii=（2,3,…,7）通过以下的步骤成功地获得其他参与者Pj（j＜i）的共享，且可恢复出秘密.

第一步：Pi可以获得Pi-1的共享Si-1的格雷码Gi-1=Si.

第三步：Pi重复的执行i-1次步骤1,2即可得到Si-2,Si-3,…,S1,S，并可正确地恢复出秘密S.

3.2 正确性分析

本节仅对Deepika和Sreekumar提出的 （3,7）-门限秘密共享方案不满足正确性要求给出详细的分析.即该方案不满足任意3个或大于3个参与者能正确地恢复秘密；小于3个参与者无法还原秘密.由于（7,7）-门限秘密共享方案中7个参与者全部参与能还原出秘密，因此 Deepika和 Sreekumar提出的（7,7）-门限秘密共享方案满足正确性.通过以下例子说明（3,7）-门限秘密共享存在的缺陷，具体步骤如下所示：

设参与者P1,P2,P3去重构秘密，参与者P1,P2,P3利用所得到的三个共享S1=1011110010，S2=1110011011，和S3=1001010110进行异或运算去还原秘密.首先对S1和S2进行异或运算得结果m1=S1⊕S2=1011110010⊕1110011011=0101101001，然后再将m1和S3进行异或运算得到结果m2=m1⊕S3=0101101001⊕1001010110=11001111111.我们发现通过共享，S1,S2和S3所得到的结果m2≠S.具体的重构秘密的运算过程如下所示.

设参与者P1,P2,P4,P6去重构秘密,参与者P1,P2,P4,P6利用所得到的四个共享 S1=1011110010，S2=1110011011，S4=1101111101 和 S6=1110111010 执行重构算法去还原秘密.首先需要对S1=1011110010和S2=1110011011执行异或运算得到结果m3=S1⊕S2=0101101001，然后再对 m3=101101001和S4=1101111101执行异或运算得到结果 m4=m3⊕S4=1000010100，最后计算 m4⊕S6得到结果 m6=0110101110.我们发现通过共享 S1，S2，S4和 S6所得到的结果m5≠S.具体的运算过程如下所示.

通过以上的两个例子说明Deepika和Sreekumar所提出的（3,7）-门限秘密共享方案无法满足任意的三个或大于三个参与者都能还原出真正的秘密这个性质.

4 方案改进

本节将改进Deepika和Sreekumar的秘密共享方案，仅对提出（3,7）-门限秘密共享方案的给出具体的改进.在改进的方案中，在重构阶段也仅只需要做异或运算，且满足正确性和隐私性.该改进方案的共享生成算法和秘密恢复算法分别描述如下.

4.1 共享生成算法

第一步：可信第三方执行第2.1节中“生成算法”过程中将秘密 S 生成 7 个伪共享 S1，S2，S3，S4，S5，S6，S7.

第二步：第三方任意的选择7个随机值K1，K2，K3，K4，K5，K6，K7, 将 K1， K2，K3，K4，K5，K6，K7, 转化为二进制数,再计算共享 Y1=S1⊕K1，Y2=S2⊕K2，Y3=S3⊕K3，Y4=S4⊕K4，Y5=S5⊕K5，Y6=S6⊕K6，Y7=S7⊕K7.

第三步：第三方计算公开值Ai1i2i3.具体地，Ai1i2i3=Yi1⊕Yi2⊕Yi3⊕S，其中这里 S 为秘密且｛i1,i2,i3｝是{1,2,…,7}的任意3元子集，公开哈希值H（S），其中H为安全的哈希函数.

第四步： 第三方通过安全的信道将 Y1，Y2，Y3，Y4，Y5，Y6，Y7传输给参与者 U1，U2，U3，U4，U5，U6，U7.

4.2 秘密重构算法

假设任意三位参与者Ui1,Ui2,Ui3重构秘密S,利用公开值Ai1i2i3和三个共享Yi1,Yi2,Yi3即可计算秘密.

5 安全性分析

本节将通过两个定理来论证改进的秘密共享方案满足正确性和隐私性要求.

定理 1（正确性）：在改进方案中，任意3个或大于3个的参与者利用手中的共享执行秘密重构算法可以重构出正确的秘密.

定理2（隐私性）：在改进的方案中，小于3个参与者利用手中的共享执行秘密重构算法无法恢复秘密.

证明：不失一般性，假定参与者U1,U2拟重构秘密S.由于参与者U1,U2只有共享Y1,Y2但没有公开值A1,2，因此参与者无法利用公开值A1,2执行秘密重构算法，这使得秘密重构算法无法正确的计算Y1⊕Y2⊕A1,2并恢复正确的秘密.此外，参与者U1或U2各自均无法通过公开值或自己的共享份额计算得到其他参与者的共享.其原因是，他们各自的共享中包含了一个随机值，即Y1=S1⊕K1和Y2=S2⊕K2中分别含有随机值K1和K2，且这随机值只有分发者知道，而任何一个参与者不仅不知道与自己共享相关的随机值，而且无法预测得到与其他参与者相关的那个随机值的任何信息.

6 总结

本文对Deepika和Sreekumar所提出的两种秘密共享方案给出了具体的安全性分析.分析结果表明：他们所提出的方案中每个参与者仅仅通过自己的共享可以还原秘密，同时还能得到其他参与者的共享，即无法达到隐私性.同时通过两个具体的例子说明他们设计的（3,7）-门限的秘密共享方案无法保证正确性.最后，本文对（3,7）-门限的秘密共享方案给出了的一种改进的方案，并确保了改进的方案能达到秘密共享的隐私性及正确性.