向新銀

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

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

向新銀

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

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

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

1 概述

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

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

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

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

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

2.1 格

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

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

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

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

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

2.2 方案的形式化定義

一個(gè)前向安全簽名方案由以下5個(gè)多項(xiàng)式時(shí)間算法組成［3］。

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

（2）密鑰提?。狠斎牍_參數(shù)mPK，密鑰msK和一個(gè)用戶的身份ID=id t∈｛0，1｝*（這里包含用戶的身份id和密鑰更新時(shí)預(yù)定義的一個(gè)時(shí)間t），輸出初始密鑰Sid0。

（3）秘鑰更新：輸入當(dāng)前時(shí)間i，一個(gè)用戶的身份ID和當(dāng)前的密鑰Sidi，輸出下一個(gè)時(shí)間i+1的秘鑰Sidi+1。

（4）簽名生成：輸入當(dāng)前時(shí)間i，一個(gè)用戶的身份ID，當(dāng)前的密鑰Sidi和簽名的消息m，輸出此時(shí)間的簽名σi。

（5）簽名驗(yàn)證：輸入當(dāng)前時(shí)間i，一個(gè)用戶的身份ID，簽名的消息m和簽名σi，如果簽名有效，則輸出1；否則，輸入0。

2.3 方案的安全模型

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

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

詢問：A進(jìn)行如下詢問：

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

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

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

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

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

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

秘鑰提?。狠斎牍_參數(shù)mPK，秘密鑰msK和一個(gè)用戶的身份（這里包含用戶的身份id和秘鑰更新時(shí)預(yù)定義的一個(gè)時(shí)間t），此算法執(zhí)行如下：

簽名驗(yàn)證：輸入當(dāng)前時(shí)間i，簽名的消息m和簽名σi：

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

4 安全性分析

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

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

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

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

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

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

5 性能分析

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

表1 方案性能比較

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

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

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

［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é)報(bào)，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］.計(jì)算機(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é)基金資助項(xiàng)目（2012JM 8018，2014JM 2-6099）；國(guó)家統(tǒng)計(jì)科學(xué)研究計(jì)劃基金資助項(xiàng)目（2013LY052）；陜西省教育廳科學(xué)計(jì)劃基金資助項(xiàng)目（2010JK553，2013JK 1193）；西安財(cái)經(jīng)學(xué)院基金資助項(xiàng)目（13XCK01）。

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

2015-02-05

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