基于中國剩余定理的無可信中心可驗證秘密共享研究

楊 陽,朱曉玲,丁 涼

(合肥工業大學計算機與信息學院,合肥230009)

基于中國剩余定理的無可信中心可驗證秘密共享研究

楊 陽,朱曉玲,丁 涼

(合肥工業大學計算機與信息學院,合肥230009)

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

秘密共享;可信中心;可驗證;門限簽名;中國剩余定理;離散對數問題

1 概述

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

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

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

2 Asmuth-Bloom方案

2.1 初始化

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

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

(2)d1,d2,…,dn嚴格單調遞增;

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

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

2.2 秘密分割

DC計算:

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

2.3 秘密恢復

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

根據CRT,該方程組有唯一解z:

則秘密S為:

Asmuth-Bloom方案基于中國剩余定理,計算量較小,但需一個可信中心的參與,且無法驗證成員秘密份額的真實性。

3 本文方案

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

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

3.1 秘密份額與組密鑰的產生

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

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

Pi計算:

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

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

(2)Pi計算組公鑰Y:

盡管成員Pi公開gyi,但通過gyimodp求yi屬于離散對數問題,因此成員私鑰yi不會泄漏。另一方面,通過Y求:

也屬于離散對數問題;因此,除非所有成員合作,否則任何人無法獲得組私鑰X。

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

并廣播αi,βij。

當收到Pi發送來的aij之后,Pj可以通過下式驗證秘密份額影子aij的正確性:

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

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

證明:

定理2Pi無法公布假的gAi。

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

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

由于β′ij是一個整數且g是一個素數,因此:

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

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

因此,Pi無法公布假的gAi。

定理3Pi無法提供假的αi。

證明:為了計算公鑰,Pi必須提供真的gyi。另一方面,Pi無法提供假的gAi。因此,αi可以通過下式驗證:

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

因此,Pi無法提供假αi。

定理4Pi無法提供假βij。

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

因此:

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

因此,Pi無法提供假βij。

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

成員Pj可利用Lj產生自己的部分簽名。

3.2 部分簽名的產生

t個成員利用各自的秘密份額,基于CRT產生各自的部分簽名,并發送給簽名合成者。

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

(2)Pi計算:

ei可以通過下式計算:

Vi用于計算部分簽名。由于成員Pi在計算Vi時需用到自己的秘密份額Li,因此每個成員只能產生自己的部分簽名。

(3)Pi為報文M產生各自的部分簽名并發送(M,r,si)給簽名合成者。

3.3 合成與驗證簽名

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

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

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

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

證明:假設:

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

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

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

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

因此:

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

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

4 安全性分析

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

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

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

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

(4)在驗證過程中,各成員子秘密yi是安全的。本文方案在驗證aij過程中需要每個成員Pi公開驗證信息:

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

5 方案實例

本節通過實例驗證本文方案的正確性。

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

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

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

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

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

(4)部分簽名產生:

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

P2計算部分簽名:

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

P3計算部分簽名:

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

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

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

驗證組簽名:

因此:

即組簽名是正確的。

6 實驗結果與分析

實驗環境:實驗平臺為Lenovo PC,T420i, Intel(R),Core(TM)i3-2310M,2.1GHz。操作系統為Win7,開發軟件為Microsoft Visual C++6.0。

實驗目的:測試本文方案和基于Lagrange Interpolation門限簽名方案中產生部分簽名的時間消耗。

實驗方案:Harn無可信中心簽名方案[5]是一種經典的基于Lagrange Interpolation無可信中心門限簽名方案,故測試該方案部分簽名產生的時間消耗,并與本方案對比。文獻[5]中部分簽名計算如下:

其主要時間消耗為計算拉格朗日插值基函數:

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

其主要時間消耗為計算逆元ei。

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

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

(2)測試本文方案部分簽名時間消耗。本方案中,取成員數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}為對應{P1,P2,…,P10}的模;當t=3時,選取成員P1,P2,P8;當t=4時,選取P1,P2,P3,P8;依此類推。測試P8產生部分簽名時間消耗。實驗結果如表2所示。

表2 本文方案部分簽名時間消耗

如圖1所示,本文方案計算部分簽名時間遠少于基于Lagrange Interpolation門限簽名方案,故本方案的時間效率優于基于Lagrange Interpolation門限簽名方案。

圖1 部分簽名時間的消耗對比

7 結束語

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

[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] 王 斌,李建華.無可信中心的(t,n)門限簽名方案[J].計算機學報,2003,26(11):1581-1584.

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

[8] 何二慶,侯整風,朱曉玲.一種無可信中心動態秘密共享方案[J].計算機應用研究,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] 于 洋,劉煥平.可驗證的Asmuth-Bloom秘密共享方案[J].哈爾濱師范大學學報:自然科學版,2012, 28(3):20-23.

[14] 侯整風,李漢清,胡東輝,等.基于中國剩余定理的無可信中心門限簽名方案[C]//2011中國儀器儀表與測控技術大會論文集.北京:中國儀器儀表學會,2011.

編輯 索書志

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

楊 陽,朱曉玲,丁 涼.基于中國剩余定理的無可信中心可驗證秘密共享研究[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

廣東省教育部產學研結合基金資助項目(2008090200049)。

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

2014-03-19

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