崔金玲, 孫 華

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

0 引言

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

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

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

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

1.1 雙線性對(duì)

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

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

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

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

1.2 困難問題

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

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

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

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

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

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

3)秘密值分享算法

①對(duì)于產(chǎn)生門限簽密的各成員IDi，其首先隨機(jī)選取秘密值xIDi∈Zp及系數(shù)在Zp、次數(shù)為t-1的多項(xiàng)式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)，計(jì)算秘密分享xi,j=hi(j)，并將它們發(fā)送給其他各成員.

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

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

6)簽密

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

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

③該dealer計(jì)算

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

7)解簽密

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

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

3 安全性分析

3.1 方案正確性

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

3.2 不可區(qū)分性

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

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

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

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

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

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

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

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

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

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

⑦解簽密詢問：當(dāng)敵手AI對(duì)C發(fā)起解簽密詢問時(shí)，若IDR=a，那么算法B可以利用a解決q-ABDHE問題；否則，算法B從列表L4中查詢接收者的私鑰SKIDR，然后運(yùn)行解簽密算法恢復(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是困難問題，對(duì)于第二類攻擊者AII，本方案滿足適應(yīng)性選擇密文攻擊下的不可區(qū)分性.

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

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

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

Phase2：敵手AII可如同定理1中那樣進(jìn)行詢問.

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

3.3 不可偽造性

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

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

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

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

Attack：

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

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

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

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

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

則q-SDH問題的解為

證畢.

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

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

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

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

則有

4 性能分析

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

表1 門限簽密方案的比較

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

5 結(jié)論

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