一種格上基于身份的代理簽名方案

王黎

摘 要 本文利用原像抽樣技術和固定維數(shù)的格基委托技術，在Boyen簽名方案的基礎上，構造了一個格上基于身份的代理簽名方案。

關鍵詞 代理簽名 格 匿名性

中圖分類號：TP391 文獻標識碼：A

0引言

基于身份的代理重加密是指代理把發(fā)送給一個身份的密文轉化為給另一個身份的密文，可將身份加密與代理加密的優(yōu)點集于一身，應用范圍更廣。隨著信息安全領域對于安全性的要求越來越高，這種不同加密體制的交叉融合具有非常重要的研究意義和廣泛的應用前景。

1基礎知識

格（Lattice）是一類定義在有限域上的、離散的幾何結構，是線性空間中n維向量構成的一個子集。其定義如下：

定義1：在n維向量空間中m個線性無關的向量（b1，b2，…，bm）所生成的向量集合：

L（b1，b2，…，bn）=

稱為格。（b1，b2，…，bn）稱為格的一組基。

格中向量x的長度用歐幾里德范數(shù)||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∈[ ]，系統(tǒng)公開參數(shù)PP{A，（R，R） ，（Cj），（Di），y}，保存主密鑰TA。

Extract：每個用戶可根據(jù)自己的身份向PKG索取簽名私鑰。用戶把自己的身份id∈{0，1} 發(fā)送給PKG，接到用戶的申請后，PKG根據(jù)id的每一位選擇R，并計算R=R R …R，Aid=AR-1，而后運行BasisDe（A，R，TA， ），得到（Aid）（其中Aid=AR-1）對應的一組基Tid，并將Tid發(fā)送給相應的用戶，Tid即為該用戶的私鑰。

Sign：對于消息m∈{0，1}，用戶ID根據(jù)消息m計算C=（-1）m[i]Ci，隨機選擇向量v1 D，運行算法samplePre（AID，TID，y-Cv1， ）得到v2∈Z，簽名為。

Verify：驗證者根據(jù)m計算C=（-1）m[i]Ci，然后驗證（1）Cv1+AIDv2=Y；（2）||V||≤ ，若均成立則輸出1，否則輸出0；

Delegate：原始簽名者O根據(jù)授權文件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重新發(fā)送授權證書。

PSign：對于明文M{0，1}，代理簽名者根據(jù)明文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規(guī)定范圍之內；（2）根據(jù)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內，以不可忽略的概率 領先本方案的一個代理簽名，則存在一個多項式有界的挑戰(zhàn)者C以不可忽略的概率（5/6） 解決一個SIS實例。

定理2：如果存在敵手AII能夠在時間t內，以不可忽略的概率 偽造本方案的一個代理簽名，則存在一個多項式有界挑戰(zhàn)者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.