張本慧，蔣 偉，唐元生

（揚(yáng)州大學(xué)數(shù)學(xué)科學(xué)學(xué)院，江蘇揚(yáng)州225002）

無可信第三方的可驗(yàn)證多重密鑰共享方案

張本慧，蔣 偉，唐元生＊

（揚(yáng)州大學(xué)數(shù)學(xué)科學(xué)學(xué)院，江蘇揚(yáng)州225002）

提出一個(gè)無可信第三方的可驗(yàn)證的向量空間多重密鑰共享方案，其安全性依賴于橢圓曲線密碼學(xué)的安全性.該方案具有如下特點(diǎn)：無須可信第三方的參與，極大地減少了開銷；由參與者聯(lián)合生成共享的主密鑰并分發(fā)相應(yīng)的共享份額；可以共享多個(gè)主密鑰，而每個(gè)共享者只須存儲(chǔ)一個(gè)子密鑰；可以有效防止內(nèi)部成員的欺詐以及外部攻擊者的攻擊；僅需有限的存儲(chǔ)空間和傳輸帶寬，具有實(shí)際應(yīng)用價(jià)值.

向量空間密鑰共享；多重密鑰共享；無可信第三方；橢圓曲線密碼學(xué)

密鑰共享是現(xiàn)代密碼學(xué)的一個(gè)重要工具，使用密鑰共享可以防止系統(tǒng)密鑰的遺失、破壞及降低敵手破譯密鑰的成功率.SHAMIR［1］于1979年提出（t，n）門限密鑰共享的概念，即在n個(gè)參與者中共享密鑰s，當(dāng)且僅當(dāng)至少有t個(gè)參與者合作時(shí)才能恢復(fù)密鑰s.BRICKELL［2］于1989年拓展了門限密鑰共享的概念，提出向量空間密鑰共享方案.但是在實(shí)際應(yīng)用中，無論門限密鑰共享方案還是向量空間密鑰共享方案，都存在第三方和成員的欺詐問題.為了解決這些問題，一方面，有學(xué)者提出構(gòu)造無可信第三方的密鑰共享方案，其中大部分方案［3－6］基于門限密鑰共享而設(shè)計(jì)；另一方面，CHOR等［7］提出通過構(gòu)造可驗(yàn)證的密鑰共享方案來防止第三方和內(nèi)部成員的欺騙以及外部攻擊者的攻擊.多重密鑰共享研究的主要內(nèi)容是如何安全有效地共享多個(gè)密鑰.本文基于向量空間密鑰共享，構(gòu)建了一個(gè)可驗(yàn)證的無須可信第三方參與的多重密鑰共享方案.相比于文獻(xiàn)［8］的方案，本文方案可共享多個(gè)密鑰，同時(shí)方案中加入了驗(yàn)證算法，使得方案更加安全.相比于一些可驗(yàn)證多重密鑰共享方案［9－11］，本文方案具有如下優(yōu)點(diǎn)：無須可信第三方的參與；本文的驗(yàn)證算法是基于橢圓曲線密碼學(xué)，而文獻(xiàn)［9－11］方案的驗(yàn)證算法是基于RSA（Rivest－Shamir－Adleman）密碼學(xué)；而橢圓曲線密碼學(xué)的密鑰長度大約是同等安全性條件下RSA密碼學(xué)密鑰長度的1／6［12］，所以在實(shí)際應(yīng)用中本文方案僅需有限的存儲(chǔ)空間和傳輸帶寬.

1 預(yù)備知識(shí)

定義1（多重密鑰共享方案） 設(shè)參與者集合P＝｛P1，…，Pn｝上的m個(gè)主密鑰空間S1，…，Sm對應(yīng)的存取結(jié)構(gòu)分別為Γ1，…，Γm，S1，…，Sn分別為參與者P1，…，Pn的子密鑰取值空間，U為隨機(jī)輸入集合.P為實(shí)現(xiàn)多存取結(jié)構(gòu)｛Γ1，…，Γm｝的多重密鑰共享方案，是指存在映射Π：S1×…× Sm×U→S1×…×Sn，使得對任意選取的m個(gè)主密鑰s1∈S1，…，sm∈Sm以及隨機(jī)輸入u∈U，有Π（s1，…，sm，u）＝（s1，…，sn），其中si∈Si為Pi的子密鑰，1≤i≤n，并且映射Π滿足下列條件：

1）重構(gòu)要求.對于每個(gè)i，1≤i≤m，si∈Si可被Γi的任何授權(quán)集重構(gòu)，即存在重構(gòu)函數(shù)族Re＝｛：（S1×…×Sn）A→Si｜1≤i≤m，A∈Γi｝，使得對任意的A∈Γi，（s1，…，sm）∈S1×…× Sm，u∈U都有（Π（s1，…，sm，u）｜A）＝si；這等價(jià)于要求對每個(gè)i，1≤i≤m和任意A∈Γi，均有H（Si｜SA）＝0，其中H（·）為熵函數(shù).

2）安全性要求.對任意B｛P1，…，Pn｝和T｛S1，…，Sm｝＼｛Si｜B∈Γi，1≤i≤m｝，滿足0＜H（T｜SB）≤H（T）；這也等價(jià)于要求對1≤i≤m的任意BΓi和T｛S1，…，Sm｝＼｛Si｝，滿足0＜H（Si｜SB，T）≤H（Si｜T）.

定義2（向量空間密鑰共享方案） 設(shè)Γ是參與者集合P＝｛P1，…，Pn｝上的一個(gè)存取結(jié)構(gòu)，D（P）是可信的第三方.如果對于有限域K＝GF（q）上的向量空間E＝Kr，存在一個(gè)函數(shù)ψ：P∪D→E，使得A∈Γψ（D）可以由ψ（A）＝｛ψ（Pi）｜Pi∈A｝中的向量線性表示，則稱Γ為P上的一個(gè)向量空間存取結(jié)構(gòu).若Γ是一個(gè)向量空間存取結(jié)構(gòu)，則可構(gòu)建Γ上的一個(gè)主密鑰空間和子密鑰空間均為有限域K的密鑰共享方案：對于要共享的密鑰s∈K，D隨機(jī)選取向量v∈E滿足v·ψ（D）＝s，D計(jì)算并秘密發(fā)送si＝v·ψ（Pi）給參與者Pi作為他的子密鑰.

2 方案描述

2.1 系統(tǒng)初始化

1）設(shè)q是一個(gè)大素?cái)?shù)，E（Zq）是定義在Zq上的橢圓曲線，G是E（Zq）上階為p（p為大素?cái)?shù)）的一個(gè)點(diǎn)，使得在〈G〉上的離散對數(shù)問題難處理.

2）設(shè)參與者集合P＝｛P1，…，Pn｝上的m個(gè)向量空間存取結(jié)構(gòu)Γ1，Γ2，…，Γm，這里的函數(shù)ψ：P→（t＞m）滿足向量ψ（Pj）中至少存在兩個(gè)分量不為0，其中ψ（Pj）＝（aj1，aj2，…，ajt），j＝1，2，…，n；無可信第三方，參與者共同約定m個(gè)向量ei＝（0，…，0，0，…，0），i＝1，2，…，m，則A∈Γiei可以由ψ（A）中的向量線性表示.

2.2 密鑰生成

1）每個(gè)參與者Pi隨機(jī)選取xi＝（xi1，xi2，…，xit）∈（）t，計(jì)算并公開Ti1＝xi1G，Ti2＝xi2G，…，Tit＝xitG.

2）每個(gè)參與者Pi計(jì)算sij＝xi·ψ（Pj）mod p并秘密發(fā)送給參與者Pj.

3）每個(gè)參與者Pj驗(yàn)證他們所收到的sij：sijG＝，i＝1，2，…，n，一旦發(fā)現(xiàn)某個(gè)sij不滿足此等式，則向Pi發(fā)出一個(gè)抱怨，作為回應(yīng)，Pi公開揭示一個(gè)滿足此等式的sij.

4）如果所有的sij通過了驗(yàn)證，則每個(gè)參與者Pj可以計(jì)算自己的子密鑰為sj＝此時(shí)隨機(jī)默認(rèn)生成的m個(gè)主密鑰即為

2.3 密鑰重構(gòu)

不失一般性，假設(shè)Γi中授權(quán)子集A＝｛P1，P2，…，Pl｝準(zhǔn)備重構(gòu)主密鑰ki.

1）A中成員可以通過下式相互驗(yàn)證對方子密鑰的真實(shí)性：siG＝，i＝1，2，…，l，如果所有子密鑰通過了驗(yàn)證，則可進(jìn)入步驟2）恢復(fù)主密鑰，否則，協(xié)議停止.

2）首先，A中成員通過合作計(jì)算出λ1，λ2，…，λl∈Zp，使得ei＝（0，…，0，1，0，…，0）＝λ1ψ（P1）＋λ2ψ（P2）＋…＋λlψ（Pl），然后通過計(jì)算下式即可恢復(fù)主密鑰ki：

3 方案分析

3.1 可行性分析

性質(zhì)1 本文方案滿足多重密鑰共享方案定義中的重構(gòu)要求.

證明 這里只須證明式（1）是正確的.事實(shí)上，ki＝mod p＝·eimod p＝·ψ（Ph）mod p＝hshmod p.

3.2 安全性分析

引理1 設(shè)t維向量ei＝（0，…，0，1i，0，…，0）不能用中的向量v1，v2，…，vr線性表示，則存在向量ai＝（ai1，…，aii，…，ait）∈且aii＝1，使得v1·ai＝0，v2·ai＝0，…，vr·ai＝0.

證明 設(shè)vj＝（vj1，vj2，…，vjt），j＝1，2，…，r，要證明存在向量ai∈且aii＝1，使得v1·ai＝0，v2·ai＝0，…，vr·ai＝0，只須證明下列方程組存在解a′i＝（ai1，…，ai，i－1，ai，i＋1，…，ait）∈：

若v1i，…，vri全為0，則方程組（2）必存在解a′i＝（0，…，0）∈；若v1i，…，vri不全為0，這等價(jià)于要證明方程組（2）的系數(shù)矩陣M與增廣矩陣N有相同的秩.記r（M）為矩陣M的秩，r（N）為矩陣N的秩，下面只須證明r（M）＝r（N）.假設(shè)r（M）≠r（N），不妨設(shè)r（M）＜k，r（N）＝k，矩陣N的前k行向量線性無關(guān)，則矩陣M的前k行向量一定線性相關(guān)，從而存在一組不全為0的數(shù)h1，h2，…，hk∈Zp，使得

因此，β－1h1（v11，…，v1，i，…，v1t）＋…＋β－1hk（vk1，…，vk，i，…，vkt）＝（0，…，0，1，0，…，0）＝ei，這與eii不能用向量v1，v2，…，vr線性表示矛盾，從而r（M）＝r（N）.引理得證.

性質(zhì)2 本文的方案滿足多重密鑰共享方案定義中的安全性要求.

證明 設(shè)B∈Γi但BΓj（j≠i），不妨設(shè)B＝｛P1，P2，…，Pl｝.一方面，由于BΓj（j≠i），故B中參與者無法重構(gòu)主密鑰kj.事實(shí)上，由引理1知：存在向量aj∈且ajj＝1，使得aj·ψ（P1）＝0，…，aj·ψ（Pl）＝0，而B中參與者擁有的關(guān)于主密鑰kj的唯一信息是其中v＝＝（k1，…，kj，…，km，bm＋1，…，bt）；則對任意γ∈Zp，有即對任意∈Zp，存在向量v′＝（c1，…，…，ct）∈，使得故對B中參與者而言，Zp中的任意元素均可能是主密鑰kj的值，因此他們無法正確得到kj.

另一方面，由于B∈Γi，故由性質(zhì)1知，B中成員可以合作恢復(fù)出主密鑰ki.B中成員要想根據(jù)ki來求得其他主密鑰kj（j≠i）的值，只有存在某個(gè)向量ψ（Px），x∈｛1，2，…，l｝，使他的第i位和第j位的分量不為0，而其余分量均為0.不妨設(shè)ψ（Px）＝（0，…，0，，0，…，0，，0，…，0），此時(shí)參與者Px擁有的子密鑰sx＝hiki＋hjkj，由于sx，hi，hj，ki均已知，故參與者Px可從ki處獲得kj：kj＝（sx－h(huán)iki）；然而，由于B∈Γi，故ei＝（0，…，0，0，…，0）必可由ψ（B）＝｛ψ（Pi）｜Pi∈B｝中的向量線性表示，而ψ（Px）＝（0，…，0，0，…，0，…，0），因此ej＝（0，…，0，1，0，…，0）也必可由ψ（B）中的向量線性表示，與BΓj矛盾，這就表明不存在這樣的ψ（Px），從而B中成員無法根據(jù)已獲得的ki完全求得其他主密鑰kj（j≠i）的值.

性質(zhì)3 通過已知信息對方案進(jìn)行攻擊是不可行的.

證明 一方面，攻擊者企圖通過公開信息Tij＝xijG推導(dǎo)出xij是不可行的，因?yàn)檫@相當(dāng)于求解橢圓曲線離散對數(shù)這一難題；另一方面，“不良”參與者企圖通過sij＝xi·ψ（Pj）mod p推導(dǎo)出向量xi或xi的某個(gè)分量也是不可行的，因?yàn)橄蛄喀祝≒j）至少有兩個(gè)分量不為0.

性質(zhì)4 外部攻擊者和內(nèi)部不誠實(shí)的參與者會(huì)被有效地檢測出來.

證明 一方面，如果一個(gè)不誠實(shí)的參與者Pi想要欺騙參與者Pj而發(fā)送一個(gè)錯(cuò)誤的sij，則其行為會(huì)在密鑰生成之步驟3）被檢測出來；另一方面，如果授權(quán)子集A∈Γi中成員想要重構(gòu)密鑰ki，假設(shè)A中有一個(gè)不誠實(shí)的參與者或外部存在一個(gè)攻擊者“Pi”在恢復(fù)密鑰時(shí)提供一個(gè)假的子密鑰＝si＋ε，其中ε∈，然而在進(jìn)行密鑰重構(gòu)之步驟1）時(shí)，A中其他參與者將會(huì)發(fā)現(xiàn)G≠，從而攻擊行為被立即檢測到.

3.3 性能分析

本文方案中沒有第三方的參與，更加具有實(shí)際應(yīng)用價(jià)值，因?yàn)樵诂F(xiàn)實(shí)社會(huì)中要找到一個(gè)大家都信賴的人或機(jī)構(gòu)作為可信第三方是非常困難的；本文方案中的驗(yàn)證算法是基于橢圓曲線密碼學(xué)，而在達(dá)到同等安全性條件下，橢圓曲線密碼學(xué)的密鑰長度大約是RSA密碼學(xué)密鑰長度的1／6，所以本文方案僅需有限的存儲(chǔ)空間和傳輸帶寬；最后，當(dāng)有新的參與者加入時(shí)，僅須自己選取向量xi∈（）t并計(jì)算分發(fā)共享份額，而其他參與者無須改變自己的選取參數(shù).

［1］ SHAMIR A.How to share a secret［J］.Commun ACM，1979，22（11）：612－613.

［2］ BRICKELL E F.Some ideal secret sharing schemes［J］.J Combin Math Combin Comput，1989，9（6）：105－133.

［3］ INGEMARSSON I，SIMMONS G J.A protocol to set up shared secret schemes without the assistance of a mutually trusted party［C］／／Advances in Cryptology—EUROCRYPT’90.Lecture Notes in Computer Science.Berlin：Springer，1991，473：266－282.

［4］ PEDERSEN T P.A threshold cryptosystem without a trusted party［C］／／Advances in Cryptology—EUROCRYPT’91.Lecture Notes in Computer Science.Berlin：Springer，1991，547：522－526.

［5］ HARN L，LIN Chang－lu.Strong（n，t，n）verifiable secret sharing scheme［J］.Inf Sci，2010，180（16）：3059－3064.

［6］ HSU Ching－fang，CHENG Qi，TANG Xue－ming，et al.An ideal multi－secret sharing scheme based on MSP［J］.Inf Sci，2011，181（7）：1403－1409.

［7］ CHOR B，GOLDWASSER S，MICALI S，et al.Verifiable secret sharing and achieving simultaneity in the presence of faults［C］／／Proceedings of 26th Annual Symposium on Foundations of Computer Science.Oregon，Portland：IEEE，1985：383－395.

［8］ 唐春明，石桂花，湯永龍.沒有管理者的密鑰共享方案［J］.通信技術(shù)，2008，41（7）：175－182.

［9］ 劉佳，韓文報(bào).一種安全的公開可驗(yàn)證門限多秘密共享方案［J］.計(jì)算機(jī)工程，2009，35（1）：24－26.

［10］ DEHKORDI M H，MASHHADI S.An efficient threshold verifiable multi－secret sharing［J］.Computer Standards ＆Interfaces，2008，30（3）：187－190.

［11］ 王斌，宋朝霞.一種有效的（t，n）門限可驗(yàn)證多密鑰共享方案［J］.揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，12（3）：70－73.

［12］ 張險(xiǎn)峰，秦志光，劉錦德.橢圓曲線加密系統(tǒng)的性能分析［J］.電子科技大學(xué)學(xué)報(bào)，2001，30（2）：144－147.

Abstract：A verifiable vector space multi－secret sharing scheme is proposed.Its security is based on the security of elliptic curve cryptography.This scheme has the following characteristics：there is no trusted center，so the cost can be saved greatly；all the participants cooperate to generate the secrets and distribute the corresponding shares；all participants can share multiple secrets，but each participant just needs to save one sub－key；the cheating between participants and the attack from outsiders can be detected；the current scheme is just needs limited memory and communication bandwidth，so it is valuable in practical applications.

Keywords：vector space secret sharing；multi－secret sharing；without a trusted center；elliptic curve cryptography

（責(zé)任編輯 時(shí) 光）

A verifiable multi－secret sharing scheme without a trusted center

ZHANG Ben－h(huán)ui，JIANG Wei，TANG Yuan－sheng＊
（Sch of Math Sci，Yangzhou Univ，Yangzhou 225002，China）

TP 309.2

A

1007－824X（2012）02－0065－05

2011－09－29

國家自然科學(xué)基金資助項(xiàng)目（60971123）

＊聯(lián)系人，E－mail：ystang＠yzu.edu.cn