格上適應性安全可撤銷的基于身份簽名方案

向新銀

（西安財經學院信息學院，西安 710100）

格上適應性安全可撤銷的基于身份簽名方案

向新銀

（西安財經學院信息學院，西安 710100）

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

適應性安全；基于身份簽名；格；小整數解；后量子密碼

1 概述

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

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

碼方案效率較高，但是在隨機預言模型中，一些學者也指出某些方案在哈希函數實例化后并不安全。因此，考慮無隨機預言的標準模型下構造可撤銷的基于身份的簽名方案具有十分重要的意義。

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

2 預備知識

定義相關參數：令q表示一個素數，PPT表示概率多項式時間。

其中，ν1，ν2，…，νm是一組線性無關的向量。

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

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

3.1 形式化定義

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

（1）參數建立：輸入一個安全參數 λ，輸出系統公開參數PP。

（2）密鑰提取：輸入一個用戶的身份標識 id，輸出用戶的私鑰skid。

（3）密鑰更新：輸入一個用戶的身份標識 id和時間周期t，輸出用戶的私鑰skt。

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

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

3.2 安全模型

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

（1）參數建立：輸入安全參數 λ，B運行此算法生成系統參數和密鑰，并公開系統參數。

（2）詢問：A適應性執行如下詢問：

1）密鑰提取詢問：輸入用戶的身份標識id，運行密鑰提取算法生成私鑰并返回給A。

2）密鑰更新詢問：輸入用戶的身份標識id和時間周期t，運行密鑰更新算法生成更新私鑰并返回給A。

3）簽名詢問：輸入系統參數，用戶的身份標識id和時間周期 t，簽名算法生成一個簽名 σ，并發送給A。

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

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

（1）參數建立：輸入一個安全參數 λ，此算法執行如下：

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

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

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

（2）密鑰提取：輸入公開參數PP，主密鑰 msk，一個身份標識 id=（b1，b2，…，bl）∈｛-1，1｝l，此算法執行如下：

2）計算Tid←EχtBasis（A0，Aid，TA0）。

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

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

2）計算Tt←EχtBasis（A0，Fid，t，Tid）。

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

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

1）計算e←SampleLeft（A0，Fid，t，Tt，u，δ）。

2）輸出簽名σ=e。

（5）驗證：輸入消息 m和簽名 σ，驗證者進行如下算法：

2）Fid，te=u。

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

5 方案的安全性分析

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

其中，概率為H在H：中的隨機選擇。

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

其中和 h=（h1，

定理 在SIS困難問題下，新方案滿足標準模型下的適應性選擇消息攻擊的強不可偽造性。

證明：假設存在一個多項式時間的敵手A，構造一個不可區分的算法B解SIS問題，即輸入任意一個矩陣A′，找到一個非零向量e≠0，使得A′e=0。具體游戲在A和B之間共同進行。

參數建立：B為應對SIS挑戰，執行如下算法：

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

（5）選取一個隨機向量u∈Znq。

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

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

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

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

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

3）對于t=（t1，t2，…，tl）∈｛-1，1｝l，計算Tt←EχtBasis（A0，Fid，t，Tid）。

并返回私鑰skt=Tt給A。

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

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

2）如果hid=0或者ht=0，這里TB或者TE的作用消失，B重新構造一個簽名e，并發送給敵手A。

偽造：A在時間周期t*內對身份標識id*和消息生成了一個偽造簽名 e*。假設或者ht*=0時產生的概率為1/2λ，對于任意的 hid*≠0和ht*≠0，即有：Fid*，t*e*=u，Fid*，t*e=u，則Fid*，t*（e*-e）=u-u。

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

6 結束語

本文基于文獻［12］的技術，提出一個格上適應性安全的可撤銷的基于身份的簽名方案，并證明了該方案在標準模型下，基于SIS困難問題滿足適應性選擇消息攻擊的強不可偽造性（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，Franklin 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］ 張彥華，胡予濮，江明明，等.格上可撤銷的基于身份的適應性安全的加密方案［J］.電子與信息學報，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，French：［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

向新銀.格上適應性安全可撤銷的基于身份簽名方案［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

國家統計科學研究計劃基金資助項目（2013LY052）；陜西省自然科學基金資助項目（2012JM 8018，2014JM 2-6099）；陜西省教育廳科學計劃基金資助項目（2010JK553，2013JK1193）；西安財經學院基金資助項目（13XCK 01）。

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

2015-04-17

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