一种格上基于身份的代理签名方案

王黎

摘 要 本文利用原像抽样技术和固定维数的格基委托技术，在Boyen签名方案的基础上，构造了一个格上基于身份的代理签名方案。

关键词 代理签名 格 匿名性

中图分类号：TP391 文献标识码：A

0引言

基于身份的代理重加密是指代理把发送给一个身份的密文转化为给另一个身份的密文，可将身份加密与代理加密的优点集于一身，应用范围更广。随着信息安全领域对于安全性的要求越来越高，这种不同加密体制的交叉融合具有非常重要的研究意义和广泛的应用前景。

1基础知识

格（Lattice）是一类定义在有限域上的、离散的几何结构，是线性空间中n维向量构成的一个子集。其定义如下：

定义1：在n维向量空间中m个线性无关的向量（b1，b2，…，bm）所生成的向量集合：

L（b1，b2，…，bn）=

称为格。（b1，b2，…，bn）称为格的一组基。

格中向量x的长度用欧几里德范数||x||表示，矩阵X的长度定义为||X||=max||x||。向量x到格的距离定义为：dist（（AT），x）=min||（ATsx）modq||。

定义2（最短向量问题SVP）：在格上寻找一个非零向量v，使得对于格上任意向量u有||v||≤||u||成立。

2本文方案

假设授权文件空间W∈{0，1}k，消息空间m∈{0，1}，身份空间id∈{0，1} 。设m≥5nlogq，q≥ （）， =：

Setup：PKG运行TrapGen（1n）得到矩A∈Z阵以及格（A）的一组基TA。随机选取个独立矩阵C1，C2，…，C∈Z和k个独立矩阵D1，D2，…，Dk∈Z，选择非零向量y∈Z，运行SampleR（1m）得到2 个矩阵（（R，R）∈D，i∈[ ]，系统公开参数PP{A，（R，R） ，（Cj），（Di），y}，保存主密钥TA。

Extract：每个用户可根据自己的身份向PKG索取签名私钥。用户把自己的身份id∈{0，1} 发送给PKG，接到用户的申请后，PKG根据id的每一位选择R，并计算R=R R …R，Aid=AR-1，而后运行BasisDe（A，R，TA， ），得到（Aid）（其中Aid=AR-1）对应的一组基Tid，并将Tid发送给相应的用户，Tid即为该用户的私钥。

Sign：对于消息m∈{0，1}，用户ID根据消息m计算C=（-1）m[i]Ci，随机选择向量v1 D，运行算法samplePre（AID，TID，y-Cv1， ）得到v2∈Z，签名为。

Verify：验证者根据m计算C=（-1）m[i]Ci，然后验证（1）Cv1+AIDv2=Y；（2）||V||≤ ，若均成立则输出1，否则输出0；

Delegate：原始签名者O根据授权文件w的各个比特位计算D=（-1）W[i]Di，随机选择向量w1～D，运行算法w1～Dsampl epre（AO，To，y Dw1， ）得到w2。输出授权证书（W，w），其中。代理签名者P验证代理授权证书的有效性：首先计算D=（-1）W[i]Di，然后检验||w||≤ 和AOw2+Dw1=y是否成立，若成立则接受授权，否则请求O重新发送授权证书。

PSign：对于明文M{0，1}，代理签名者根据明文m各个位置计算C=（-1）m[i]Ci，利用私钥TP，计算Samplepre（Ap，Tp， ，Y-cw2）得到w3。则P代表对明文的代理签名为（IDO，IDP，m，W，w，pv），其中。

PVerify：对于代理签名（IDO，IDP，m，W，w，pv），验证者O通过如下方式进行验证：（1）检验m是否在授权文件w规定范围之内；（2）根据m，W计算出D=（-1）W[i]Di和C=（-1）m[i]Ci；（3）验证||w||≤ ，||pv||≤ ，AOw2+Dw1=y和Cw2+Apw3=y是否均成立，若均成立则接受签名，否则拒绝该签名。

3安全性

定理1：定理6：如果存在敌手AI能够在时间t内，以不可忽略的概率 领先本方案的一个代理签名，则存在一个多项式有界的挑战者C以不可忽略的概率（5/6） 解决一个SIS实例。

定理2：如果存在敌手AII能够在时间t内，以不可忽略的概率 伪造本方案的一个代理签名，则存在一个多项式有界挑战者c以不可忽略的概率（5/6） 解决一个SIS实例。

参考文献

[1] Paterson，K.& J.Schuldt.Efficient identity based signatures secure in the standard model[C].Proceedings of the ACISP. Melbourne， Australia， 2006：207-222.

[2] 李明祥，韓伯涛，朱建勇等.在标准模型下安全的基于身份的代理签名方案[J].华南理工大学学报：自然科学版，2009，37（05）：118-122

[3] Gentry，C.& C.Peikert&V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions[J]. In proceeding of the STOC 2008，2008：197-206.

[4] 李继国，姜平进.标准模型下可证安全的基于身份的高效签名方案[J].计算机学报，2009，32（11）：2130-2136.