基于身份可公開驗(yàn)證的簽密方案

文毅玲 馬建峰

西安電子科技大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 陜西 710071

0 引言

簽密由Zheng1997年提出，它是一種公鑰密碼原型，其設(shè)計(jì)思想是在一個(gè)邏輯步驟內(nèi)同時(shí)完成數(shù)字簽名和公鑰加密兩項(xiàng)功能，從而其計(jì)算量和通信成本都要低于傳統(tǒng)的“先簽名后加密”方式。因此，簽密特別適用于能量受限的（如低能移動(dòng)元件，靈通卡和新興傳感器等），既需保密性又需認(rèn)證性的消息傳輸環(huán)境中。簽密技術(shù)已經(jīng)得到廣泛應(yīng)用，如電子現(xiàn)金支付等。

1 新方案及其安全性與效率

1.1 新方案的描述

Setup：設(shè)為由p生成的循環(huán)加群，階為q，為具有相同階q的循環(huán)乘法群，為一個(gè)雙線性映射。定義四個(gè)安全的Hash函數(shù)，和PKG隨機(jī)選擇一個(gè)主密鑰，計(jì)算。PKG公開系統(tǒng)參數(shù)保密主密鑰s。

Keygen：給定一個(gè)用戶U的身份，PKG計(jì)算該用戶的私鑰，其中為該用戶的公鑰。在這里，記發(fā)送者Alice的身份為，公鑰為，私鑰為接收者Bob的身份為，公鑰為，私鑰為

Signcrypt：為了發(fā)送一個(gè)消息給Bob，Alice執(zhí)行以下步驟：

（4）發(fā)送密文（，）cWσ=給Bob；

Unsigncrypt：當(dāng)收到密文σ時(shí)，Bob計(jì)算恢復(fù)消息

Verify：如果等式成立，Bob接受這個(gè)消息m，否則認(rèn)為σ不合法。

1.2 安全性

定理1 在隨機(jī)預(yù)言模型中，若存在一個(gè)IND-IBSC-CCIA敵手Malice能夠在t時(shí)間內(nèi)，以ε的優(yōu)勢(shì)贏得游戲（他最多能進(jìn)行次詢問次Signcrypt詢問，qu次Unsigncrypt詢問，則存在一個(gè)區(qū)分者C，能夠在時(shí)間內(nèi)，以的優(yōu)勢(shì)解決BDH問題，其中表示計(jì)算一次雙線性對(duì)運(yùn)算所需要的時(shí)間。

證明：設(shè)區(qū)分者C收到一個(gè)隨機(jī)的BDH問題實(shí)例他的目標(biāo)是計(jì)算出。C把Malice作為子程序并扮演IND-IBSC-CCIA游戲中的Malice的挑戰(zhàn)者。游戲一開始，C將系統(tǒng)參數(shù)發(fā)送給Malice，其中C在接受挑戰(zhàn)的過程中，維護(hù)六張表：和這些表初始為空。其中和分別記錄Malice對(duì)隨機(jī)預(yù)言機(jī)和的詢問，而SL用于記錄C模擬簽密預(yù)言機(jī)，LU用于記錄C模擬解密預(yù)言機(jī)。詳情如下：

H1詢問：C首先從中選取一個(gè)隨機(jī)數(shù)這里假設(shè)Malice不做重復(fù)的詢問。

對(duì)于Malice的第i次詢問，如果，回答并設(shè)置，否則，從中隨機(jī)選取x，計(jì)算并將添加到L1中，回答

H2詢問：如果在表中，返回，否則從中隨機(jī)選取h2，將添加到中，返回

H3詢問：如果在表中，返回，否則從中隨機(jī)選取h3，將添加到中，返回

H4詢問：如果在表中，返回，否則從中隨機(jī)選取h4，將添加到中，返回

Keygen詢問：假設(shè)Malice在執(zhí)行Keygen詢問之前已經(jīng)執(zhí)行過詢問。如果，終止模擬；否則在表中查找對(duì)應(yīng)的條目，返回

Signcrypt詢問：假設(shè)Malice在對(duì)和執(zhí)行Signcrypt詢問前已經(jīng)執(zhí)行過詢問。在這里，我們分兩種情況考慮。

在表L1中查找到條目計(jì)算計(jì)算可以從上述的詢問獲得。返回

Unsigncrypt詢問（c，W）：假設(shè)Malice在對(duì)ID2執(zhí)行Unsigncrypt詢問前已經(jīng)執(zhí)行過詢問。在這里，我們分兩種情況考慮。

在經(jīng)過多項(xiàng)式有界次上述詢問后，Malice輸出兩個(gè)希望挑戰(zhàn)的身份和兩個(gè)消息如果終止這個(gè)模擬；否則隨機(jī)選取，令就是BDH問題的候選答案），計(jì)算，然后提交挑戰(zhàn)密文給Malice。

Malice經(jīng)過第二輪詢問，這些詢問同第一輪相同。在模擬結(jié)束時(shí)，Malice輸出一個(gè)d'作為對(duì)d的猜測(cè)。如果輸出作為BDH問題的答案；否則C沒有解決BDH問題。

下面求C成功的概率。如果Malice在第一階段對(duì)IDb執(zhí)行Keygen詢問，C將失敗。選擇身份的選法有在q1種身份中，至少有一個(gè)身份沒執(zhí)行Keygen詢問，因此，Malice不對(duì)IDb執(zhí)行Keygen詢問的概率大于此外，Malice選擇身份IDb進(jìn)行挑戰(zhàn)的概率為在第二階段，如果Malice對(duì)執(zhí)行H4詢問，C將失敗。同理，Malice不對(duì)執(zhí)行H4詢問的概率大于。因此，C解決BDH問題的優(yōu)勢(shì)至少為。在C的計(jì)算時(shí)間上，每次Signcrpt詢問最多需要1次雙線性對(duì)運(yùn)算，每次Unsigncrypt詢問最多需要4次雙線性對(duì)運(yùn)算。證畢。

不可偽造性：由于Paterson方案在適應(yīng)性選擇消息攻擊下能抗存在性偽造，所以我們的方案也同樣能抗存在性偽造。因?yàn)樾路桨附夂灻芎缶褪荘aterson方案。

公開驗(yàn)證性：解簽密后，提交（m，W，V）給第三方驗(yàn)證者，驗(yàn)證者檢驗(yàn)等式是否成立即可。此過程不需要接收者Bob的私鑰SB，因此是可公開驗(yàn)證的。

不可否認(rèn)性：既然我們的方案是不可偽造的，又是可公開驗(yàn)證的，如果Alice確實(shí)簽密過一個(gè)消息，她就不能夠否認(rèn)。

前向安全性：即使Alice的私鑰被意外泄露或偷走，第三方也不能計(jì)算會(huì)話密鑰。因此，新方案滿足前向安全性。

1.3 效率

從計(jì)算量和通信成本來評(píng)價(jià)新方案。表1給出了我們的新方案與幾個(gè)基于身份的簽密方案的性能比較。為了簡(jiǎn)便，我們用Ex，Mu，Pa分別表示中的指數(shù)運(yùn)算次數(shù)、中的標(biāo)量乘運(yùn)算次數(shù)和雙線性對(duì)運(yùn)算次數(shù)，x（+y）表示需要x次雙線性對(duì)運(yùn)算，y次雙線性對(duì)預(yù)計(jì)算。Chen和Malone-Lee在文獻(xiàn)中宣稱他們的方案在可證明安全方案中是效率最高的，只需3次對(duì)運(yùn)算，而我們方案僅需2次對(duì)運(yùn)算。

表1 幾個(gè)基于身份簽密方案的效率比較

2 對(duì)李發(fā)根方案的分析

2.1 方案描述

Setup設(shè)為由P生成的循環(huán)加群，階為q，為具有相同階q的循環(huán)乘法群，為一個(gè)雙線性映射。定義四個(gè)安全的Hash函數(shù)，和。PKG隨機(jī)選擇一個(gè)主密鑰，計(jì)算PKG公開系統(tǒng)參數(shù)保密主密鑰s。

Keygen給定一個(gè)用戶U的身份IDU，PKG計(jì)算該用戶的私鑰其中為該用戶的公鑰。在這里，記發(fā)送者Alice的身份為，公鑰為，私鑰為接收者Bob的身份為，公鑰為私鑰為

Signcrypt為了發(fā)送一個(gè)消息給Bob，Alice執(zhí)行以下步驟：

Unsigncrypt當(dāng)收到密文σ時(shí)，Bob計(jì)算恢復(fù)消息

Verify如果等式成立，Bob接受這個(gè)消息m，否則認(rèn)為σ不合法。

2.2 安全性分析

事實(shí)上，該方案不是IND-IBSC-CPA安全的，因而更不是IND-IBSC-CCIA安全的。設(shè)Malice是敵手，攻擊方法如下：

（1）挑戰(zhàn)者C輸入安全參數(shù)k，運(yùn)行Setup算法，并將系統(tǒng)參數(shù)params發(fā)送給敵手Malice。

（2）Malice選擇兩個(gè)相同長(zhǎng)度的明文和希望挑戰(zhàn)的兩個(gè)身份發(fā)送給C。C隨機(jī)選擇計(jì)算并將結(jié)果σ發(fā)送給Malice。

（3）Malice計(jì)算得到發(fā)送者的公鑰，選取明文m0（或m1）和收到挑戰(zhàn)密文，直接應(yīng)用驗(yàn)證算法驗(yàn)證等式是否成立。如果成立，則輸出作為對(duì)d的猜測(cè)；否則，輸出作為對(duì)d的猜測(cè)。

注意到驗(yàn)證算法中，除消息m外，其它的參數(shù)對(duì)于敵手Malice來說都是已知的（其中是系統(tǒng)公開參數(shù)，是攻擊者選取的發(fā)送者的公鑰，由系統(tǒng)公開的Hash函數(shù)直接計(jì)算得到，R和S是Malice收到的挑戰(zhàn)密文中的公開信息），因而，驗(yàn)證過程能夠有效進(jìn)行。由于簽密驗(yàn)證算法的有效性，敵手Malice將以壓倒性優(yōu)勢(shì)猜測(cè)到d的值。因此，該方案不是IND-IBSC-CPA安全的。

3 結(jié)束語(yǔ)

高安全高效率的簽密方案的設(shè)計(jì)一直是簽密技術(shù)研究的焦點(diǎn)。可公開驗(yàn)證性和不可偽造性蘊(yùn)含著不可否認(rèn)性，沒有可公開驗(yàn)證性的方案要解決不可否認(rèn)性通常是困難和低效的（例如，使用交互式零知識(shí)證明技術(shù)）。簽密又具有保密性，在敵手攻擊能力異樣強(qiáng)大的開放網(wǎng)絡(luò)環(huán)境中，基于身份的簽密方案應(yīng)具有IND-IBSC-CCIA安全，EUF-IBSC-ACMIA安全以及前向安全和其它一切安全屬性。本文基于Paterson的簽名方案設(shè)計(jì)出一個(gè)高效的簽密方案，并在隨機(jī)預(yù)言機(jī)模型下，證明方案是IND-IBSC-CCIA安全和EUF-IBSC-ACMIA安全的。

[1]Zheng Yuliang，Digital signcryption or how to achieve cost（signature & encryption <

[2]Yang Cuomin，S.Wong Duncan and Deng Xiaotie.Analysis and Improvement of a Sign-cryption Scheme with Key Privacy[A].Proceeding of PKC'04[C].LNCS 3650.Berlin: Springerverlag.2005.