基于ECC的存在特權(quán)集的門限群簽名方案

董玉蓉

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽 520025）

基于ECC的存在特權(quán)集的門限群簽名方案

董玉蓉

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽 520025）

通過對(duì)一種ElGamal類型存在特權(quán)集的門限群簽名方案的分析研究,提出了一種基于ECC的存在特權(quán)集的門限群簽名方案。該方案能有效防止KDC的欺詐,且只有在同時(shí)滿足（t，n）和（t1，n1）門限簽名時(shí)才能生成消息的有效簽名，從而實(shí)現(xiàn)了門限特性，并具有門限群簽名應(yīng)有的性質(zhì)。

特權(quán)集；秘密共享；門限群簽名；ECC

群簽名方案首次由Chanm和VanHeyst于1991年提出。在群簽名方案中，允許每個(gè)成員都可以代表整個(gè)群體進(jìn)行簽名。在群簽名方案中引入秘密共享，解決密鑰安全與有效保管問題的同時(shí)也形成了一類新的群簽名方案——門限群簽名方案，即群體中的某些給定子集可以代表整個(gè)群體簽名。在門限群簽名方案中，門限群簽名是由參加簽名的各個(gè)成員所簽署的部分?jǐn)?shù)字簽名按照某種方式結(jié)合后產(chǎn)生。2003年，BELLARE M等人提出了群簽名的簡(jiǎn)化形式定義[1]。在這之后，不少學(xué)者提出的門限群簽名方案均采用形式化的方法證明方案的安全性。參考文獻(xiàn)[2]提出良好的門限群簽名應(yīng)該具備以下一些性質(zhì)：群簽名特性、門限特性、不可偽造性、驗(yàn)證簡(jiǎn)單性、匿名性、可追查性、強(qiáng)壯性。參考文獻(xiàn)[3]中，Chen Feng等人基于Shamir秘密共享體制并結(jié)合 “存在特權(quán)集的門限群簽名方案”的思想[4]，構(gòu)造了一類基于離散對(duì)數(shù)問題的ElGamal類型的存在特權(quán)集的門限群簽名方案。

本文利用橢圓曲線密碼體制的特點(diǎn)對(duì)Chen Feng的方案進(jìn)行改進(jìn)。新的方案與原方案的共同點(diǎn)在于都使用雙重秘密共享技術(shù)和單簽名構(gòu)造群簽名的技術(shù)[3]，不同之處在于新方案實(shí)現(xiàn)了群成員的加入和撤銷，提高了方案的通用性。同時(shí)，為了防止密鑰分配中心的欺詐[5]，各用戶對(duì)自己私鑰的有效性進(jìn)行了驗(yàn)證，并且利用橢圓曲線密碼體制的特點(diǎn)優(yōu)化本方案，進(jìn)而提高了方案的效率和安全性。

1 一種ElGamal類型的存在特權(quán)集的門限群簽名方案

Chen Feng依據(jù)離散對(duì)數(shù)問題提出了一種存在特權(quán)集的ElGamal類型門限群簽名方案。

其基本設(shè)計(jì)流程如下：

（1）初始化：由可信的密鑰認(rèn)證中心KAC選取2個(gè)安全參數(shù)p、q，在有限域Fq上隨機(jī)選取兩個(gè)多項(xiàng)式 f（x）、g（x）,次數(shù)分別為（t-1）、（t1-1），并取有限域 Fq的本原元α。

（2）群密鑰及秘密碎片的產(chǎn)生：群密鑰d及群公鑰z由KAC隨機(jī)選取的兩個(gè)多項(xiàng)式構(gòu)成。利用“雙重”SSS秘密共享方案為各簽名者建立公私鑰碎片。

（3）簽名：群簽名由參與簽名的成員和簽名服務(wù)機(jī)構(gòu)SC共同生成：每個(gè)成員先生成自己的單簽名，然后發(fā)送給SC驗(yàn)證該單簽名是否為合法簽名，再由SC決定是否接受；如果接受的單簽名滿足門限要求，則計(jì)算組合出群對(duì)消息的簽名。

Chen Feng方案可簡(jiǎn)單描述為：在計(jì)算機(jī)網(wǎng)絡(luò)開放式環(huán)境下，一個(gè)能夠被完全信任的中心是不存在的。該方案的群密鑰和群成員的秘密份額都由可信的密鑰認(rèn)證中心決定，不能保證密鑰認(rèn)證中心分發(fā)給各用戶的密鑰碎片有效，存在密鑰分配中心欺詐的問題。此外方案沒有考慮到群成員的安全有效的加入和撤銷，因此不滿足群簽名的特性。

2 本文方案

本文提出的基于ECC的存在特權(quán)集的門限群簽名方案共分為六個(gè)階段：系統(tǒng)初始化、群密鑰產(chǎn)生、群成員的加入和撤銷、密鑰分發(fā)、單個(gè)簽名生成與驗(yàn)證、群簽名生成。

2.1 系統(tǒng)初始化階段

該方案的系統(tǒng)參數(shù)意義如下：

KDC：密鑰分配中心；

Clerk：簽名服務(wù)者，負(fù)責(zé)頒布簽名；

G：由n個(gè)簽名方組成的群體,至少有其中t方參與才可產(chǎn)生合法簽名；

G1：G 的子集，有 n1（n1＜n）個(gè)成員。 至少有其中 t1（t1＜t）方參與才可產(chǎn)生合法簽名，稱為特權(quán)子集；

G2：G的子集，其中的簽名方為普通用戶；

ui：群成員 pi的公開身份；

IDi：群成員 pi的真實(shí)身份。

該方案的安全參數(shù)描述為：

（1）密鑰分配中心KDC給定任一有限域Fp（p為大素?cái)?shù)），并定義 Fp上的一條安全橢圓曲線 E（Fp），保證該橢圓曲線的離散對(duì)數(shù)問題是難解的。在E（Fp）上選一基點(diǎn)P，其階數(shù)為 q（q為一個(gè)大于 160 bit的大素?cái)?shù)）。另外，KDC還選擇一個(gè)單向安全的Hash函數(shù)H（）。

（2）KDC構(gòu)造 2個(gè)秘密多項(xiàng)式 f（x）∈RFq[x]，g（x）∈RFq[x]，次數(shù)分別為（t-1）和（t1-1）。

其 中 ，a0=f（0），b0=g（0），ai，bj∈Zq*（i=1，2，… ，t-1；j=1，2，…，t1-1）。

2.2 群密鑰的產(chǎn)生

群密鑰：由 KDC產(chǎn)生，即 d=[f（0）+g（0）]=a0+b0。

群公鑰：Y=（a0+b0）·P。

Clerk隨機(jī)地為用戶pi選擇群內(nèi)公開身份ui∈Zq*。

2.3 群成員的加入

（1）群成員 pi隨機(jī)選取 ki∈Zq*，并計(jì)算 Ri=ki·P=（xi，yi），并將（ki，Ki）在群內(nèi)公開。

（2）簽名服務(wù)者 Clerk通過驗(yàn)證 Ri≠Rj（i≠j）是否成立，來檢驗(yàn)群成員pi、pj是否選擇了同樣的隨機(jī)數(shù)。若Ri=Rj，說明這兩個(gè)群成員選擇了相同的隨機(jī)數(shù)，則Clerk通知他們重新選取并進(jìn)行計(jì)算。若Ri≠Rj，則進(jìn)行下一步。

（4）Clerk驗(yàn)證 σi=H（ui||IDi）是否成立：

若 σi≠H（ui||IDi），則說明群成員 pi偽造了一個(gè)群內(nèi)公開身份，Clerk拒絕pi加入簽名生成過程，并通知KDC拒絕為其分發(fā)秘密鑰碎片。

若 σi=H（ui||IDi），則接受 pi加入，通知 KDC為其分發(fā)秘密鑰碎片。

（5）群成員的撤銷。設(shè)該系統(tǒng)現(xiàn)有k（k≥t）個(gè)群成員，撤銷群成員pj的過程如下：Clerk將pj在群內(nèi)的公開身份uj置為1。在驗(yàn)證用戶身份合法性時(shí)，若檢測(cè)到σj=H（1），則拒絕 pj加入簽名群，同時(shí)通知 KDC拒絕 pj為分發(fā)秘密鑰碎片。

2.4 密鑰分配及驗(yàn)證

（1）密鑰分配

秘密鑰碎片分 發(fā)采用 “雙重”SSS[3]，分 別是（t，n）和（t1，n1）門限。將密鑰d分割成多種組合，d的每種組合都與包含t個(gè)不同用戶的子集相對(duì)應(yīng)。

如果群成員pi是普通用戶，則得到相對(duì)應(yīng)的秘密碎片 di=f（xi），并由 KDC在群內(nèi)廣播其公鑰 Yi=di·P=f（xi）·P；如果群成員pi是特權(quán)集用戶，則得到的秘密碎片為di=[f（xi）+g（yij）]，由 KDC公開其公鑰為 Yi=di·P=[f（xi）+g（yij）]·P。以上的過程利用“雙重”SSS秘密共享方案為各群成員建立了公、私鑰碎片。

最后，KDC 公開參數(shù)為：E（Fp），P，p，q，H（）。

（2）群成員對(duì)各自密鑰的驗(yàn)證

根據(jù) Pedersen VSS驗(yàn)證方法[5]，群成員 pi可通過式（1）和式（2）驗(yàn)證KDC為其分配的密鑰di的有效性：若群成員pi為特權(quán)集用戶，則驗(yàn)證：

若等式成立，證明KDC分配給群成員pi的密鑰di是正確、有效的。否則就說明KDC欺詐。

2.5 單個(gè)簽名生成與驗(yàn)證

假設(shè)現(xiàn)有t個(gè)群成員參與群簽名的生成，設(shè)被簽署的消息為m。則簽名步驟如下：

項(xiàng)式得出。簽名者pi發(fā)送（m，si）給 Clerk。

（3）Clerk驗(yàn)證單簽名：Clerk接收到各個(gè)簽名消息si后，利用簽名者pi的公鑰驗(yàn)證其單個(gè)簽名的有效性，驗(yàn)證等式為:

若等式成立，則接受該單簽名，否則拒絕接受單簽名。

2.6 群簽名的生成

3 方案分析

3.1 正確性分析

（1）單簽名的驗(yàn)證

假設(shè)至少有 t個(gè)人參與簽名，且恰為 1，2，…，t，其中至少有t1個(gè)人屬于特權(quán)用戶集，并且簽名者沒有欺詐行為。不論是普通用戶還是特權(quán)用戶,都可以通過式（3）驗(yàn)證單簽名的正確性。

上述過程驗(yàn)證了單簽名的正確性。

（2）群簽名的驗(yàn)證

假設(shè)簽名組成員都嚴(yán)格按照簽名的步驟對(duì)消息進(jìn)行簽名，就有

所以有：

上述過程通過式（3）對(duì)群簽名的正確性進(jìn)行了驗(yàn)證。

3.2 安全性分析

根據(jù)門限群簽名的特性對(duì)該方案進(jìn)行安全性分析。

（1）匿名性

由于簽名者使用的是公開身份，公開身份和真實(shí)身份的對(duì)應(yīng)關(guān)系只有Clerk和簽名者本身知道。其他用戶只知道通過廣播信道傳播出的Ri的值，并不能依據(jù)Ri來確定用戶的真實(shí)身份，也就無法根據(jù)群簽名（在未經(jīng)特許的情況下）追蹤各簽名方的真實(shí)身份。因此該方案具有匿名性。

（2）不可偽造性

參與簽名的群成員只有獲得合法身份，才能獲得秘密鑰碎片進(jìn)而生成有效的部分簽名，非法用戶無法偽造有效部分簽名。Clerk通過驗(yàn)證σi=H（ui||IDi）來確定群成員的身份是否合法。

（3）可追查性

如果事后簽名出現(xiàn)矛盾，在得到許可的情況下，需要調(diào)查哪些成員參與簽名，Clerk很容易確定簽名方的真實(shí)身份。

（4）抗合謀攻擊

在秘密鑰碎片的分發(fā)上采用“雙重”SSS。當(dāng)進(jìn)行合謀攻擊時(shí)，如果不符合特權(quán)條件的要求，即使有t個(gè)或t個(gè)以上簽名者參與，g（0）的恢復(fù)也是不可能的，進(jìn)而無法得到群密鑰；如果有不足t個(gè)人參與簽名，即使符合特權(quán)條件的要求（g（0）可以恢復(fù)）也不可能恢復(fù) f（0），從而無法得到群密鑰?？梢?，該方案能抵抗合謀攻擊。

（5）可撤銷性

簽名者pi被撤銷后，在開始新的簽名過程時(shí)，KDC公布了新的Y′，pj就不能繼續(xù)參與群簽名的生成，因?yàn)榇藭r(shí)群公鑰由原來的Y變成了Y′。

若簽名者pj繼續(xù)使用原來的私鑰dj參與新的群簽名的生成，Clerk在收到 pj的單簽名 sj后，要根據(jù) pj的公鑰Yj驗(yàn)證式（3）是否成立。然而Clerk在信道內(nèi)無法獲得與 pj相對(duì)應(yīng)的 Yj，也就無法驗(yàn)證式（3），因此 Clerk拒絕接受該單簽名。所以，被撤銷后的簽名者pj并不能繼續(xù)參與群簽名的生成。

（6）門限特性

由于方案是基于雙重Shamir秘密共享建立的，因此在簽名階段具有門限方案的安全性：任意少于t個(gè)群的成員無法得到有效簽名，且任意少于t1個(gè)特權(quán)集成員也無法得到有效簽名。

3.3 效率分析

本方案的建立基于橢圓曲線密碼體制，與ElGamal類型的基于離散對(duì)數(shù)問題的原方案相比密鑰長度和簽名長度都大大降低。

ECC算法只需采用較短的密鑰就可達(dá)到與離散對(duì)數(shù)算法相同的加密強(qiáng)度。ECC算法具有每比特最高的安全強(qiáng)度。由于智能卡在CPU處理能力和RAM大小上受限，采用一種運(yùn)算量小但同時(shí)能提供高加密強(qiáng)度的公鑰密碼機(jī)制對(duì)于實(shí)現(xiàn)數(shù)字簽名的應(yīng)用非常關(guān)鍵。ECC在這方面具有明顯的優(yōu)勢(shì)，160 bit ECC算法的安全性與1 024 bit采用基于離散對(duì)數(shù)問題的算法安全性相同。因此，采用橢圓曲線密碼體制設(shè)計(jì)的門限群簽名方案的計(jì)算量和通信量都要小于基于離散對(duì)數(shù)問題的ElGamal密碼體制的門限群簽名方案。

本文基于橢圓曲線密碼體制和雙重Shamir秘密共享體制，結(jié)合Chen Feng的特權(quán)集思想，設(shè)計(jì)了一個(gè)同時(shí)具有門限群簽名功能和門限共享驗(yàn)證功能的存在特權(quán)集的門限群簽名方案，該方案不但克服了目前一些方案的缺陷和弱點(diǎn)，而且具有更高的實(shí)現(xiàn)效率。方案除了具有門限群簽名的性質(zhì)外，還可以利用公開驗(yàn)證功能防止KDC欺詐。相對(duì)于原方案，本方案是基于橢圓曲線密碼體制建立的，在安全性和效率方面考慮得更全面。但是，如何將該方案推廣到實(shí)際應(yīng)用中，仍有待于進(jìn)一步研究。

[1]BELLARE M，MICCIANCIO D，WARINSCHI B.Foundation of group signatures:formal definitions,simplified requirements,and a construction based on generalassumptions[C].Proc of EUROCRPT 2003，LNCS2656.Berlin:Springer-Verlag，2003：614-629.

[2]王貴林，卿斯?jié)h.幾個(gè)門限群簽名方案的弱點(diǎn)[J].軟件學(xué)報(bào)，2000，11（10）：1326-1332.

[3]陳偉東，馮登國.一類存在特權(quán)集的門限群簽名方案[J].軟件學(xué)報(bào)，2005，16（7）：1289-1295.

[4]石怡，馮登國.一類新型（tj，t，n）-門限群簽名方案的設(shè)計(jì)與分析[M].北京：科學(xué)出版社，2000.

[5]彭長根，李祥，羅文俊.一種面向群組通信的通用門限簽密方案[J].電子學(xué)報(bào)，2007，35（1）：64-67.

Threshold group signature scheme with privilege subsets based on ECC

Dong Yurong

（Computer Science and Information College,Guizhou University,Guiyang 520025，China）

Through the analysis and study of a threshold group signature scheme which is based on ElGamal type,in order to solve the deficiency of the scheme,a new threshold group signature scheme with privileged subsets based on ECC is proposed.The proposed scheme can prevent the fraud of KDC efficiently.Only when the scheme satisfiesand（t，n）and（t1，n1）threshold signature,the valid signature can be generated,thus the scheme reached the property of threshold.The program also has the properties of threshold group signature.

privileged subjects；secret sharing；threshold group signature；ECC

TP309

A

1674-7720（2011）02-0089-04

2010-07-31）

董玉蓉，女，1985年生，碩士研究生，主要研究方向：密碼學(xué)與信息安全。