论文部分内容阅读
摘 要：文章利用Hermite插值的思想，提出了一种基于椭圆曲线的多秘密共享方案。在该方案中，可灵活的增删参与者，参与者的子秘密可以重复使用且可认证，多个主秘密能够同时被重构。所给方案能够有效抵御管理者欺骗和参与者欺骗。
关键词：Hermite插值公式；椭圆曲线；多秘密共享；椭圆曲线离散对数问题
中图分类号：TP309
秘密共享方案[1-2]就是一个秘密被分成n个子秘密，再分发给n个参与者，当任意大于或等于t个参与者合作能够恢复出该秘密。现有的秘密共享门限方案中，通常存在以下部分不足[3-4]：（1）参与者拥有的子秘密不能多次使用；（2）只能共享一个秘密；（3）无法抵御管理者欺骗；（4）无法抵御参与者欺骗。本文基于椭圆曲线密码体制和Hermite插值法提出了一种新的可验证的多秘密共享方案。该方案能够同时避免以上不足，还有参与者能够灵活增减，多个主秘密能够同时被重构出来，能识别公开信息被恶意篡改等特点。
1 方案的构造
1.1 准备阶段
设秘密的管理者为UD，S={s1，s2，…，sm}是m个需要共享的主秘密集合，U={u1，u2，…，un}是共享S中秘密的具有n个参与者的参与者组。UD生成公告牌PB用于存储公开参数。UD在有限域GF（q）（其中q为大素数）上选取一条安全的椭圆曲线：y2=x3+ax+b。选择E（Fq）上的一个基点G，G的阶为大素数N。h（x）为单向hash函数。UD把（E，G，N，h（x））放入PB中。UD在区间[1，N-1]随机选择n个不同的整数Ki（i=1，2，…，n）作为ui（i=1，2，…，n）的子秘密，并通过安全通道秘密发送给各个参与者。
因Hermite插值多项式系数与门限值t有关，因此我们针对m与t的关系分别设计方案。
1.2 m≤2t-1时的方案：
1.2.1 构造阶段
（1）UD构造一个2t-1阶多项式f（x）：
当1≤i≤m，ai=si；当m （2）计算yi=f（h（ki））和y`i=f`（h（ki））（i=1，2，…n）的值。
（3）针对多项式系数，计算检查向量M=（M1，M2，…，M2t），其中Mi=aiG（i=1，…，2t）。把M存入PB中。
（4）在椭圆曲线E（Fq）上任选一点R，计算Di（i=1，…，n）：
Di≡（yi，yi`）-kiR（modN） 公式（1）
为了参与者相互之间能检验子秘密的真伪，计算参数Ci=h（KiR）（i=1，2，…，n）。
（5）UD将点R，参数M，Di（i=1，2，…，n）和Ci=（i=1，2，…，n）放入中。
1.2.2 子秘密的验证
当参与者ui收到子秘密ki之后。通过公式（1）检验子秘密ki的有效性。
公式（2）
若公式（1）成立，则表示UD发给ui的子秘密ki是诚实的。
1.2.3 主秘密的恢复
当任意t个参与者欲恢复出主秘密结合S={s1，s2，…，sm}时，其恢复过程如下：
（1）参与者计算并提供屏蔽子秘密Wi≡KiR（modn）（i=1，2，…，t）。
（2）其他参与者验证等式Ci=h（Wi），若成立则该屏蔽子秘密是有效的。
（3）通过公式（1）及公式（2）可以验证相关公开参数的正确性，然后通过公式（yi，yi`）=（Di+Wi）（modN）计算出（yi，yi`）。
（4）由t个（yi，yi`）对，结合Hermite插值公式，即可恢复出多项式f（x）。其中前m个系数既是主秘密{s1，s2，…，sm}。
1.3 m≥2t时的方案：
1.3.1 构造阶段
（1）UD构造一个m-1阶多项式f（x）：
，其中ai=si，记为f（x）导数。
（2）计算yi=f（h（ki））和yi`=f`（h（ki））（i=1，2，…，n）的值。
（3）通过Hermite插值公式，重构m-1阶多项式f（x）。
当m为奇数时（m为偶数类似可求）：
计算Zv=f（bv）（v=1，2，…，（m+1）/2-t），Zv`=f`（bv）（v=1，2，…，（m+1）/2-t）
，并将（Zv，Zv`）（v=1，2，…，（m+1）/2-t）存入中。
（4）在椭圆曲线E（Fq）上任选一点R，放入PB，类似2.2.1（3）（4）（5）过程，计算并将M，Di（i=1，2，…，n），Ci（i=1，2，…，n）放入PB，。
1.3.2 子秘密的验证
当参与者ui收到子秘密ki之后。通过公式（3）检验子秘密ki的有效性。
公式（3）
1.3.3 主秘密的恢复
当任意t个参与者欲恢复出主秘密结合S={s1，s2，…，sm}时，其恢复过程如下：
（1）类似2.2.3（1）（2）（3）过程，求出（yi，yi`）（i=1，2，…，t）。
（2）通过下式检验（Zv，Zv`）（v=1，2，…，（m+1）/2-t）是否有效。
公式（4）
（3）参与者由t个点（yi，yi`）及（Zv，Zv`）（v=1，2，…，（m+1）/2-t），结合插值公式，可恢复出多项式f（x），从而获得了主秘密。
2 方案分析
2.1 正確性分析
公式（1）的证明过程如下，证明：由Di≡（yi，yi`）-kiR（modN）（i=1，2，…，n）知：（yi，yi`）≡（Di+kiR）（modN）（i=1，2，…，n）。假若参与者ui收到的子秘密ki正确无误。则必有：。所以：
即（2）成立。公式（3）（4）的验证过程类似。
2.2 安全性分析
攻击1：恶意者试图通过公开信息恢复主秘密mi。由Mi求ai，其中Mi=aiG，因为基于椭圆曲线离散对数问题的计算难解性，所以求不出，即无法恢复出主秘密。
攻击2：管理者欺骗。 假若管理者给参与者提供虚假的子秘密，这时参与者通过公式（2）或（3）可以验证子秘密的正确性，识别管理者的欺骗。
攻击3：参与者欺骗。在本方案中参与者如果想提供虚假屏蔽子秘密且不被其他参与者发现需通过的通过Ci=h（wi）的验证，而这难度等同找到函数的一个碰撞。
3 结束语
在本文提出的可验证多秘密共享方案中，分发者能够动态决定要共享的主秘密个数，且多个主秘密能够被同时重构出来。主秘密更新时，参与者可以反复多次使用自己的子秘密。本方案的每一个阶段，都进行了严格的论证，能有效地抵御各种形式的伪造欺骗。
参考文献
[1]Shamir A.How to share a secret[J].Communications of the ACM，1979，22（11）：612-613.
[2] Blakley G.R.Safeguarding cryptographic keys[C].Proceedings of the 1979 National computer conference，New York，June 47，1979，vol.48，AFIPS Press，313-317.
[3]吴春英，李顺东.一类特殊超图与理想秘密共享方案[J].计算机工程，2013，39（7）：205-208.
[4]张晓敏.基于线性单向函数的可验证的多秘密共享方案[J].计算机应用，2013，33（5）：1391-1393.
作者单位：湖南化工职业技术学院，湖南株洲 412000
关键词：Hermite插值公式；椭圆曲线；多秘密共享；椭圆曲线离散对数问题
中图分类号：TP309
秘密共享方案[1-2]就是一个秘密被分成n个子秘密，再分发给n个参与者，当任意大于或等于t个参与者合作能够恢复出该秘密。现有的秘密共享门限方案中，通常存在以下部分不足[3-4]：（1）参与者拥有的子秘密不能多次使用；（2）只能共享一个秘密；（3）无法抵御管理者欺骗；（4）无法抵御参与者欺骗。本文基于椭圆曲线密码体制和Hermite插值法提出了一种新的可验证的多秘密共享方案。该方案能够同时避免以上不足，还有参与者能够灵活增减，多个主秘密能够同时被重构出来，能识别公开信息被恶意篡改等特点。
1 方案的构造
1.1 准备阶段
设秘密的管理者为UD，S={s1，s2，…，sm}是m个需要共享的主秘密集合，U={u1，u2，…，un}是共享S中秘密的具有n个参与者的参与者组。UD生成公告牌PB用于存储公开参数。UD在有限域GF（q）（其中q为大素数）上选取一条安全的椭圆曲线：y2=x3+ax+b。选择E（Fq）上的一个基点G，G的阶为大素数N。h（x）为单向hash函数。UD把（E，G，N，h（x））放入PB中。UD在区间[1，N-1]随机选择n个不同的整数Ki（i=1，2，…，n）作为ui（i=1，2，…，n）的子秘密，并通过安全通道秘密发送给各个参与者。
因Hermite插值多项式系数与门限值t有关，因此我们针对m与t的关系分别设计方案。
1.2 m≤2t-1时的方案：
1.2.1 构造阶段
（1）UD构造一个2t-1阶多项式f（x）：
当1≤i≤m，ai=si；当m
（3）针对多项式系数，计算检查向量M=（M1，M2，…，M2t），其中Mi=aiG（i=1，…，2t）。把M存入PB中。
（4）在椭圆曲线E（Fq）上任选一点R，计算Di（i=1，…，n）：
Di≡（yi，yi`）-kiR（modN） 公式（1）
为了参与者相互之间能检验子秘密的真伪，计算参数Ci=h（KiR）（i=1，2，…，n）。
（5）UD将点R，参数M，Di（i=1，2，…，n）和Ci=（i=1，2，…，n）放入中。
1.2.2 子秘密的验证
当参与者ui收到子秘密ki之后。通过公式（1）检验子秘密ki的有效性。
公式（2）
若公式（1）成立，则表示UD发给ui的子秘密ki是诚实的。
1.2.3 主秘密的恢复
当任意t个参与者欲恢复出主秘密结合S={s1，s2，…，sm}时，其恢复过程如下：
（1）参与者计算并提供屏蔽子秘密Wi≡KiR（modn）（i=1，2，…，t）。
（2）其他参与者验证等式Ci=h（Wi），若成立则该屏蔽子秘密是有效的。
（3）通过公式（1）及公式（2）可以验证相关公开参数的正确性，然后通过公式（yi，yi`）=（Di+Wi）（modN）计算出（yi，yi`）。
（4）由t个（yi，yi`）对，结合Hermite插值公式，即可恢复出多项式f（x）。其中前m个系数既是主秘密{s1，s2，…，sm}。
1.3 m≥2t时的方案：
1.3.1 构造阶段
（1）UD构造一个m-1阶多项式f（x）：
，其中ai=si，记为f（x）导数。
（2）计算yi=f（h（ki））和yi`=f`（h（ki））（i=1，2，…，n）的值。
（3）通过Hermite插值公式，重构m-1阶多项式f（x）。
当m为奇数时（m为偶数类似可求）：
计算Zv=f（bv）（v=1，2，…，（m+1）/2-t），Zv`=f`（bv）（v=1，2，…，（m+1）/2-t）
，并将（Zv，Zv`）（v=1，2，…，（m+1）/2-t）存入中。
（4）在椭圆曲线E（Fq）上任选一点R，放入PB，类似2.2.1（3）（4）（5）过程，计算并将M，Di（i=1，2，…，n），Ci（i=1，2，…，n）放入PB，。
1.3.2 子秘密的验证
当参与者ui收到子秘密ki之后。通过公式（3）检验子秘密ki的有效性。
公式（3）
1.3.3 主秘密的恢复
当任意t个参与者欲恢复出主秘密结合S={s1，s2，…，sm}时，其恢复过程如下：
（1）类似2.2.3（1）（2）（3）过程，求出（yi，yi`）（i=1，2，…，t）。
（2）通过下式检验（Zv，Zv`）（v=1，2，…，（m+1）/2-t）是否有效。
公式（4）
（3）参与者由t个点（yi，yi`）及（Zv，Zv`）（v=1，2，…，（m+1）/2-t），结合插值公式，可恢复出多项式f（x），从而获得了主秘密。
2 方案分析
2.1 正確性分析
公式（1）的证明过程如下，证明：由Di≡（yi，yi`）-kiR（modN）（i=1，2，…，n）知：（yi，yi`）≡（Di+kiR）（modN）（i=1，2，…，n）。假若参与者ui收到的子秘密ki正确无误。则必有：。所以：
即（2）成立。公式（3）（4）的验证过程类似。
2.2 安全性分析
攻击1：恶意者试图通过公开信息恢复主秘密mi。由Mi求ai，其中Mi=aiG，因为基于椭圆曲线离散对数问题的计算难解性，所以求不出，即无法恢复出主秘密。
攻击2：管理者欺骗。 假若管理者给参与者提供虚假的子秘密，这时参与者通过公式（2）或（3）可以验证子秘密的正确性，识别管理者的欺骗。
攻击3：参与者欺骗。在本方案中参与者如果想提供虚假屏蔽子秘密且不被其他参与者发现需通过的通过Ci=h（wi）的验证，而这难度等同找到函数的一个碰撞。
3 结束语
在本文提出的可验证多秘密共享方案中，分发者能够动态决定要共享的主秘密个数，且多个主秘密能够被同时重构出来。主秘密更新时，参与者可以反复多次使用自己的子秘密。本方案的每一个阶段，都进行了严格的论证，能有效地抵御各种形式的伪造欺骗。
参考文献
[1]Shamir A.How to share a secret[J].Communications of the ACM，1979，22（11）：612-613.
[2] Blakley G.R.Safeguarding cryptographic keys[C].Proceedings of the 1979 National computer conference，New York，June 47，1979，vol.48，AFIPS Press，313-317.
[3]吴春英，李顺东.一类特殊超图与理想秘密共享方案[J].计算机工程，2013，39（7）：205-208.
[4]张晓敏.基于线性单向函数的可验证的多秘密共享方案[J].计算机应用，2013，33（5）：1391-1393.
作者单位：湖南化工职业技术学院，湖南株洲 412000