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

向新银

（西安财经学院信息学院，西安710100）

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

向新银

（西安财经学院信息学院，西安710100）

在前向安全签名方案中，即使当前的秘钥泄露，也能保证先前生成的签名具有不可伪造性。针对已有格上基于前向安全签名方案签名长度过长的不足，利用Lyubashevsky无陷门技术，提出一个高效的前向安全签名方案。在随机预言模型下，基于小整数解困难假设证明了其能抵抗适应性选择消息攻击，无需陷门函数和高斯抽样函数。性能分析结果表明，与现有方案相比，该方案具有前向安全的特性，计算效率更高。

基于身份签名；前向安全；格；无陷门；小整数解问题；后量子密码

1 概述

为了解决基于公钥基础设施（Public Key Infrastructure，PKI）密码体制带来的证书管理开销过大的问题。1984年，Sham ir提出了基于身份的密码学原语［1］，其思想是用户的公钥可由用户的身份信息（邮件地址、身份证号码等）生成，私钥由可信任第三方密钥生成器生成。2001年，Boneh和Franklin［2］构造了一个实用的基于身份加密体制，因其具有良好的特性，受到了学者的广泛关注，一些新的方案相继被提出［3-4］，如基于身份的签名、基于身份的加密等。但一般的基于身份的签名方案安全性必须保证密钥绝对安全，一旦密钥泄露，之后生成的签名将无效。在实际应用场景中，一些移动设备和未设置保护的设备密钥泄露经常出现，广泛使用这些设备易受攻击者的侵入。因此，密钥泄露是基于身份的签名体制所面临的最致命的威胁，如何遏制基于身份签名方案的密钥泄露的危害，对于构建实用的公钥密码系统十分重要。

1997年，Anderson等人［5］提出前向安全的思想，给出了限制密钥泄露的危害的方法。Bellare和M iner［6］给出了前向安全签名方案安全模型的形式化定义，并提出了一个实用的前向安全签名方案。后来，一些新的方案不断出现［3-4，7］。但以上的研究大多是基于传统数论困难问题构造的，如基于因式分解、基于离散对数问题。一旦进入量子时代，一般基于数论的问题在量子环境下将不再安全，构造量子环境下的基于身份的前向签名方案成为一个新的方向。1997年，A jtai等人［8］提出了一个格基公钥密码方案，格具有良好的线性结构，且格方案易于实现，并能够抵制量子计算的攻击，目前还没有解格难题的有效方法［9］。

本文利用Lyubashevsky无陷门的格签名方案［10］，构造了一个格上基于身份的前向安全签名方案，并在小整数解问题（SIS）的假设下，证明该方案的安全性。

2 预备知识

定义相关参数如下：PPT表示概率多项式时间算法，νT表示向量ν的转置，νP表示向量ν的lP范数，χ→D表示χ从分布D中任意选取，χ→S表示χ从集合S中均匀随机选取。

2.1 格

定义1 设B=（ν1，ν2，…，νm）∈Rm×m是m维空间的一组基，则格其中，ν1，ν2，…，νm是一组线性无关的向量。

定义3 令一个任意的正参数γ＞0，c∈Rm，实数γ＞0，定义Zm上的连续的正态分布为：∀χ∈ 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 对于任意的正整数m和γ＞0［10］，存在：

引理3 令V是Zm上的一个子集，且V的元素的范数不超过T，γ∈R存在，V→R是一个概率分布，这里存在一个常数M= O（1）使得满足以下2种算法的分布的概率具有统计渐进性：

2.2 方案的形式化定义

一个前向安全签名方案由以下5个多项式时间算法组成［3］。

（1）参数建立：输入安全参数n，输出公开参数mPK和密钥msK。

（2）密钥提取：输入公开参数mPK，密钥msK和一个用户的身份ID=id t∈｛0，1｝*（这里包含用户的身份id和密钥更新时预定义的一个时间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 方案的安全模型

一个基于身份前向安全签名方案在适应性选择消息攻击下是存在性不可伪造的，其安全定义由如下游戏来表示，分别由一个多项式时间的敌手A和一个算法B共同进行。

参数建立：B通过此算法生成公开参数mPK和秘密钥msK，并将mPK发送给A，而自己保存msK。

询问：A进行如下询问：

（1）秘钥提取询问：B一旦收到A对身份id的秘密钥的询问，B生成id的初始秘钥Sid0，并将Sid0发送给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*没有在秘钥提取询问时被发布和（id*，i*，m*）没在签名询问中出现过，如果VerifymsK（id*，i*，m*，σi*）=1，A将赢得此次游戏。

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

令素数q=Poly（n），m＞64+n log n/log3，常数M=O（1），ν∈Zm和K都为正整数，2个哈希函数和具体方案构造如下：

秘钥提取：输入公开参数mPK，秘密钥msK和一个用户的身份（这里包含用户的身份id和秘钥更新时预定义的一个时间t），此算法执行如下：

签名验证：输入当前时间i，签名的消息m和签名σi：

如果以上2个等式成立，则接受此签名；否则，拒绝。

4 安全性分析

定理 在随机预言机模型下，如果SIS问题是困难的，基于身份前向安全签名方案在适应性选择消息攻击下是存在性不可伪造的。

H1询问：对于任意的i=1，2，…，t，B维护一张H1询问的列表（这里Qi表示id i的哈希值），列表初始值为空。A对进行询问，如果在列表中将 Qi作为对H1询问的响应；否则B随机选取一个Ri，将Ri作为对H1询问的响应，并将添加到L1中。

秘钥更新询问：若A对（id，i）进行秘钥更新询问，B返回A当前时刻i的私钥作为响应。即对于任意的时间i∈（0，t），假设A在上做H1询问，那么对于在的H1询问，B将在列表L1中查找一个匹配值计算其中，最后B将返回给A，并将添加到L4中。

签名询问：敌手A询问对消息m的签名，尽管B不知道签名私钥，但是也能模拟出有效的签名。B首先浏览列表L1和L2，即对于任意的时间i∈（0，t），如果列表L1和L2存在相应的哈希值，B计算zi=以概率输出当前的时间i的签名σi=（ci，zi）；否则随机选取向量c′i和通过对H询问得到ci，然后计算并将zi存储到列表L3和L4中，最终输出相应的签名σi=（ci，zi）。

伪造：敌手A最后结束上述询问，并输出当前时间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 性能分析

现有的格签名方案大多是基于陷门生成函数提出的，但本文的格上基于身份的签名安全签名方案无陷门的。下面主要通过公钥大小、私钥大小和签名大小来分析新方案的性能，并将新方案与已有的方案进行性能对比。不失一般性，采用统一标准来分析。这里令m=O（n log n），q=O（n2）和σ=n·表1给出了本文方案与现有的方案的性能比较。

表1 方案性能比较

从表1分析可知，文献［11］方案的公钥、私钥、签名大小比新方案要大，效率较低。文献［12］方案的私钥大小、签名大小比新方案要大，效率较低。因此，本文方案的效率具有一定的优势。

6 结束语

本文利用Lyubashevsky的无陷门技术，提出一个格上高效的基于身份的前向安全签名方案，在随机预言机模型下，基于SIS困难假设证明了本文方案对适应性选择消息攻击满足存在性不可伪造性，无需陷门生成函数和高斯抽样函数，与现有的方案相比，该方案在公钥大小、私钥大小和签名大小方面具有一定的优势。另外，如何设计标准模型下的格基无陷门前向安全签名方案是下一步的研究方向。

［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，Franklin 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］ 王小云，刘明洁.格密码学研究［J］.密码学学报，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

陕西省自然科学基金资助项目（2012JM 8018，2014JM 2-6099）；国家统计科学研究计划基金资助项目（2013LY052）；陕西省教育厅科学计划基金资助项目（2010JK553，2013JK 1193）；西安财经学院基金资助项目（13XCK01）。

向新银（1979-），男，讲师、硕士，主研方向：格公钥，密码技术。

2015-02-05

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