格上基于身份的前向安全簽名方案

向新銀

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

格上基于身份的前向安全簽名方案

向新銀

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

在前向安全簽名方案中，即使當前的秘鑰泄露，也能保證先前生成的簽名具有不可偽造性。針對已有格上基于前向安全簽名方案簽名長度過長的不足，利用Lyubashevsky無陷門技術(shù)，提出一個高效的前向安全簽名方案。在隨機預(yù)言模型下，基于小整數(shù)解困難假設(shè)證明了其能抵抗適應(yīng)性選擇消息攻擊，無需陷門函數(shù)和高斯抽樣函數(shù)。性能分析結(jié)果表明，與現(xiàn)有方案相比，該方案具有前向安全的特性，計算效率更高。

基于身份簽名；前向安全；格；無陷門；小整數(shù)解問題；后量子密碼

1 概述

為了解決基于公鑰基礎(chǔ)設(shè)施（Public Key Infrastructure，PKI）密碼體制帶來的證書管理開銷過大的問題。1984年，Sham ir提出了基于身份的密碼學(xué)原語［1］，其思想是用戶的公鑰可由用戶的身份信息（郵件地址、身份證號碼等）生成，私鑰由可信任第三方密鑰生成器生成。2001年，Boneh和Franklin［2］構(gòu)造了一個實用的基于身份加密體制，因其具有良好的特性，受到了學(xué)者的廣泛關(guān)注，一些新的方案相繼被提出［3-4］，如基于身份的簽名、基于身份的加密等。但一般的基于身份的簽名方案安全性必須保證密鑰絕對安全，一旦密鑰泄露，之后生成的簽名將無效。在實際應(yīng)用場景中，一些移動設(shè)備和未設(shè)置保護的設(shè)備密鑰泄露經(jīng)常出現(xiàn)，廣泛使用這些設(shè)備易受攻擊者的侵入。因此，密鑰泄露是基于身份的簽名體制所面臨的最致命的威脅，如何遏制基于身份簽名方案的密鑰泄露的危害，對于構(gòu)建實用的公鑰密碼系統(tǒng)十分重要。

1997年，Anderson等人［5］提出前向安全的思想，給出了限制密鑰泄露的危害的方法。Bellare和M iner［6］給出了前向安全簽名方案安全模型的形式化定義，并提出了一個實用的前向安全簽名方案。后來，一些新的方案不斷出現(xiàn)［3-4，7］。但以上的研究大多是基于傳統(tǒng)數(shù)論困難問題構(gòu)造的，如基于因式分解、基于離散對數(shù)問題。一旦進入量子時代，一般基于數(shù)論的問題在量子環(huán)境下將不再安全，構(gòu)造量子環(huán)境下的基于身份的前向簽名方案成為一個新的方向。1997年，A jtai等人［8］提出了一個格基公鑰密碼方案，格具有良好的線性結(jié)構(gòu)，且格方案易于實現(xiàn)，并能夠抵制量子計算的攻擊，目前還沒有解格難題的有效方法［9］。

本文利用Lyubashevsky無陷門的格簽名方案［10］，構(gòu)造了一個格上基于身份的前向安全簽名方案，并在小整數(shù)解問題（SIS）的假設(shè)下，證明該方案的安全性。

2 預(yù)備知識

定義相關(guān)參數(shù)如下：PPT表示概率多項式時間算法，νT表示向量ν的轉(zhuǎn)置，νP表示向量ν的lP范數(shù)，χ→D表示χ從分布D中任意選取，χ→S表示χ從集合S中均勻隨機選取。

2.1 格

定義1 設(shè)B=（ν1，ν2，…，νm）∈Rm×m是m維空間的一組基，則格其中，ν1，ν2，…，νm是一組線性無關(guān)的向量。

定義3 令一個任意的正參數(shù)γ＞0，c∈Rm，實數(shù)γ＞0，定義Zm上的連續(xù)的正態(tài)分布為：?χ∈ Rm，其中，ρmγ，c（χ）=

引理1 對于任意的矩陣A∈Zn×mq，其中，m＞ 64+n log n/log（2d+1）隨機選取s←｛-d，…，0，…，d｝m，這里存在一個s′∈｛-d，…，0，…，d｝m使得As=As′的概率為1-2-100［10］。

引理2 對于任意的正整數(shù)m和γ＞0［10］，存在：

引理3 令V是Zm上的一個子集，且V的元素的范數(shù)不超過T，γ∈R存在，V→R是一個概率分布，這里存在一個常數(shù)M= O（1）使得滿足以下2種算法的分布的概率具有統(tǒng)計漸進性：

2.2 方案的形式化定義

一個前向安全簽名方案由以下5個多項式時間算法組成［3］。

（1）參數(shù)建立：輸入安全參數(shù)n，輸出公開參數(shù)mPK和密鑰msK。

（2）密鑰提取：輸入公開參數(shù)mPK，密鑰msK和一個用戶的身份ID=id t∈｛0，1｝*（這里包含用戶的身份id和密鑰更新時預(yù)定義的一個時間t），輸出初始密鑰Sid0。

（3）秘鑰更新：輸入當前時間i，一個用戶的身份ID和當前的密鑰Sidi，輸出下一個時間i+1的秘鑰Sidi+1。

（4）簽名生成：輸入當前時間i，一個用戶的身份ID，當前的密鑰Sidi和簽名的消息m，輸出此時間的簽名σi。

（5）簽名驗證：輸入當前時間i，一個用戶的身份ID，簽名的消息m和簽名σi，如果簽名有效，則輸出1；否則，輸入0。

2.3 方案的安全模型

一個基于身份前向安全簽名方案在適應(yīng)性選擇消息攻擊下是存在性不可偽造的，其安全定義由如下游戲來表示，分別由一個多項式時間的敵手A和一個算法B共同進行。

參數(shù)建立：B通過此算法生成公開參數(shù)mPK和秘密鑰msK，并將mPK發(fā)送給A，而自己保存msK。

詢問：A進行如下詢問：

（1）秘鑰提取詢問：B一旦收到A對身份id的秘密鑰的詢問，B生成id的初始秘鑰Sid0，并將Sid0發(fā)送給A。

（2）秘鑰更新詢問：B一旦收到A對（id，j）（1≤j≤t）的詢問，B返回j時刻的秘鑰Sidj。

（3）簽名詢問：B一旦收到A對（id，i，m）的詢問，B返回消息m的簽名σi。

偽造：A輸出一個身份id*，時間i*，消息m*和簽名σi*。如果id*沒有在秘鑰提取詢問時被發(fā)布和（id*，i*，m*）沒在簽名詢問中出現(xiàn)過，如果VerifymsK（id*，i*，m*，σi*）=1，A將贏得此次游戲。

3 基于身份的前向安全簽名方案

令素數(shù)q=Poly（n），m＞64+n log n/log3，常數(shù)M=O（1），ν∈Zm和K都為正整數(shù)，2個哈希函數(shù)和具體方案構(gòu)造如下：

秘鑰提取：輸入公開參數(shù)mPK，秘密鑰msK和一個用戶的身份（這里包含用戶的身份id和秘鑰更新時預(yù)定義的一個時間t），此算法執(zhí)行如下：

簽名驗證：輸入當前時間i，簽名的消息m和簽名σi：

如果以上2個等式成立，則接受此簽名；否則，拒絕。

4 安全性分析

定理 在隨機預(yù)言機模型下，如果SIS問題是困難的，基于身份前向安全簽名方案在適應(yīng)性選擇消息攻擊下是存在性不可偽造的。

H1詢問：對于任意的i=1，2，…，t，B維護一張H1詢問的列表（這里Qi表示id i的哈希值），列表初始值為空。A對進行詢問，如果在列表中將 Qi作為對H1詢問的響應(yīng)；否則B隨機選取一個Ri，將Ri作為對H1詢問的響應(yīng)，并將添加到L1中。

秘鑰更新詢問：若A對（id，i）進行秘鑰更新詢問，B返回A當前時刻i的私鑰作為響應(yīng)。即對于任意的時間i∈（0，t），假設(shè)A在上做H1詢問，那么對于在的H1詢問，B將在列表L1中查找一個匹配值計算其中，最后B將返回給A，并將添加到L4中。

簽名詢問：敵手A詢問對消息m的簽名，盡管B不知道簽名私鑰，但是也能模擬出有效的簽名。B首先瀏覽列表L1和L2，即對于任意的時間i∈（0，t），如果列表L1和L2存在相應(yīng)的哈希值，B計算zi=以概率輸出當前的時間i的簽名σi=（ci，zi）；否則隨機選取向量c′i和通過對H詢問得到ci，然后計算并將zi存儲到列表L3和L4中，最終輸出相應(yīng)的簽名σi=（ci，zi）。

偽造：敵手A最后結(jié)束上述詢問，并輸出當前時間i*∈（0，t）的身份id*，消息m*和簽名σi*，如果以下3種條件同時成立：（1）1≤i*＜j＜t；（2）id*在密鑰提取詢問階段沒有被詢問；（3）（id*，i*，m*）在簽名詢問階段沒有被詢問，且m*，σi*）=1。則攻擊成功。

當敵手A成功偽造了一個簽名（id*，i*，m*， σi*），由分叉引理［13］可知，A輸出這里和，即有

5 性能分析

現(xiàn)有的格簽名方案大多是基于陷門生成函數(shù)提出的，但本文的格上基于身份的簽名安全簽名方案無陷門的。下面主要通過公鑰大小、私鑰大小和簽名大小來分析新方案的性能，并將新方案與已有的方案進行性能對比。不失一般性，采用統(tǒng)一標準來分析。這里令m=O（n log n），q=O（n2）和σ=n·表1給出了本文方案與現(xiàn)有的方案的性能比較。

表1 方案性能比較

從表1分析可知，文獻［11］方案的公鑰、私鑰、簽名大小比新方案要大，效率較低。文獻［12］方案的私鑰大小、簽名大小比新方案要大，效率較低。因此，本文方案的效率具有一定的優(yōu)勢。

6 結(jié)束語

本文利用Lyubashevsky的無陷門技術(shù)，提出一個格上高效的基于身份的前向安全簽名方案，在隨機預(yù)言機模型下，基于SIS困難假設(shè)證明了本文方案對適應(yīng)性選擇消息攻擊滿足存在性不可偽造性，無需陷門生成函數(shù)和高斯抽樣函數(shù)，與現(xiàn)有的方案相比，該方案在公鑰大小、私鑰大小和簽名大小方面具有一定的優(yōu)勢。另外，如何設(shè)計標準模型下的格基無陷門前向安全簽名方案是下一步的研究方向。

［1］ Sham ir A.Identity-based Cryptosystems and Signature Schem es［C］//Proceedings of Advances in Cryptology-Crypto'84.Santa Barbara，USA：Springer-Verlag，1984：47-53.

［2］ Boneh D，F(xiàn)ranklin M.Identity Based Encryption from the W eil Pairing［C］//Proceedings of Advances in Cryptology-CRYPTO'01.Santa Barbara，USA：Springer-Verlag，2001：213-229.

［3］ Yu Jia，Kong Fanyu，Cheng Xiangguo，et al.One Forward-secure Signature Scheme Using Bilinear Maps and Its Applications［J］.Information Science，2014，279（1）：60-76.

［4］ Yu Jia，Kong Fanyu，Cheng Xiangguo，et al.Erratum to the Paper：Forward-secure Identity-based Public-key Encryption Without Random Oracles［J］.Fundamenta Informaticae，2012，114（1）：103.

［5］ Anderson R.Two Remarks on Public Key Cryptology［EB/OL］.（2011-11-12）.http：//www.cl.cam.ac. uk/techreports/UCAM-CL-TR-549.pdf.

［6］ Bellare M，Miner S.A Forward-secure Digital Signature Scheme［C］//Proceedings of the 19th Annual International Cryptology Conference.Santa Barbara，USA：Springer-Verlag，1999：431-448.

［7］ Liu Yali，Yin Xinchun，Qiu Liang.ID-based Forward Secure Signature Scheme from the Bilinear Pairings［C］//Proceedings of International Symposium on Electronic Commerce and Security.Guangzhou，China：［s.n.］，2008：179-183.

［8］ Ajtai M.Generating Hard Instances of Lattice Problem s［C］//Proceedings of the 28th Annual ACM Symposium on the Theory of Computing.Pennsylvania，USA：［s.n.］，1996：99-108.

［9］ 王小云，劉明潔.格密碼學(xué)研究［J］.密碼學(xué)學(xué)報，2014，1（1）：13-27.

［10］ Lyubashevsky V.Lattice Signatures Without Trapdoors［C］//Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cambridge，UK：［s.n.］，2012：738-755.

［11］ Rückert M.Strongly Unforgeable Signatures and Hierarchical Identity-based Signatures from Lattices Without Random Oracles［C］//Proceedings of the International Workshop on Post-quantum Cryptography Darmstadt.［S.1.］：Springer-Verlag，2010：215-222.

［12］ Zhang Xiaojun，Xu Chunxiang，Jin Chunhua，et al. Efficient Forward Secure Identity-based Shorter Signature from Lattice［J］.Computers&Electrical Engineering，2014，40（6）：1963-1971.

［13］ Bellare M，Neven G.Multi-signatures in the Plain Public-key Model and a General Forking Lemm a［C］// Proceedings of ACM Conference on Computer and Communications Security.A lexandria，USA：ACM Press，2006：390-399.

編輯 索書志

Identity-based Forward Secure Signature Scheme from Lattices

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

In a forward secure signature scheme，the scheme can guarantee the unforgeability of the foregoing signatures even if the current signing secret key is revealed.Aim ing at the efficiency weakness that exists in the previous forward secure signature schemes from lattices，using the technique（Without trapdoors）of Lyubashevsky，an efficient identity based forward secure signature scheme from lattices is proposed.In the random oracle model，the scheme is existentially unforgeable against adaptive chosen message attacks under the Small Integer Solution（SIS）problem.Performance analysis results show that，compared with other existing schemes，the scheme has the characters of forward secure and can provide better efficiency.

identity-based signature；forward security；lattice；Without trapdoors；Small Integer Solution（SIS）problem；post-quantum cryptography

向新銀.格上基于身份的前向安全簽名方案［J］.計算機工程，2015，41（9）：155-158.

英文引用格式：Xiang Xinyin.Identity-based Forward Secure Signature Scheme from Lattices［J］.Computer Engineering，2015，41（9）：155-158.

1000-3428（2015）09-0155-04

A

TP309

10.3969/j.issn.1000-3428.2015.09.028

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

向新銀（1979-），男，講師、碩士，主研方向：格公鑰，密碼技術(shù)。

2015-02-05

2015-03-22 E-m ail：xiangxinyin@163.com