無可信第三方的可驗證多重密鑰共享方案

張本慧，蔣 偉，唐元生

（揚州大學數(shù)學科學學院，江蘇揚州225002）

無可信第三方的可驗證多重密鑰共享方案

張本慧，蔣 偉，唐元生＊

（揚州大學數(shù)學科學學院，江蘇揚州225002）

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

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

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

1 預備知識

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

1）重構要求.對于每個i，1≤i≤m，si∈Si可被Γi的任何授權集重構，即存在重構函數(shù)族Re＝｛：（S1×…×Sn）A→Si｜1≤i≤m，A∈Γi｝，使得對任意的A∈Γi，（s1，…，sm）∈S1×…× Sm，u∈U都有（Π（s1，…，sm，u）｜A）＝si；這等價于要求對每個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）；這也等價于要求對1≤i≤m的任意BΓi和T｛S1，…，Sm｝＼｛Si｝，滿足0＜H（Si｜SB，T）≤H（Si｜T）.

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

2 方案描述

2.1 系統(tǒng)初始化

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

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

2.2 密鑰生成

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

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

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

4）如果所有的sij通過了驗證，則每個參與者Pj可以計算自己的子密鑰為sj＝此時隨機默認生成的m個主密鑰即為

2.3 密鑰重構

不失一般性，假設Γi中授權子集A＝｛P1，P2，…，Pl｝準備重構主密鑰ki.

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

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

3 方案分析

3.1 可行性分析

性質1 本文方案滿足多重密鑰共享方案定義中的重構要求.

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

3.2 安全性分析

引理1 設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.

證明 設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，這等價于要證明方程組（2）的系數(shù)矩陣M與增廣矩陣N有相同的秩.記r（M）為矩陣M的秩，r（N）為矩陣N的秩，下面只須證明r（M）＝r（N）.假設r（M）≠r（N），不妨設r（M）＜k，r（N）＝k，矩陣N的前k行向量線性無關，則矩陣M的前k行向量一定線性相關，從而存在一組不全為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）.引理得證.

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

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

另一方面，由于B∈Γi，故由性質1知，B中成員可以合作恢復出主密鑰ki.B中成員要想根據(jù)ki來求得其他主密鑰kj（j≠i）的值，只有存在某個向量ψ（Px），x∈｛1，2，…，l｝，使他的第i位和第j位的分量不為0，而其余分量均為0.不妨設ψ（Px）＝（0，…，0，，0，…，0，，0，…，0），此時參與者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）的值.

性質3 通過已知信息對方案進行攻擊是不可行的.

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

性質4 外部攻擊者和內部不誠實的參與者會被有效地檢測出來.

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

3.3 性能分析

本文方案中沒有第三方的參與，更加具有實際應用價值，因為在現(xiàn)實社會中要找到一個大家都信賴的人或機構作為可信第三方是非常困難的；本文方案中的驗證算法是基于橢圓曲線密碼學，而在達到同等安全性條件下，橢圓曲線密碼學的密鑰長度大約是RSA密碼學密鑰長度的1／6，所以本文方案僅需有限的存儲空間和傳輸帶寬；最后，當有新的參與者加入時，僅須自己選取向量xi∈（）t并計算分發(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］.通信技術，2008，41（7）：175－182.

［9］ 劉佳，韓文報.一種安全的公開可驗證門限多秘密共享方案［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）門限可驗證多密鑰共享方案［J］.揚州大學學報：自然科學版，2009，12（3）：70－73.

［12］ 張險峰，秦志光，劉錦德.橢圓曲線加密系統(tǒng)的性能分析［J］.電子科技大學學報，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

（責任編輯 時 光）

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

國家自然科學基金資助項目（60971123）

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