一個有效的無證書門限簽密方案

崔金玲, 孫 華

(安陽師范學院 計算機與信息工程學院, 河南 安陽 455000)

0 引言

無證書密碼的概念由AL-RIYAMI等[1]于2003提出，由于其不需使用證書，同時又克服了基于身份密碼體制中的密鑰托管問題，因而對無證書密碼的研究引起了不少學者的興趣，并取得了一系列的研究成果.

簽密能夠同時實現(xiàn)機密性和認證性這兩個安全目標.無證書簽密概念由BARBOSA等[2]于2008年提出，并且在隨機預(yù)言模型下提出了一個無證書的簽密方案.ARANHA等[3]提出一個僅需兩個雙線性對運算的無證書簽密方案，然而其沒有對方案的安全性進行證明.同年，WU等[4]也提出一個新的無證書簽密方案，該方案在簽密和解簽密階段需要4個雙線性對運算，不幸的是，文獻[5]指出該方案是不安全的.首個無證書多接收者簽密方案由SELVI等[6]提出，然而該方案在第一類攻擊者面前是不安全的.在標準模型方面，第一個無須借助隨機預(yù)言機可證安全的無證書簽密方案由LIU等[7]提出，然而WENG等[8]通過分析指出方案的語義安全性和不可偽造性這兩個安全目標在第二類攻擊者攻擊下無法實現(xiàn).文獻[9]和文獻[10]同樣給出了兩個標準模型下的無證書簽密方案，然而它們同樣是不安全的.

在面向群體的通信中，需要同時具有保密性和認證性的應(yīng)用場合越來越多，而面向群體的簽密體制可以較好地滿足這種安全需求.門限簽密不僅能夠?qū)崿F(xiàn)這一安全目標，并且能夠有效防止單點失效.目前，已有的門限簽密方案[11-13]大都是在身份密碼體制下基于隨機預(yù)言模型提出的.在該模型中，Hash函數(shù)被看成是完全隨機的函數(shù).然而在該模型下被證明是安全的方案并不代表是真正的安全，因此本文在標準模型下提出的無證書門限簽密方案更有實際意義.

1 預(yù)備知識

1.1 雙線性對

設(shè)G、GT是兩個階為素數(shù)p的循環(huán)群，g是群G的生成元，雙線性對是具有如下性質(zhì)的映射e:G×G→GT：

1. 雙線性：對于任意的P,Q∈G和a,b∈Zp，都有e(aP,bQ)=e(P,Q)ab；

2. 非退化性：e(g,g)≠1；

3. 可計算性：對于任意的P,Q∈G，存在一個有效的算法計算e(P,Q).

1.2 困難問題

3.q-ABDHE問題：給定群G中一個含有(q+3)個元素組成的向量(g′,g′aq+2,g,ga,ga2,…,gaq)及Z∈GT，判定等式Z=e(gaq+1,g′)是否成立.

2 本文的無證書門限簽密方案

方案描述：設(shè){ID1,…,IDn}是用于產(chǎn)生門限簽密的身份為US的n個成員集合，不妨設(shè)ID1,…,IDt是代表US對消息M進行簽密的t個成員，IDR為簽密接收者.給定階為素數(shù)p的循環(huán)群G和GT，雙線性映射e:G×G→GT，對于任意長度的消息M，哈希函數(shù)H:{0,1}*→{0，1}nm輸出長度為nm的位串.

1)系統(tǒng)參數(shù)產(chǎn)生算法

2)部分私鑰產(chǎn)生算法

對于身份為ID∈Zp的用戶，KGC任意選取rID∈Zp，計算d1=(h1g-rID)1/α-ID.如果ID=α，那么KGC將重新選擇并計算；否則，令d2=rID，并將DID=(d1,d2)作為用戶的部分私鑰.

3)秘密值分享算法

①對于產(chǎn)生門限簽密的各成員IDi，其首先隨機選取秘密值xIDi∈Zp及系數(shù)在Zp、次數(shù)為t-1的多項式hi(x)=ci,0+ci,1x+…+ci,t-1xt-1，其中ci,0=xIDi.然后IDi向其他成員IDj(j≠i)廣播參數(shù)Ei,d=gci,d(d=0,1,…,t-1)，計算秘密分享xi,j=hi(j)，并將它們發(fā)送給其他各成員.

4)用戶公鑰產(chǎn)生算法

5)用戶私鑰產(chǎn)生算法

6)簽密

給定用來產(chǎn)生門限簽密的n個成員的集合US，身份為IDR的門限簽密接收者，待簽密消息M∈GT.各成員IDi首先產(chǎn)生其部分簽密，然后將其發(fā)送給US中任一用以生成門限簽密的集成者dealer，該過程執(zhí)行如下：

為拉格朗日系數(shù).

③該dealer計算

則最終的無證書門限簽密為C=(C1,C2,C3,C4,C5,C6,T).

7)解簽密

設(shè)簽密產(chǎn)生者的身份為IDS，簽密接收者IDR的私鑰為SKIDR，其在收到無證書門限簽密C=(C1,C2,C3,C4,C5,C6,T)后，進行如下計算：

②如果上式成立，則C是一個有效的密文，那么簽密接收者IDR能夠利用其私鑰SKIDR通過下式恢復(fù)出消息

3 安全性分析

3.1 方案正確性

方案的正確性很容易得到驗證，限于篇幅原因這里省略.

3.2 不可區(qū)分性

定理1 如若q-ABDHE是困難問題，對于第一類攻擊者AI，本方案滿足適應(yīng)性選擇密文攻擊下的不可區(qū)分性.

證明設(shè)敵手AI能夠成功攻破本方案，則可以構(gòu)造算法B，其可利用敵手AI解決q-ABDHE問題，而這與q-ABDHE是一個困難問題相矛盾.

輸入算法B的q-ABDHE問題實例(g′,g′aq+2,g,ga,ga2,…,gaq,Z)，其目標是判定等式

Z=e(g,g′)aq+1

是否滿足.這里算法B模擬AI的挑戰(zhàn)者C與其交互如下：

Phase1：敵手AI可發(fā)起如下7種形式的詢問，同時算法B需使用4個初始為空的列表L1、L2、L3和L4.

然后在列表L1中添加(M,T).

②部分私鑰詢問：當對身份IDi的部分私鑰DIDi進行詢問時，如果IDi=a，算法B可以利用a解決q-ABDHE問題；否則，令q-1階多項式為fq-1(x)=fq(x)-f(IDi)/x-IDi，算法B計算d1=gfq-1(a)，d2=fq(a)，并把(IDi,DIDi)添加到列表L2中，這里DIDi=(d1,d2)，最后將DIDi作為結(jié)果返回.

④用戶私鑰詢問：當詢問身份IDi的私鑰SKIDi時，如果(IDi,SKIDi)存在于列表L4，則返回SKIDi；否則，算法B分別從列表L2、L3中查詢(IDi,DIDi)和(IDi,PKIDi,xIDi,c)，令SKIDi=(DIDi,xIDi)，然后把(IDi,SKIDi)添加到列表L4中，最后將SKIDi作為結(jié)果返回.

⑥簽密詢問：當敵手AI對(M,IDS,IDR)發(fā)起簽密詢問時，若IDS=a，那么算法B可以利用a解決q-ABDHE問題；否則，算法B能夠構(gòu)造IDS的私鑰，然后運行簽密算法并返回相應(yīng)的門限簽密C=(C1,C2,C3,C4,C5,C6,T).

⑦解簽密詢問：當敵手AI對C發(fā)起解簽密詢問時，若IDR=a，那么算法B可以利用a解決q-ABDHE問題；否則，算法B從列表L4中查詢接收者的私鑰SKIDR，然后運行解簽密算法恢復(fù)出消息m并把它發(fā)送給AI.

令s=(loggg′)fq+1(a)，如果Z=e(gaq+1,g′)，則有

Guess：敵手AI輸出b′作為b的猜測.如果b=b′，那么B輸出Z=e(gaq+1,g′)作為q-ABDHE問題的解.證畢.

定理2 如若DBDH是困難問題，對于第二類攻擊者AII，本方案滿足適應(yīng)性選擇密文攻擊下的不可區(qū)分性.

證明設(shè)敵手AII能夠成功攻破本方案，則可以構(gòu)造算法B，其可利用敵手AII解決DBDH問題，而這與DBDH是一個困難問題相矛盾.

輸入算法B的DBDH問題實例(ga,gb,gc,h)，其目標是判定等式h=e(g,g)abc是否成立.這里算法B模擬AII的挑戰(zhàn)者C與其交互如下：

Phase1：敵手AII可如同定理1中那樣進行詢問，由于敵手AII知道主密鑰，故無須進行部分私鑰詢問.此外，它不能夠進行公鑰替換詢問.

Phase2：敵手AII可如同定理1中那樣進行詢問.

Guess：敵手AI輸出b′作為b的猜測.如果b=b′，那么B輸出h=e(g,g)abc作為DBDH問題的解.證畢.

3.3 不可偽造性

定理3 如若q-SDH是困難問題，本方案在第一類攻擊者AI攻擊下滿足存在不可偽造性.

證明如果敵手AI能夠成功偽造一個有效的密文，則存在算法B，它可以利用AI解決q-SDH問題，而這與q-SDH是一個困難問題相矛盾.

輸入算法B的q-SDH問題實例(g,ga,ga2,…,gaq)，其目標是利用敵手AI計算(c,g1/a+c).這里算法B模擬AI的挑戰(zhàn)者C與其交互如下：

Setup: 算法B如同定理1中那樣構(gòu)造系統(tǒng)參數(shù)，并將params發(fā)送給敵手AI，不同之處在于h2=g-u.

Attack：

①當敵手AI發(fā)起H1詢問、用戶公鑰詢問、用戶私鑰詢問以及公鑰替換詢問時，算法B如同定理1中第一階段那樣進行響應(yīng).

②部分私鑰詢問：當對身份IDi的部分私鑰DIDi進行詢問時，如果IDi=a，算法B可利用a解決q-SDH問題；否則，算法B采取與定理1中相同的方式進行響應(yīng).

③簽密詢問：當對(M,IDS,IDR)發(fā)起簽密詢問時，若IDS=a，算法B可利用a解決q-SDH問題；否則，算法B采取與定理1中相同的方式進行響應(yīng).

④解簽密詢問：當敵手AI對C發(fā)起解簽密詢問時，若IDR=a，算法B可以利用a解決q-SDH問題；否則，算法B采取與定理1中相同的方式進行響應(yīng).

如果A-1=0，那么算法B將失敗退出；否則，可以得到

則q-SDH問題的解為

證畢.

定理4 如若CDH是困難問題，本方案在第二類攻擊者AII攻擊下滿足存在不可偽造性.

證明如果敵手AII能夠成功偽造一個有效的密文，則存在算法B，它可以利用AII解決CDH問題，而這與CDH是一個困難問題相矛盾.

輸入算法B的CDH問題實例(ga,gb)，其目標是利用敵手AII計算gab.這里算法B模擬AII的挑戰(zhàn)者C與其交互如下：

Attack：敵手AII可如同定理3中那樣進行詢問.由于敵手AII知道主密鑰，故無須進行部分私鑰詢問.同時，它不能夠進行公鑰替換詢問.

則有

4 性能分析

因雙線性對運算的開銷遠大于群元素的其他計算開銷，故這里只考慮雙線性對的運算.假定門限簽密方案中的門限值為t，成員總數(shù)為n.這里可通過對z0=e(g,g)和z1=e(g,h1)進行預(yù)計算來提高計算效率.

表1 門限簽密方案的比較

通過表1對比可知，本文所提出的方案具有較低的計算開銷.

5 結(jié)論

本文提出了一個安全且具有較高效率的無證書門限簽密方案.如何設(shè)計具有特定應(yīng)用背景的無證書密碼方案，且具有較少的運算量和通信開銷，是我們下一步將繼續(xù)開展的工作.