向新銀

（西安財(cái)經(jīng)學(xué)院信息學(xué)院，西安 710100）

格上適應(yīng)性安全可撤銷的基于身份簽名方案

向新銀

（西安財(cái)經(jīng)學(xué)院信息學(xué)院，西安 710100）

傳統(tǒng)基于身份的簽名方案的安全性依賴于密鑰的安全，一旦密鑰泄露，則需重新發(fā)布先前所有的簽名。為撤銷簽名方案中私鑰泄露或惡意的用戶，提出一個(gè)可撤銷的基于身份簽名方案，并給出解決密鑰泄漏的有效方法，在小整數(shù)解困難問題下，能抵抗適應(yīng)性選擇消息攻擊的強(qiáng)不可偽造性。安全性分析結(jié)果表明，該方案不僅滿足原有可撤銷的基于身份的簽名方案的可證明安全性，而且還能抵抗量子攻擊。

適應(yīng)性安全；基于身份簽名；格；小整數(shù)解；后量子密碼

1 概述

為簡化公鑰的管理，文獻(xiàn)［1］提出了基于身份的密碼學(xué)原語，其思想是用戶的公鑰可由用戶的身份信息（郵件地址、身份證號碼等）生成，私鑰由可信任第三方密鑰生成器生成。2001年，Boneh和Franklin［2］構(gòu)造了第一個(gè)實(shí)用的基于身份加密體制，并成功地將雙線性對運(yùn)用到公鑰密碼體制中。2002年，Paterson［3］利用雙線性對，構(gòu)造了一個(gè)新的基于身份的簽名方案，但該方案效率較低。文獻(xiàn)［4］基于CDH的困難假設(shè)提出改進(jìn)方案，該方案的計(jì)算效率和簽名大小都有較大的提高。2009年，Tseng等人［5］在隨機(jī)預(yù)言模型下提出了一個(gè)可證明安全的基于身份的簽名方案，但是他們的方案并不支持強(qiáng)不可偽造性。

隨著公鑰密碼體制的發(fā)展，特別在一些安全性較差的環(huán)境中，密鑰容易泄露。如何遏制密鑰泄露的發(fā)生，可以通過撤銷密鑰來解決。2008年，Boldyreva等人［6］應(yīng)用二叉樹結(jié)構(gòu)構(gòu)造一個(gè)可撤銷的基于身份的加密方案，該方案盡管減少了密鑰更新的大小，但是需要通過安全信道周期地傳輸新的用戶私鑰，導(dǎo)致加密和解密過程的計(jì)算開銷過大。文獻(xiàn)［7］提出了一個(gè)實(shí)用的可撤銷方案。文獻(xiàn)［8］在隨機(jī)預(yù)言模型下提出了一個(gè)可撤銷的基于身份的簽名方案。然而，以上方案大多是在隨機(jī)預(yù)言模型下證明其安全性。雖然在隨機(jī)預(yù)言模型下構(gòu)造的密

碼方案效率較高，但是在隨機(jī)預(yù)言模型中，一些學(xué)者也指出某些方案在哈希函數(shù)實(shí)例化后并不安全。因此，考慮無隨機(jī)預(yù)言的標(biāo)準(zhǔn)模型下構(gòu)造可撤銷的基于身份的簽名方案具有十分重要的意義。

從文獻(xiàn)［9］構(gòu)造了一類隨機(jī)格后，格公鑰的研究受到了廣泛的關(guān)注。文獻(xiàn)［10］構(gòu)造了格上可撤銷的基于身份的加密方案，但是該方案僅支持選擇性安全。隨后，文獻(xiàn)［11］基于文獻(xiàn)［10］方案提出一個(gè)格上可撤銷的基于身份適應(yīng)性安全的加密方案。目前還沒有格上可撤銷的基于身份的簽名方案，為此，本文利用文獻(xiàn)［12］的技術(shù)，構(gòu)造了一個(gè)格上適應(yīng)性安全的可撤銷的基于身份的簽名方案。

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

定義相關(guān)參數(shù)：令q表示一個(gè)素?cái)?shù)，PPT表示概率多項(xiàng)式時(shí)間。

其中，ν1，ν2，…，νm是一組線性無關(guān)的向量。

定義2（離散高斯分布） 令一個(gè)任意的正參數(shù)ρ＞0，c∈Rm，實(shí)數(shù)σ＜0，定義格Λ上的離散高斯分布為其

3 方案形式化定義和安全模型

3.1 形式化定義

一個(gè)可撤銷基于身份的簽名方案由以下5個(gè)算法組成［3］：

（1）參數(shù)建立：輸入一個(gè)安全參數(shù) λ，輸出系統(tǒng)公開參數(shù)PP。

（2）密鑰提?。狠斎胍粋€(gè)用戶的身份標(biāo)識(shí) id，輸出用戶的私鑰skid。

（3）密鑰更新：輸入一個(gè)用戶的身份標(biāo)識(shí) id和時(shí)間周期t，輸出用戶的私鑰skt。

（4）簽名：輸入公開參數(shù)PP，時(shí)間周期t的公鑰Pkt和私鑰skt，輸出簽名σ。

（5）驗(yàn)證：輸入用戶的身份標(biāo)識(shí) id，時(shí)間周期 t和消息 m的簽名 σ，如果簽名 σ是否有效，輸出1；否則，輸出0。

3.2 安全模型

定義4（強(qiáng)不可偽造性） 一個(gè)可撤銷的基于身份的簽名方案滿足選擇消息攻擊下強(qiáng)不可偽造性，即如果沒有敵手A在sUF-CMA游戲中以不可忽略的優(yōu)勢取勝。這里的sUF-CMA游戲是在一個(gè)算法B和敵手A之間進(jìn)行。

（1）參數(shù)建立：輸入安全參數(shù) λ，B運(yùn)行此算法生成系統(tǒng)參數(shù)和密鑰，并公開系統(tǒng)參數(shù)。

（2）詢問：A適應(yīng)性執(zhí)行如下詢問：

1）密鑰提取詢問：輸入用戶的身份標(biāo)識(shí)id，運(yùn)行密鑰提取算法生成私鑰并返回給A。

2）密鑰更新詢問：輸入用戶的身份標(biāo)識(shí)id和時(shí)間周期t，運(yùn)行密鑰更新算法生成更新私鑰并返回給A。

3）簽名詢問：輸入系統(tǒng)參數(shù)，用戶的身份標(biāo)識(shí)id和時(shí)間周期 t，簽名算法生成一個(gè)簽名 σ，并發(fā)送給A。

（3）偽造：A輸出用戶身份標(biāo)識(shí) id*，消息 m*，時(shí)間周期t*和簽名σ*。如果（id*，m*，t*）在詢問階段沒有被詢問過且驗(yàn)證有效，則A贏得此游戲。

4 可撤銷的基于身份的簽名方案

（1）參數(shù)建立：輸入一個(gè)安全參數(shù) λ，此算法執(zhí)行如下：

1）運(yùn)行陷門生成算法TrapGen（q，n，m）生成一個(gè)矩陣和上的一個(gè)短基 TA0∈，使得

2）選取2 l+2個(gè)n×m的矩陣A1，A2，…，Al，B，

4）輸出公開參數(shù) PP=（A0，A1，…，Al，B，C，D1，…，Dl，u），保存主密鑰msk=TA0。

（2）密鑰提?。狠斎牍_參數(shù)PP，主密鑰 msk，一個(gè)身份標(biāo)識(shí) id=（b1，b2，…，bl）∈｛-1，1｝l，此算法執(zhí)行如下：

2）計(jì)算Tid←EχtBasis（A0，Aid，TA0）。

3）輸出公鑰Pkid=Aid，私鑰skid=Tid。

（3）密鑰更新：輸入公開參數(shù)PP，用戶私鑰skid，一個(gè)用戶的身份標(biāo)識(shí)id=（b1，b2，…，bl）∈｛-1，1｝l和任意的時(shí)間周期t=（t1，t2，…，tl）∈｛-1，1｝l，此算法執(zhí)行如下：

2）計(jì)算Tt←EχtBasis（A0，F(xiàn)id，t，Tid）。

3）輸出公鑰Pkt=Fid，t私鑰skt=Tt。

（4）簽名：輸入公開參數(shù)PP，一個(gè)任意的時(shí)間周期t=（t1，t1，…，tl）∈｛-1，1｝l，用戶的更新密鑰對（Pkt，skt）和消息m∈｛0，1｝*，此算法執(zhí)行如下：

1）計(jì)算e←SampleLeft（A0，F(xiàn)id，t，Tt，u，δ）。

2）輸出簽名σ=e。

（5）驗(yàn)證：輸入消息 m和簽名 σ，驗(yàn)證者進(jìn)行如下算法：

2）Fid，te=u。

如果以上條件同時(shí)成立，則簽名有效，輸出1；否則，輸出0。

5 方案的安全性分析

定義4 假設(shè)H：=｛H：X→Y｝是一個(gè)從X映射到Y(jié)的哈希函數(shù)，對于任意的Q+1個(gè)集合χ—=（χ0，χ1，…，χQ）∈XQ+1，定義 χ—非退化的概率為：

其中，概率為H在H：中的隨機(jī)選擇。

H抗退化碰撞的定義如下：給定任意的χ—=（χ0，且 χ0≠（χ1，χ2，…，χQ），存在

其中和 h=（h1，

定理 在SIS困難問題下，新方案滿足標(biāo)準(zhǔn)模型下的適應(yīng)性選擇消息攻擊的強(qiáng)不可偽造性。

證明：假設(shè)存在一個(gè)多項(xiàng)式時(shí)間的敵手A，構(gòu)造一個(gè)不可區(qū)分的算法B解SIS問題，即輸入任意一個(gè)矩陣A′，找到一個(gè)非零向量e≠0，使得A′e=0。具體游戲在A和B之間共同進(jìn)行。

參數(shù)建立：B為應(yīng)對SIS挑戰(zhàn)，執(zhí)行如下算法：

（1）任意抽取 2個(gè)矩陣和其相應(yīng)的陷門（B，TB）←TrapGen（q，n，m），（E，TE）←TrapGen（q，n，m）。

（5）選取一個(gè)隨機(jī)向量u∈Znq。

（6）輸出公開參數(shù) PP=（A0，｛Aid，i｝i=1，2，…，l，｛At，i｝i=1，2，…，l，B，E，u），保存主密鑰msk=（TB，TE），并將PP發(fā)送給敵手A。

詢問：B在消息m上應(yīng)對敵手A多項(xiàng)式次用戶密鑰生成，密鑰更新和密鑰撤銷詢問的應(yīng)答。首先輸入一個(gè)身份標(biāo)識(shí) id=（b1，b2，…，bl）∈｛-1，1｝l，過程如下：

（1）密鑰提取詢問：為了響應(yīng)A對id=（b1，b2，…，bl）∈｛-1，1｝l密鑰提取詢問，B執(zhí)行以下操作：

如果hid≠0，這時(shí)A0‖A0Rid+hidB。B執(zhí)行如下算法：Tid←EχtBasis（A0，Kid，TA0），并返回skid=Tid給A。

（2）密鑰更新詢問：為了響應(yīng)A對t=（t1，t2，…，的密鑰更新詢問，B執(zhí)行如下算法：

3）對于t=（t1，t2，…，tl）∈｛-1，1｝l，計(jì)算Tt←EχtBasis（A0，F(xiàn)id，t，Tid）。

并返回私鑰skt=Tt給A。

（3）簽名詢問：為了響應(yīng) A對消息 m∈｛0，1｝*上的簽名詢問，B執(zhí)行如下算法：

1）如果hid≠0，即有：e←Sam pleRigh t（Fid，t，Tt，u），輸出簽名e。

2）如果hid=0或者h(yuǎn)t=0，這里TB或者TE的作用消失，B重新構(gòu)造一個(gè)簽名e，并發(fā)送給敵手A。

偽造：A在時(shí)間周期t*內(nèi)對身份標(biāo)識(shí)id*和消息生成了一個(gè)偽造簽名 e*。假設(shè)或者h(yuǎn)t*=0時(shí)產(chǎn)生的概率為1/2λ，對于任意的 hid*≠0和ht*≠0，即有：Fid*，t*e*=u，F(xiàn)id*，t*e=u，則Fid*，t*（e*-e）=u-u。

僅考慮如下情況，如果hid*=0和ht*=0，則：

6 結(jié)束語

本文基于文獻(xiàn)［12］的技術(shù)，提出一個(gè)格上適應(yīng)性安全的可撤銷的基于身份的簽名方案，并證明了該方案在標(biāo)準(zhǔn)模型下，基于SIS困難問題滿足適應(yīng)性選擇消息攻擊的強(qiáng)不可偽造性（sUF-CMA）。該方案提供了可撤銷性和更好的安全性，可以推廣到選擇性安全的可撤銷的基于身份的簽名方案。

［1］ Shamir A.Identity-based Cryptosystems and Signature Schemes［C］//Proceedings of Crypto’84，Santa Barbara，USA：IEEE Press，1984：47-53.

［2］ Boneh D，F(xiàn)ranklin M.Identity-based Encryption from the Weil Pairing［C］//Proceedins of Crypto’01.Santa Barbara，USA：IEEE Press，2001：213-229.

［3］ Paterson K，Schuldt J.Efficient Identity-based Signatures Secure in the Standard Model［C］//Proceedings of the 11 th Australasian Conference on Information Security and Privacy.Melbourne，Australia：［s.n.］，2002：207-222.

［4］ Cha JC，Cheon J H.An Identity-based Signature from Gap Diffie-Hellman Groups［C］//Proceedings of the 6 th International Workshop on Practice and Theory in Public Key Cryptography.Miami，USA：IEEE Press，2003：18-30.

［5］ Tseng Y M，Wu TY，Wu JD.A Pairing-based User Authentication Scheme for Wireless Clients with Smart Cards［J］.Informatica，2008，19（2）：285-302.

［6］ Boldyreva A，Goyal V，Kumar V.Identity-based Encryption with Efficient Revocation［C］//Proceedings of the 15th ACM Conference on Computer and Communications Security.New York，USA：ACM Press，2008：417-426.

［7］ Tsai T T，Tseng Y M，W u T Y.Provably Secure Revocable ID-based Signature in the Standard Model［J］.Security and Communication Networks，2013，10（6）：1250-1260.

［8］ Sun Yinxia，Zhang Futai，Shen Linmin，et al.Revocable Identity-based Signature Without Pairing［C］//Proceedings of the 5th International Conference on Intelligent Networking and Collaborative System s.X i’an，China：［s.n.］，2013：363-365.

［9］ Ajtai M.Generating Hard Instances of Lattice Problems［C］//Proceedings of the 28th Annual ACM Symposium on Theory of Computing.New York，USA：ACM Press，1996：99-108.

［10］ Chen Jie，Lim L M，Ling Sen，et al.Revocable Identitybased Encryption from Lattices［C］//Proceedings of the 17th Australasian Conference on Information Security and Privacy.Wollongong，Australia：［s.n.］，2012：390-403.

［11］ 張彥華，胡予濮，江明明，等.格上可撤銷的基于身份的適應(yīng)性安全的加密方案［J］.電子與信息學(xué)報(bào)，2015，37（2）：423-428.

［12］ Agrawal S，Boneh D，Boyen X.Efficient Lattice（H）IBE in the Standard Model［C］//Proceedings of Eurocrypt’10.Riviera，F(xiàn)rench：［s.n.］，2010：553-572.

編輯 索書志

Adaptive Secure Revocable Identity-based Signature Scheme over Lattices

XIANG Xinyin
（School of Information，Xi’an University of Finance and Economics，Xi’an 710100，China）

The security of traditional identity-based signatures wholly depends on the security of secret keys.Exposure of secret keys requires reissuing all previously assigned signatures.Based on this，to revoke private key leaks or malicious users in the signature scheme，an adaptive secure revocable identity-based signature over lattices is proposed，which provides an efficient revocation mechanism to revoke misbehaving or compromised users from the system s.The scheme is proved to be strongly Unforgeable against adaptive Chosen-message Attacks（sUF-CMA）under Small Integer Solution（SIS）assumption.Security analysis results show that the proposed scheme not only can meet the security of revocable identity-based signature，but also can resist the quantum attack.

adaptive secure；identity-based signature；lattice；Small Integer Solution（SIS）；post-quantum cipher

向新銀.格上適應(yīng)性安全可撤銷的基于身份簽名方案［J］.計(jì)算機(jī)工程，2015，41（10）：126-129.

英文引用格式：Xiang Xinyin.Adaptive Secure Revocable Identity-based Signature over Lattices［J］.Computer Engineering，2015，41（10）：126-129.

1000-3428（2015）10-0126-04

A

TP309

10.3969/j.issn.1000-3428.2015.10.024

國家統(tǒng)計(jì)科學(xué)研究計(jì)劃基金資助項(xiàng)目（2013LY052）；陜西省自然科學(xué)基金資助項(xiàng)目（2012JM 8018，2014JM 2-6099）；陜西省教育廳科學(xué)計(jì)劃基金資助項(xiàng)目（2010JK553，2013JK1193）；西安財(cái)經(jīng)學(xué)院基金資助項(xiàng)目（13XCK 01）。

向新銀（1979-），男，講師、博士，主研方向：格公鑰。

2015-04-17

2015-05-19E-mail：xiangxinyin@hotmail.com