基于中國(guó)剩余定理的無(wú)可信中心可驗(yàn)證秘密共享研究

楊 陽(yáng),朱曉玲,丁 涼

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥230009)

基于中國(guó)剩余定理的無(wú)可信中心可驗(yàn)證秘密共享研究

楊 陽(yáng),朱曉玲,丁 涼

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥230009)

基于中國(guó)剩余定理提出一種無(wú)可信中心可驗(yàn)證門限簽名秘密共享方案。該方案無(wú)需可信中心的參與,每個(gè)成員被視為分發(fā)者,通過(guò)相互交換秘密份額影子協(xié)同產(chǎn)生各自的秘密份額,從而避免可信中心的權(quán)威欺騙。成員利用自己的秘密份額產(chǎn)生部分簽名,再由部分簽名合成組簽名,在簽名過(guò)程中不直接利用或暴露組私鑰,從而保證組私鑰的可重用性。基于離散對(duì)數(shù)求解困難性,構(gòu)造秘密份額影子驗(yàn)證式,從而識(shí)別成員之間的欺騙行為,有效防止成員之間的惡意欺詐。實(shí)驗(yàn)結(jié)果表明,與基于拉格朗日插值的秘密共享方案相比,該方案具有較高的計(jì)算效率。

秘密共享;可信中心;可驗(yàn)證;門限簽名;中國(guó)剩余定理;離散對(duì)數(shù)問(wèn)題

1 概述

1979年,Shamir[1]和Blakley[2]分別基于Lagrange Interpolation定理和射影定理,提出2種(t,n)門限秘密共享方案。隨后,人們對(duì)門限秘密共享進(jìn)行了廣泛研究。文獻(xiàn)[3]基于離散對(duì)數(shù)問(wèn)題,提出了一種非交互式可驗(yàn)證秘密共享方案,該方案通過(guò)驗(yàn)證等式而無(wú)需信息交互,能夠驗(yàn)證和識(shí)別假的秘密份額,但攻擊者可能獲得秘密構(gòu)造多項(xiàng)式。文獻(xiàn)[4]對(duì)文獻(xiàn)[3]的方案進(jìn)行改進(jìn),基于同態(tài)承諾提出一種非交互可驗(yàn)證秘密共享方案,能夠保證秘密構(gòu)造多項(xiàng)式的安全。為了避免可信中心的“權(quán)威欺騙”,1994年,文獻(xiàn)[5]基于Lagrange Interpolation提出一種無(wú)可信中心門限簽名方案,但是該方案經(jīng)過(guò)一次簽名后,攻擊者容易獲得組私鑰和成員的私鑰,導(dǎo)致私鑰不可重用。文獻(xiàn)[6]采用聯(lián)合秘密共享技術(shù)解決了成員私鑰易被恢復(fù)的問(wèn)題。文獻(xiàn)[7]基于Lagrange Interpolation提出一種無(wú)可信中心的有向門限簽名方案,但不能驗(yàn)證成員提供的秘密份額的真實(shí)性。文獻(xiàn)[8]基于Lagrange Interpolation提出一種無(wú)可信中心動(dòng)態(tài)秘密共享方案,該方案在不暴露共享秘密的情況下,通過(guò)成員協(xié)同交互,能夠動(dòng)態(tài)地更新各自的秘密份額,增加新成員,但其計(jì)算量大。

文獻(xiàn)[9]提出一種基于中國(guó)剩余定理(Chinese Remainder Theorem,CRT)的秘密共享方案,與基于Lagrange Interpolation方案相比,其計(jì)算量較小。文獻(xiàn)[10-11]基于CRT分別提出2個(gè)可驗(yàn)證秘密共享方案(VSS),但上述2種方案均需可信中心產(chǎn)生和分發(fā)秘密份額。文獻(xiàn)[12]基于CRT提出了一種新的VSS方案并證明了其安全性,該方案中由成員協(xié)同產(chǎn)生秘密份額,但其驗(yàn)證過(guò)程仍需要一個(gè)可信中心參與。文獻(xiàn)[13]基于CRT提出一種可驗(yàn)證的秘密共享方案,該方案由可信中心與成員合作產(chǎn)生秘密份額與驗(yàn)證信息,其驗(yàn)證信息較文獻(xiàn)[12]更簡(jiǎn)單。文獻(xiàn)[14]提出一種無(wú)可信中心門限簽名方案,該方案沒(méi)有對(duì)秘密份額進(jìn)行驗(yàn)證,在交互過(guò)程中,成員之間可能存在欺騙行為。目前,基于CRT的可驗(yàn)證無(wú)可信中心門限秘密共享方案尚未發(fā)現(xiàn)。

本文基于CRT提出一種可驗(yàn)證的無(wú)可信中心門限簽名方案,該方案無(wú)需可信中心,所有成員相互合作,在不泄露秘密的情況下產(chǎn)生秘密份額及組公鑰并隱式產(chǎn)生組私鑰。此外,本文方案成員相互協(xié)作產(chǎn)生驗(yàn)證參數(shù),通過(guò)驗(yàn)證等式驗(yàn)證秘密份額的真實(shí)性。

2 Asmuth-Bloom方案

2.1 初始化

假設(shè)DC是一個(gè)分發(fā)者,P={P1,P2,…,Pn}是n個(gè)成員組成的集合,門限為t,秘密是S。DC選取一個(gè)大素?cái)?shù)q(q＞S),整數(shù)A和一個(gè)正整數(shù)序列d= {d1,d2,…,dn},且滿足以下條件:

(1)0≤A≤[N/q]-1;

(2)d1,d2,…,dn嚴(yán)格單調(diào)遞增;

(3)(di,dj)=1,(i≠j);

(4)(di,q)=1,(i=1,2,…,n);

2.2 秘密分割

DC計(jì)算:

并發(fā)送(zi,di)給Pi(i=1,2,…,n)作為Pi的秘密份額。

2.3 秘密恢復(fù)

任何成員可以通過(guò)相互交換各自的秘密份額恢復(fù)秘密S。設(shè)W={P1,P2,…,Pt}為恢復(fù)秘密的一組t個(gè)成員。相互交換秘密后,Pi(i=1,2,…,t)可以構(gòu)建如下同余方程組:

根據(jù)CRT,該方程組有唯一解z:

則秘密S為:

Asmuth-Bloom方案基于中國(guó)剩余定理,計(jì)算量較小,但需一個(gè)可信中心的參與,且無(wú)法驗(yàn)證成員秘密份額的真實(shí)性。

3 本文方案

本文基于CRT,提出一種新的可驗(yàn)證的無(wú)可信中心門限簽名方案。與基于Lagrange Interpolation的門限簽名方案相比,具有較高的計(jì)算效率。

本文方案分為3個(gè)步驟:(1)秘密份額與組密鑰的產(chǎn)生;(2)部分簽名的產(chǎn)生;(3)合成和驗(yàn)證簽名。

3.1 秘密份額與組密鑰的產(chǎn)生

假設(shè)P={P1,P2,…,Pn}是一組n個(gè)成員的集合,門限值為t。選取公共參數(shù):2個(gè)大素?cái)?shù)p和q,一組正整數(shù)序列d={d1,d2,…,dn}和一個(gè)素?cái)?shù)域上的生成元g,q和d滿足Asumth-Bloom方案。公開(kāi)n,t,p,q,g和d={d1,d2,…,dn}。

(1)Pi(i=1,2,…,n)隨機(jī)選擇yi和一個(gè)整數(shù)Ai滿足以下條件:

Pi計(jì)算:

其中,yi表示成員的子秘密,即成員私鑰;aij為秘密份額影子,用于產(chǎn)生秘密份額。

公開(kāi)aij(i≠j),gAi和gyi,Pi保存aii。

(2)Pi計(jì)算組公鑰Y:

盡管成員Pi公開(kāi)gyi,但通過(guò)gyimodp求yi屬于離散對(duì)數(shù)問(wèn)題,因此成員私鑰yi不會(huì)泄漏。另一方面,通過(guò)Y求:

也屬于離散對(duì)數(shù)問(wèn)題;因此,除非所有成員合作,否則任何人無(wú)法獲得組私鑰X。

(3)Pi計(jì)算αi,βij(j=1,2,…,n):

并廣播αi,βij。

當(dāng)收到Pi發(fā)送來(lái)的aij之后,Pj可以通過(guò)下式驗(yàn)證秘密份額影子aij的正確性:

如果aij滿足上式,則成員Pi發(fā)送的秘密份額影子aij為真。

定理1秘密份額驗(yàn)證式(2)～式(5)正確。

證明:

定理2Pi無(wú)法公布假的gAi。

證明:假設(shè)Pi公布一個(gè)假的gAi設(shè)為Fi,即當(dāng)Pj收到Fi后,式(4)、式(5)仍然成立。設(shè)a′ij為Pi提供的假的秘密份額影子,因此:

由于g和q是2個(gè)素?cái)?shù),如果Fi不是g的冪,βij將不是整數(shù),與方案中條件βij=gkijmodp必為整數(shù)相矛盾。因此,Fi必是g的冪。假設(shè):

由于β′ij是一個(gè)整數(shù)且g是一個(gè)素?cái)?shù),因此:

另一方面,秘密份額值小于dj,因此:

完全符合方案初始構(gòu)造秘密份額影子條件,即a′ij為真,與假設(shè)a′ij為假秘密份額相矛盾。

因此,Pi無(wú)法公布假的gAi。

定理3Pi無(wú)法提供假的αi。

證明:為了計(jì)算公鑰,Pi必須提供真的gyi。另一方面,Pi無(wú)法提供假的gAi。因此,αi可以通過(guò)下式驗(yàn)證:

如果αi滿足上式,αi為真。否則,αi為假。

因此,Pi無(wú)法提供假αi。

定理4Pi無(wú)法提供假βij。

證明:假設(shè)Pi公開(kāi)假β′ij≠βij,由于αi為真,即當(dāng)Pj接受a′ij≠aij時(shí),式(3)～式(5)仍然成立。

因此:

由于秘密份額的值比dj小,因此a′ij＞dj恒不成立。

因此,Pi無(wú)法提供假βij。

(4)當(dāng)收到其他成員的aij后,Pj計(jì)算他的秘密份額Lj:

成員Pj可利用Lj產(chǎn)生自己的部分簽名。

3.2 部分簽名的產(chǎn)生

t個(gè)成員利用各自的秘密份額,基于CRT產(chǎn)生各自的部分簽名,并發(fā)送給簽名合成者。

(1)Pi選取任意隨機(jī)數(shù)ui∈Zq,計(jì)算并廣播ri:

(2)Pi計(jì)算:

ei可以通過(guò)下式計(jì)算:

Vi用于計(jì)算部分簽名。由于成員Pi在計(jì)算Vi時(shí)需用到自己的秘密份額Li,因此每個(gè)成員只能產(chǎn)生自己的部分簽名。

(3)Pi為報(bào)文M產(chǎn)生各自的部分簽名并發(fā)送(M,r,si)給簽名合成者。

3.3 合成與驗(yàn)證簽名

合成者收到t個(gè)部分簽名(M,r,si)后,計(jì)算:

(M,r,s)是報(bào)文M的組簽名。任何人均可利用組公鑰驗(yàn)證簽名。驗(yàn)證式如下:

如果上式成立,則組簽名(M,r,s)有效。

定理5(正確性分析) 如果gs≡rM·Yrmodp,組簽名(M,r,s)有效。

證明:假設(shè):

t個(gè)成員P1,P2,…,Pt各自擁有秘密份額L1,L2,…,Lt,滿足下面同余式:

Z≡Limoddi,i=1,2,…,t(10)

通過(guò)式(1)和式(2):

另一方面,通過(guò)式(3)和式(9),可以得到:

因此:

根據(jù)式(2)～式(7):

另一方面,由式(4)和式(11),得:

4 安全性分析

本文方案安全性分析如下:

(1)本文方案無(wú)需可信中心,秘密份額由全體成員協(xié)同產(chǎn)生,任何人均無(wú)法知道組私鑰,有效地避免了可信中心的權(quán)威欺騙。

(2)本文方案能夠識(shí)別成員之間的欺詐行為,根據(jù)定理2～定理5,每個(gè)成員必須公開(kāi)真的αi,βij,如果Pi提供假的秘密份額影子aij,通過(guò)αi,βij及驗(yàn)證式(2)～式(5)可以檢測(cè)出來(lái)。

(3)組私鑰X是安全的且具有可重用性。在組密鑰產(chǎn)生階段,除非全體成員合作,單個(gè)成員無(wú)法獲得組私鑰X(由式(2)～式(4)可知)。在部分簽名產(chǎn)生階段,每個(gè)成員計(jì)算部分簽名si=ui·M+r·Vi時(shí)沒(méi)有直接使用或暴露組私鑰X的任何信息,因此,在一次簽名后,組私鑰仍可以重復(fù)使用。

(4)在驗(yàn)證過(guò)程中,各成員子秘密yi是安全的。本文方案在驗(yàn)證aij過(guò)程中需要每個(gè)成員Pi公開(kāi)驗(yàn)證信息:

根據(jù)αi求得Xi屬于離散對(duì)數(shù)問(wèn)題,因此αi是安全的,另一方面,攻擊者想根據(jù)βij獲得Xi,則必須知道kij,而根據(jù)kij獲得βij仍然屬于離散對(duì)數(shù)問(wèn)題。因此,Xi是安全的,進(jìn)而yi(yi=Xi-Aiq)也是安全的。

5 方案實(shí)例

本節(jié)通過(guò)實(shí)例驗(yàn)證本文方案的正確性。

(1)初始化條件:假設(shè)n=5,t=3,p=13,q=11,g=3,d={9,11,13,15,17}和M=1。

(2)秘密份額及組公鑰的產(chǎn)生:

(3)驗(yàn)證秘密份額影子:

如果P1提供真的秘密份額影子a12=1,則:

因此成員之間的欺騙行為可通過(guò)式(2)～式(5)識(shí)別。

(4)部分簽名產(chǎn)生:

P1的部分簽名為(1,1,859),并發(fā)送給簽名合成者。

P2計(jì)算部分簽名:

P2的部分簽名為(1,1,118),并發(fā)送給簽名合成者。

P3計(jì)算部分簽名:

P3部分簽名為(1,1,496),并發(fā)送給簽名合成者。

(5)組簽名的合成與驗(yàn)證:

則(1,1,10)為報(bào)文M的組簽名。

驗(yàn)證組簽名:

因此:

即組簽名是正確的。

6 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境:實(shí)驗(yàn)平臺(tái)為L(zhǎng)enovo PC,T420i, Intel(R),Core(TM)i3-2310M,2.1GHz。操作系統(tǒng)為Win7,開(kāi)發(fā)軟件為Microsoft Visual C++6.0。

實(shí)驗(yàn)?zāi)康?測(cè)試本文方案和基于Lagrange Interpolation門限簽名方案中產(chǎn)生部分簽名的時(shí)間消耗。

實(shí)驗(yàn)方案:Harn無(wú)可信中心簽名方案[5]是一種經(jīng)典的基于Lagrange Interpolation無(wú)可信中心門限簽名方案,故測(cè)試該方案部分簽名產(chǎn)生的時(shí)間消耗,并與本方案對(duì)比。文獻(xiàn)[5]中部分簽名計(jì)算如下:

其主要時(shí)間消耗為計(jì)算拉格朗日插值基函數(shù):

在本文方案中,部分簽名計(jì)算如下:

其主要時(shí)間消耗為計(jì)算逆元ei。

(1)測(cè)試基于Lagrange Interpolation門限簽名方案部分簽名時(shí)間消耗。基于Lagrange Interpolation門限簽名方案中,成員數(shù)n為15,秘密份額集合X={10,11,12,13,14,15,16,17,18,19,20, 21,22,23,24}對(duì)應(yīng)成員集合P={P1,P2,…,P15};門限t分別取3,4,5,6,7,8,9,10。當(dāng)t=3時(shí),選取成員P1,P2,P3;當(dāng)t=4時(shí),選取P1,P2,P3,P4;依此類推。測(cè)試P1產(chǎn)生部分簽名時(shí)間消耗。實(shí)驗(yàn)結(jié)果如表1所示。

表1 基于Lagrange Interpolation方案的部分簽名時(shí)間消耗

(2)測(cè)試本文方案部分簽名時(shí)間消耗。本方案中,取成員數(shù)n為15,成員集合為P={P1,P2,…,P15},門限t分別取3、4、5、6、7、8、9、10。選取序列d={3,7,11,17,19,23,29,31,37,41}為對(duì)應(yīng){P1,P2,…,P10}的模;當(dāng)t=3時(shí),選取成員P1,P2,P8;當(dāng)t=4時(shí),選取P1,P2,P3,P8;依此類推。測(cè)試P8產(chǎn)生部分簽名時(shí)間消耗。實(shí)驗(yàn)結(jié)果如表2所示。

表2 本文方案部分簽名時(shí)間消耗

如圖1所示,本文方案計(jì)算部分簽名時(shí)間遠(yuǎn)少于基于Lagrange Interpolation門限簽名方案,故本方案的時(shí)間效率優(yōu)于基于Lagrange Interpolation門限簽名方案。

圖1 部分簽名時(shí)間的消耗對(duì)比

7 結(jié)束語(yǔ)

本文基于CRT提出一種可驗(yàn)證的無(wú)可信中心門限簽名方案。本文方案無(wú)需可信中心,成員通過(guò)交換秘密份額影子協(xié)同產(chǎn)生各自的秘密份額,從而避免了可信中心的“權(quán)威欺騙”,并能夠識(shí)別成員之間的欺騙行為。成員利用各自的秘密份額產(chǎn)生部分簽名,再由部分簽名合成組簽名;在簽名過(guò)程中沒(méi)有直接利用或暴露組私鑰,從而保證了組私鑰的可重用性。本文對(duì)方案的正確性和安全性進(jìn)行了理論分析,并通過(guò)實(shí)例驗(yàn)證方案的正確性。

[1] Shamir A.How to Share a Secret[J].Communications of ACM,1979,22(11):612-613.

[2] Blakley G R.Safeguarding Cryptographic Keys[C]// ProceedingsofNationalComputerConference. Arlington,USA:[s.n.],1979:313-317.

[3] Feldman P.APracticalSchemeforNon-interactive Verifiable Secret Sharing[C]//Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. [S.1.]:IEEE Computer Society,1987:427-437.

[4] Pedersen T P.Non-interactiveandInformation-theoretic Secure Verifiable Secret Sharing[C]//Proceedings of the 11thAnnualInternationalCryptologyConferenceon Advances in Cryptology.[S.1.]:IEEE Press,1991: 129-140.

[5] Harn L.Group-oriented(t,n)ThresholdDigital Signature Scheme and Digital Multisignature[J].IEEE Proceedings of Computers and Digital and Techniques, 1994,141(5):307-313.

[6] 王 斌,李建華.無(wú)可信中心的(t,n)門限簽名方案[J].計(jì)算機(jī)學(xué)報(bào),2003,26(11):1581-1584.

[7] 沈忠華,于秀源.一個(gè)無(wú)可信中心的有向門限簽名方案[J].杭州師范學(xué)報(bào):自然科學(xué)版,2006,5(2): 95-98.

[8] 何二慶,侯整風(fēng),朱曉玲.一種無(wú)可信中心動(dòng)態(tài)秘密共享方案[J].計(jì)算機(jī)應(yīng)用研究,2013,30(2):177-179.

[9] Asmuth C A,Bloom J.A Modular Approach to Key Safeguarding[J].IEEE Transactions on Information Theory,1983,29(2):208-210.

[10] Li Qiong,Wang Zhifang,Niu Xiamu,et,al.A Aoninteractive Modular Verifiable Secret Sharing Scheme[C]// Proceedings of International Conference on Communications,Circuits and Systems.Los Alamitos,USA:[s.n.], 2005:84-87.

[11] Iftene S.Secret Sharing Schemes with Applications in Security Protocols[D].[S.1.]:UniversityAlexandru,2007.

[12] Kaya K,Selcuk A A.A Verifiable Secret Sharing Scheme BasedontheChineseRemainderTheorem[C]// Proceedings of the 9th Annual International Conference on Cryptology.Kharagpur,India:[s.n.],2008:414-425.

[13] 于 洋,劉煥平.可驗(yàn)證的Asmuth-Bloom秘密共享方案[J].哈爾濱師范大學(xué)學(xué)報(bào):自然科學(xué)版,2012, 28(3):20-23.

[14] 侯整風(fēng),李漢清,胡東輝,等.基于中國(guó)剩余定理的無(wú)可信中心門限簽名方案[C]//2011中國(guó)儀器儀表與測(cè)控技術(shù)大會(huì)論文集.北京:中國(guó)儀器儀表學(xué)會(huì),2011.

編輯 索書(shū)志

Research on Verifiable Secret Sharing Without Trusted Center Based on Chinese Remainder Theorem

YANG Yang,ZHU Xiaoling,DING Liang
(School of Computer and Information,Hefei University of Technology,Hefei 230009,China)

A new verifiable threshold signature scheme without a trusted center is proposed based on Chinese Remainder Theorem(CRT).The scheme do not needed the trusted center.Each participant is regarded as a distributor,and generates his own secret share by exchanging secret share shadows with the others,which can avoid the trusted center’s authority deception.Participants use their own secret shares to generate the partial signatures,and the group signature is composed of the partial signatures,which means the group private key is not used or exposed directly,so that the group private key’s reusability can be ensured.Based on the discrete logarithm problem,the scheme constructs the secret shadow verification formula,so that it can identify the participants’mutual cheating to prevent the malicious fraud of the participants effectively.Experimental results show that compared with the secret sharing schemes based on Lagrange interpolation,this scheme is more efficient.

secret sharing;trusted center;verifiable;threshold signature;Chinese Remainder Theorem(CRT);discrete logarithm problem

楊 陽(yáng),朱曉玲,丁 涼.基于中國(guó)剩余定理的無(wú)可信中心可驗(yàn)證秘密共享研究[J].計(jì)算機(jī)工程, 2015,41(2):122-128.

英文引用格式:Yang Yang,Zhu Xiaoling,Ding Liang.Research on Verifiable Secret Sharing Without Trusted Center Based on Chinese Remainder Theorem[J].Computer Engineering,2015,41(2):122-128.

1000-3428(2015)02-0122-07

:A

:TP309

10.3969/j.issn.1000-3428.2015.02.024

廣東省教育部產(chǎn)學(xué)研結(jié)合基金資助項(xiàng)目(2008090200049)。

楊 陽(yáng)(1991-),男,碩士研究生,主研方向:信息安全;朱曉玲,博士研究生;丁 涼,講師。

2014-03-19

:2014-04-14E-mail:yangyang9074@163.com