基于双线性对的可公开验证多秘密共享方案

尚雪娇,杜伟章

(长沙理工大学计算机与通信工程学院,长沙410114)

基于双线性对的可公开验证多秘密共享方案

尚雪娇,杜伟章

(长沙理工大学计算机与通信工程学院,长沙410114)

现有可公开验证多秘密共享方案只能由Lagrange插值多项式构造,且共享的秘密仅限于有限域或加法群。为解决上述问题,提出一个基于双线性对的可公开验证多秘密共享方案。该方案中每个参与者需持有2个秘密份额来重构多个秘密,并且在秘密分发的同时生成验证信息。任何人都可以通过公开的验证信息对秘密份额的有效性进行验证,及时检测分发者和参与者的欺骗行为。在秘密重构阶段采用Hermite插值定理重构秘密多项式,并结合双线性运算重构秘密。分析结果表明,在双线性Diffie-Hellman问题假设下,该方案能抵抗内外部攻击,具有较高的安全性。

双线性对;秘密共享;多秘密共享;秘密份额;Hermite插值;双线性Diffie-Hellman问题

1 概述

秘密共享是现代密码学和信息安全的一个重要分支,在现实生活中有着广泛的应用。Shamir[1]和Blakey[2]于1979年分别独立提出了门限秘密共享方案,前者基于Lagrange插值多项式,后者基于射影几何理论。为了防止不诚实的分发者和参与者的恶意行为,Chor[3]等人在1985年提出了可验证的秘密共享方案。之后,Stadler[4]又提出了可公开验证的秘密共享(PVSS)方案的概念。可公开验证的秘密共享方案允许任何人对秘密份额的有效性进行验证,并且验证过程中不会泄漏秘密的相关信息。

近年来,随着对秘密共享研究的深入,学者结合不同的公钥密码体制、数学模型、双线性对技术等提出了各种各样的秘密共享方案[5-8]。2010年,李大伟等人提出了一种使用IBE公钥算法实现的可验证秘密共享方案[9],该方案中秘密分发者将IBE私钥作为共享秘密分发给参与者,参与者可以通过公开的验证信息验证秘密份额的正确性。田友亮等人构造了一个椭圆曲线上的信息论安全的可验证秘密共享方案[10],利用双线性对的双线性性质,提高了方案中秘密份额验证的有效性。文献[11]提出了一个双线性对上公开可验证的多秘密共享方案,该方案利用双线性对的性质实现了秘密份额的公开验证,并且可以同时共享多个秘密。由于双线性对具有很好的性质,越来越多的学者将其应用于秘密共享方案的研究[12-13]。

在一般的秘密共享方案中,共享的秘密都是有限域上[5]或加法群上[10]的,WU等人于2011年提出了一个基于双线性对的可公开验证秘密共享方案[14],方案中共享秘密s是乘法群上的,弥补了已有方案中共享秘密仅限于有限域和加法群上的不足,并利用双线性对的性质对秘密份额的有效性进行了验证,进而防止参与者的欺骗行为。本文在文献[14]方案的基础上,结合Hermite插值多项式构造了一个可公开验证的多秘密共享方案,该方案可解决原方案一次秘密共享过程只能共享一个秘密的问题。

2 预备知识

2.1 双线性对

定义1 设G1是阶为q(q为素数)的加法群, G2是阶为q的乘法群,若对任意的a,b∈,存在映射e:G1×G1→G2满足以下性质,则称该映射为双线性映射:

(1)双线性性:对任意P,Q∈G1,有e( aP,bQ)= e(P,Q)ab。

(2)非退化性:存在P,Q∈G1,使得e( P,Q)≠1。

(3)可计算性:对任意P,Q∈G1,存在有效算法计算e( P,Q)。

2.2 Diffie-Hellman问题

定义2 设G1和G2是阶为素数q的加法群和乘法群,它们之间存在映射e:G1×G1→G2,P是G1的生成元,对任意的 a,b,c∈Z*q,定义如下数学难题:

(1)离散对数问题(DLP):给定(P,aP),求a。

(2)计算性 Diffie-Hellman(CDH)问题:给定(P,aP,bP),计算abP。

(3)双线性 Diffie-Hellman(BDH)问题:给定(P,aP,bP,cP),计算e(P,P)abc∈G2。设算法A用来解决BDH问题,其优势定义为ε,如果:

Pr(A(P,aP,bP,cP)=e(P,P)abc)≥ε

目前,还没有有效的算法解决BDH问题。因此可以假设BDH问题是一困难问题。

2.3 Hermite插值

已知函数f(x)在n个互异点x1,x2,…,xn处的函数值f(x1),f(x2),…,f(xn)及一阶导数f′(x1),f′(x2),…,f′(xn),可构造一个2n-1次多项式H2n-1(x)满足以下插值条件:

其中,i=1,2,…,n。

此时的H2n-1(x)称为Hermite插值多项式,它的一般表达式为:

其中,αj(x)和βj(x)称为Hermite插值基函数:

3 方案描述

3.1 系统初始化

3.2 秘密分发

3.2.1 秘密份额的分发

秘密分发工作由D按以下步骤执行:

所以,rk=f(k-1),k=1,2,…,t。

(2)记f′(x)为f(x)的一阶导数,则:

(3)D利用各参与者的身份信息为其计算伪秘密份额ui=f(IDi),vi=f′(IDi),计算并公开系数承诺Aj=ajP,j=0,1,…,2t-1,易知A0=f(0)P,A1= f′(0)P。

3.2.2 秘密份额的验证

3.3 秘密重构

秘密重构的过程如下:

(1)参与者Pi利用自己的私钥xi计算:

若t个参与者的秘密份额均能通过验证,则利用2t个秘密份额s1j(j=1,2,…,t)和s2j(j=1,2,…,t),根据双线性对的性质和Hermite插值定理可得:

其中:

由于rk=f( k-1),因此可以得出:

4 方案分析

4.1 正确性分析

验证式及秘密重构的正确性分析如下:

(1)验证式的正确性

首先证明式(1)和式(2)的正确性:

由于 Ui=uiP,Vi=viP,ui=f(IDi),vi= f′(IDi),则:

由以上2个等式成立可知,分发者D为参与者Pi分发的伪秘密份额(ui,vi)是有效的。

下面证明式(3)的正确性:

因此,验证式(3)是正确的,即包含参与者秘密份额相关信息的数据(Ci,Di)是有效的。

验证式(4)的正确性:

因此,式(4)是正确的,可以用来验证参与者提供的秘密份额的有效性。

(2)秘密重构的正确性

参与者Pi利用自己的私钥xi,由Ci=e(Ri,Ppub)ui和Di=e(Ri,Ppub)vi得到秘密份额s1i=e(Ppub,Ppub)ui, s2i=e(Ppub,Ppub)vi。当重构秘密Sk(k=1,2,…,t)时, t个参与者P1,P2,…,Pt合作共同计算:

又因为rk=f(k-1),所以:

这样即可得到共享的t秘密S1,S2,…,St。

4.2 安全性分析

定理2 若BDH假设成立,则任何少于t个参与者合作都不能重构秘密s1,s2,…,st。

(2)随机选取t-1组整数:(f(d1),f′(d1)), (f(d2),f′(d2)),…,(f(dt-1),f′(dt-1)),再结合已经确定的(f(0),f′(0)),由Hermite插值定理可知,这样便确定了2t-1次多项式f(x)。

(3)计 算 Ci=e(Ri,Ppub)f(di),Di=e (Ri,Ppub)f′(di),Ui=f(di)P,Vi=f′(di)P,i=1, 2,…,t-1。

(4)由于f( 0)和f′(0)隐含在A0和A1中,因此攻击者A虽然固定了f(x),却无法重构它,故不能计算f(t),f(t+1),…,f(n)的值。然而,由A0=aP, A1=bP,Ui=f(di)P,Vi=f′(di)P,i=1,2,…,t-1,A可以得到如下的方程组:

其中,i=1,2,…,t-1。

解该方程组可以求出A2,A3,…,A2t-1。然后,A便可利用求出的A0,A1,…,A2t-1计算Ui(i=t,t+1,…,n)和Vi(i=t,t+1,…,n)的值。

(5)令参与者Pi的公钥Ri=x′iPpub,i=1,2,…, n。由于 Ci=e(Ri,Ppub)ui=e(x′iPpub,Ppub)ui= e(x′icP,Ppub)f(di),Ui=f(di)P,因此 Ci=e (Ui,Ppub)cx′i,i=1,2,…,n。同理,可以得到Di=e (Vi,Ppub)cx′i,i=1,2,…,n。

这样,所有的参数设置完成,即成功建立了一个模拟的多秘密共享系统。攻击者A将这些信息提供给t-1个成员P1,P2,…,Pt-1,根据假设,这t-1个成员可以重构秘密 Sk=e(Ppub,Ppub)rk。当 k=1时,由秘密S1=e(Ppub,Ppub)r1=e(Ppub,Ppub)f(0), Ppub=cP,f(0)P=aP,可推出 e(P,P)acc=e (Ppub,Ppub)f(0),这说明BDH问题是可以求解的,即BDH假设不成立。因此,若BDH假设成立,任何少于t个参与者合作不能重构秘密s1,s2,…,st。

5 结束语

本文基于椭圆曲线上的离散对数问题和双线性Diffie-Hellman假设,并结合Hermite插值定理构造了一种新的可公开验证多秘密共享方案。秘密分发不需要安全通道,仅利用双线性对的性质即可实现秘密份额的公开验证,每个参与者只需持有2个秘密份额就可以重构多个秘密。通过对方案正确性和安全性的分析可知,该方案满足可公开验证多秘密共享方案的特性。同时,Hermite插值多项式的引入,为可公开验证多秘密共享方案的研究提供了一种新的途径。然而,该方案中较多的双线性运算影响了其运行效率,因此,提高多秘密共享方案的效率是下一步的工作重点。

[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 National Computer Conference. New York,USA:[s.n.],1979:313-317.

[3] Chor B,Goldwasser S,Micali S,et al.Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults[C]//Proceedings of the 26th IEEE Symposium on Foundations of Computer Science.[S.1.]:IEEE Press,1985:383-395.

[4] Stadler M.Publicly Verifiable Secret Sharing[C]// Proceedings of Cryptology-Eurocryptp'96.Berlin, Germany:Springer-Verlag,1996:191-199.

[5] Kaya K,Selcuk A.A Verifiable Secret Sharing Scheme Based on the Chinese Remainder Theorem[C]// Proceedings of INDOCRYPT'08.Berlin,Germany: Springer-Verlag,2008:414-425.

[6] 步山岳,王汝传.一种可验证和高效的多秘密共享门限方案[J].计算机科学,2011,38(1):100-103.

[7] 田有亮,彭长根.基于双线性对的可验证秘密共享方案[J].计算机应用,2007,27(12):125-127.

[8] 谭晓青.高效的可验证多秘密共享方案[J].计算机工程与应用,2009,45(12):33-35.

[9] 李大伟,杨 庚,朱 莉.一种基于身份加密的可验证秘密共享方案[J].电子学报,2010,38(9):2060-2065.

[10] 田友亮,马建峰,彭长根,等.椭圆曲线上的信息论安全的可验证秘密共享方案[J].通信学报,2011,32 (12):96-102.

[11] 张建中,张艳丽.一个双线性对上公开可验证多秘密共享方案[J].计算机工程与应用,2011,47(25): 82-84.

[12] Tian Youliang,Peng Changgen,Ma Jianfeng.Publicly Verifiable Secret Sharing Schemes Using Bilinear Pairings [J].International Journal of Network Security,2012,14 (3):142-148.

[13] Li Fei,Gao Wei,Wang Yi-lei.An Efficient Certificateless Threshold Decryption Schemes Based on Pairings[J]. Journal of Computers,2012,7(12):2987-2996.

[14] Wu Tsu-Yang,Tseng Yuh-Min.A Pairing-based Publicly Verifiable Secret Sharing Scheme[J].Journal of Systems Science and Complexity,2011,24(1):186-194.

编辑 索书志

Publicly Verifiable Multi-secret Sharing Scheme Based on Bilinear Pairings

SHANG Xue-jiao,DU Wei-zhang
(College of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410114,China)

In order to solve the problems that the previous publicly verifiable multi-secret sharing schemes can be constructed only by Lagrange interpolation polynomial and the shared secret is limited to the finite field or additive group,a publicly verifiable multi-secret sharing scheme based on bilinear pairings is proposed.In the scheme,each participant has to hold two shares for reconstructing multiple secrets,and the verification information is generated in the process of secret distribution.According to public verification information,anyone can verify the validity of secret shares. Cheating of dealer and participants can be detected in time.In the secret reconstructing process,Hermite interpolation theorem is used to reconstruct the secret polynomial,and bilinear operation is combined to reconstruct the secret.Under the assumptions of Bilinear Diffie-Hellman Problem(BDHP),the analysis result shows that this scheme can resist internal and external attacks and is a secure and efficient multi-secret sharing scheme.

bilinear pairings;secret sharing;multi-secret sharing;secret share;Hermite interpolation;Bilinear Diffie-Hellman Problem(BDHP)

1000-3428(2014)09-0155-04

A

TP309

10.3969/j.issn.1000-3428.2014.09.031

尚雪娇(1988-),女,硕士研究生,主研方向:信息安全;杜伟章,教授、博士。

2013-08-19

2013-10-10E-mail:wbjsxj_2012@163.com