王鳳和 胡予濮 王春曉

①(西安電子科技大學計算機網(wǎng)絡與信息安全教育部重點實驗室 西安 710071)

②(泰山學院數(shù)學與系統(tǒng)科學學院 泰安 271021)③(山東建筑大學理學院 濟南 250101)

1 引言

2001年，Rivest, Shamir 和Tauman[1]提出了環(huán)簽名的概念。環(huán)簽名允許成員完全匿名地實現(xiàn)簽名，驗證者可以驗證該簽名來自群組的成員，但無法確定簽名者的身份。環(huán)簽名提出后引起了廣泛關注，提出了各種基于數(shù)論假設或者利用雙線性對設計的標準環(huán)簽名方案[2?5]及其變形的環(huán)簽名方案如可控環(huán)簽名[6]，代理環(huán)簽名[7,8]等。環(huán)簽名及其變形方案可以被廣泛的應用于電子選舉、電子現(xiàn)金、Ad hoc groups的匿名身份(認證)等領域。然而已有工作說明著名的大整數(shù)分解與離散對數(shù)問題在量子計算機上都可以在多項式時間內(nèi)解決[9]，從而使得基于它們設計的密碼系統(tǒng)在量子環(huán)境下都將不再安全。因此設計在后量子時代依然確保安全的環(huán)簽名方案成為環(huán)簽名領域一個有意義的研究方向。

格上的困難問題具有在量子計算環(huán)境下依然安全的特點，因此基于格設計密碼算法具有后量子安全的優(yōu)勢。格上設計的密碼系統(tǒng)除具有量子安全的特點之外還有其他的優(yōu)點，例如格上算法的結構簡單，運算快捷(主要使用模乘和模加運算而且僅僅涉及小整數(shù)運算)、格上困難問題在最壞和一般狀態(tài)下的困難性等價等等。近幾年來，越來越多的密碼學家開始關注在一般格上設計可證明安全的密碼系統(tǒng)，取得一系列的重要成果[10?16]。但與利用大數(shù)分解、離散對數(shù)設計的大量帶有特殊安全性能的方案、協(xié)議比較，基于一般格建立的密碼系統(tǒng)才剛剛起步，在格上設計的具有特殊功能的密碼系統(tǒng)還很少，尤其注意到還沒有在格上實現(xiàn)環(huán)簽名的設計(盡筆者所知)。因此基于格設計環(huán)簽名方案作為格理論在環(huán)簽名領域中的有效應用也成為格基密碼一個有價值的研究課題。

2009年E-Print上公開Peikert[13]的最新研究成果，Peikert在格上利用格和基的擴充技術和原象抽樣函數(shù)[16]在盆景樹模型(Bonsai Trees)下設計了一個標準模型下的數(shù)字簽名方案和一個分級身份加密方案，其核心工作是盆景樹模型下的格擴充技術，即從一個母格及其一組小的基向量(好基或小基)出發(fā)構造更高維數(shù)的格和它上面的小基。本文利用盆景樹簽名構造了一個格上的環(huán)簽名方案。本文的環(huán)簽名方案中每一位環(huán)成員掌握著一個格矩陣作為公鑰，對應格上的一組小基作為成員的簽名密鑰。在每次簽名時，簽名者以自己公鑰對應的格作為盆景樹的根節(jié)點(母格)利用其他成員的公開鑰和簽名消息將自己的格擴展，得到一個更大維數(shù)的格并以此格作為盆景樹的下一級節(jié)點(子格)，建立一個盆景樹模型，在此過程中同時把母格上的小基擴展得到子格上的一組小基。利用子格上的小基通過盆景樹簽名完成自己的環(huán)簽名。方案的安全性分析中說明方案允許成員實現(xiàn)完全匿名簽名，驗證者可以驗證簽名的合法性，并判斷簽名者確實來自群組，但是任何人不能發(fā)現(xiàn)簽名者的身份。在標準模型下，證明方案的安全性是基于格上SIS問題的困難性。而格上SIS問題是量子計算環(huán)境下的困難問題，所以我們的格基環(huán)簽名具有量子安全的特性。

2 基礎知識

2.1 格

設v1, v2,…,vn是Rn上一組線性無關的向量，格Λ定義為所有這些向量的整數(shù)線性組合構成的集合，即構成格Λ的一組基。設ω是一個向量，將定義為向量ω的lp-范數(shù)，當p=2時，稱作歐幾里得范數(shù)。

2.2 格上的幾個困難問題

以SVP和CVP問題為核心的格上困難問題，是格基密碼安全性的保障，SVP和CVP存在很多近似問題，本節(jié)僅僅介紹本文相關的SVP和CVP和其近似問題-SIS問題。

(1)SVP問題 設A是格的一組基，SVP問題就是在格上尋找一個非零向量u滿足任意格上的向量v,有||u||≤||v||成立。其中||?||為給定的范數(shù)。

(2)CVP問題 設A是格的一組基，ω是一個向量，CVP問題就是要在格上尋找u，使得任意格上的向量v有：||u?ω||≤||v?ω||。其中||?||為給定的范數(shù)。

(3)SIS問題(小整數(shù)解問題)參數(shù)q(?),m(n),β(?),給定n和尋找一個非零向量e，滿足：Ae=0modq(n),||e||≤β(n)。

2.3 盆景樹原理

Peikert引入的盆景樹模型事實上是一個分級陷門函數(shù)，在盆景樹模型下以某個格(一組基)作為根節(jié)點可以生成一個更大維數(shù)的格作為下一級的枝節(jié)點，同時得到格的一組基。這種由“根”到“枝”的“生長”可以是無陷門的即無指導生長(undirected growth)，此時“盆景師”在分級過程中沒有使用陷門因此沒有任何特權；也可以是有陷門時由“盆景師”控制盆景樹的“生長”過程，包括控制生長(controlled growth)、擴展控制(extending control)和隨機控制(randoming control)。本文主要使用盆景樹的擴展控制方法，細節(jié)及其他原理參照文獻[13]。格上的擴展控制(extending control)算法是一個由較小維數(shù)的格和基向量構造更大維數(shù)的格和基向量的算法。設任意一個格Λ(A)以及它的一組基S，由(A,S)得到一個更大維數(shù)的格Λ(A′)=Λ(A||)及其基向量S′。我們將擴展控制記為ExBasis(S, A′=A||)，算法描述如下：

文獻[13]說明在盆景樹模型下可以利用上述擴展控制算法構造盆景樹簽名。

2.4 盆景樹簽名

本節(jié)簡要介紹文獻[13]給出的盆景樹簽名方案。

注：簽名的各個參數(shù)都是n的函數(shù)。

2.4.2 簽名 設簽名消息M的hash值為μ∈(0,1)，根據(jù)μ各個位置的值選擇對應公鑰∈，令：=A||||||||…∈，利用擴展控制算法[13]得到格Aμ上的一組小基，進而利用原象抽樣函數(shù)[16]生成格Aμ上的一個小向量：v=Sample D(Exbasis(S, Aμ),s)。如果取樣得到0向量或者||v||≥s，則重新取樣。向量v作為消息M的簽名。

2.4.3 驗證 首先計算消息M的hash值μ∈(0,1)，根據(jù)μ各個位置的值選擇對應公鑰∈，并與簽名者的公鑰級聯(lián)得到矩陣=A||||||||…∈，然后驗證：(1)v≠0，||v||≤s;(2)Aμv=0。通過則接受簽名，否則拒絕簽名。

3 本文提出的環(huán)簽名方案

3.1 系統(tǒng)生成

n為整個方案的安全參數(shù)，其他參數(shù)都是n的函數(shù)。設U1…Ul是l個用戶分別掌握一個格矩陣，以及對應格上的一組小基Si。密鑰分配中心隨機、獨立地生成2k個矩陣∈，j=1,2,…,k，e=0或1。同時密鑰分配中心也要將環(huán)成員的公鑰級聯(lián)成一個新的矩陣=1AA||A2||A3||…||Al?1||Al。設h(?):{0,1}*→{0,1}k為一個輸出為k-bit的安全hash函數(shù)。則環(huán)公鑰為(, A)，j=1,2,…,k，e=0或1，對應格上的Si作為用戶Ui的簽名密鑰。其它安全參數(shù)定義為：m1=O(n?logn)，m2=O(n?logn)，m′=lm1+km2，

3.2 簽名

設用戶Ui要生成簽名消息M的簽名，消息的hash值μ=h(M)∈(0,1)k。Ui首先利用對應μ∈(0,1)k的各個分值選擇公開參數(shù)矩陣，然后建立盆景樹：利用秘密鑰Si將格iA擴展為更大維數(shù)的格，并生成此格上的一組小基′。然后用戶Ui改變′A中各個子陣iA的位置使之與環(huán)公鑰A一致并相應得改變基中各分量的位置，得到Aμ和Sμ。通過Aμ,Sμ，利用盆景樹簽名得到向量v：v=SampleD(Exbasis(Si, Aμ),s)。v作為消息M的簽名。

3.3 驗證

驗證者得到消息M的簽名v后，首先計算hash函數(shù)值μ=h(M)∈(0,1)k，利用μ的各個分量值選取環(huán)參數(shù)矩陣，并與環(huán)公鑰A級聯(lián)得到Aμ，然后驗證：(1)v≠0，||v||≤s; (2)Aμv=0。通過以上驗證則接受簽名，否則拒絕簽名。

說明 該環(huán)簽名的主要基于盆景樹簽名格完成簽名，完備性驗證參照文獻[13]，本文略。

4 環(huán)簽名的性能分析

4.1 匿名性

定理1 本文的方案實現(xiàn)了簽名者身份的完全匿名性。

證明 消息的環(huán)簽名是大維數(shù)格上的一個范數(shù)較小的向量，而大維數(shù)格矩陣Aμ中子陣A包含所有環(huán)成員的公鑰信息，注意到這些公鑰的位置是完全平等的，因此從任何一個成員的公鑰出發(fā)都可能得到該消息的簽名v，即每一個成員都可能生成此簽名，因此驗證者不能從v中分解出簽名者公鑰的任何信息，他只能以1/l的概率推測簽名人的身份，l是成員的個數(shù)；而要通過大維數(shù)格上的一個小向量得到小維數(shù)格上的一組小基(簽名密鑰)來對應簽名人的身份更是不可行的。進一步地，消息的環(huán)簽名v服從格上的正態(tài)分布[13]，因此任意兩個環(huán)成員的簽名或者一個環(huán)成員對兩個消息的簽名服從的概率分布對驗證者而言是不可區(qū)分的。所以環(huán)簽名實現(xiàn)了無條件匿名性。 證畢

4.2 存在性不可偽造性

定義1 存在性不可偽造：一個簽名方案稱作是存在性不可偽造的，如果對于任意多項式時間的偽造者在掌握簽名公鑰的條件下通過與簽名者的多項式有限次的交互得到有限個消息對應的簽名，如果偽造者能夠輸出一個新消息的合法簽名的概率是可以忽略的。

定理2 假設存在不是任何環(huán)成員的概率多項式時間敵手F能夠至多通過Q次hash詢問，Q1次環(huán)簽名詢問以不可忽略的概率ε偽造新的消息μ(假設μ是一個hash值)的合法環(huán)簽名，其中消息μ從未在簽名詢問中被詢問過。則可以構造算法S以近似ε/kQ1的概率來解大維數(shù)格上的SIS問題。

將矩陣A0作為環(huán)簽名方案中環(huán)成員公鑰級聯(lián)得到矩陣，矩陣對應一個環(huán)簽名方案中的環(huán)公開參數(shù)矩陣。以(A0,)來初始化敵手F，讓敵手F來攻擊以上環(huán)簽名。

簽名詢問：設算法S開始為敵手F發(fā)送消息μJ的簽名詢問生成環(huán)簽名：在列表L2中尋找此消息的簽名記錄vJ，若找到此消息則返回列表中相應的vJ作為簽名。若消息μJ不在L2中，設i為第一個滿足≠p的位置，算法S通過格及其好基S利ii用盆景樹下的擴展控制算法得到格AμJ=A0||||||…||||及其好基S，然后μJ利用原象抽樣算法得到消息μJ的簽名vJ，將消息μJ的簽名vJ發(fā)送給敵手F，同時在列表L2中存儲消息μJ及其簽名vJ。 在敵手F對所有簽名詢問滿意后，敵手F以概率ε生成第Q1+1個消息μQ1+1的偽造簽名vQ+1。算法S檢查p是否是消息μQ+1的前綴，如果不是μQ1+1的前綴，算法S終止游戲，宣布失敗。否則p是μQ1+1的前綴，則矩陣AμQ+1是由矩陣A0和k個Ui(b)級聯(lián)得到。所以算法S可以通過添加子陣并調(diào)整子陣的順序同時在vQ1+1上添加相應的0并調(diào)整順序，得到一個向量v，滿足：Av=0(modq),由模擬過程知||v||≤s。從而算法S成功得到Ax=0的一個小整數(shù)解。

分析算法S成功的優(yōu)勢：算法S成功的關鍵是隨機選取的集合T中的比特串p應該是第Q1+1個消息μQ1+1的前綴，此概率接近1/kQ1,從而算法S成功的概率近似為ε/kQ1。 證畢

4.3 效率分析

方案的一個不足之處是在簽名時要將盆景樹模型下的母格擴充為一個比原始盆景樹簽名更大維數(shù)的格，原因是環(huán)成員需要聯(lián)合其他成員的公鑰。這使得環(huán)簽名中簽名格的維數(shù)要大于原始的盆景樹簽名。設m1=c1nlgq,m2=c2nlg q ，其中c1,c2為常數(shù)，本文的方案中簽名格矩陣的列數(shù)和簽名長度為kc1nlgq+lc2nlg q ，l為環(huán)成員的個數(shù)。所以本文簽名效率要低于盆景樹簽名，事實上一般的特殊簽名的效率總要比原始簽名要低。本文環(huán)簽名方案中用戶的密鑰長度都為m1lgq，與盆景樹簽名相同。公鑰長度為2km2nlgq+lm1nlg q ，其中l(wèi)是環(huán)成員個數(shù)，k是hash函數(shù)的輸出長度。由于方案設計中僅僅使用到了小整數(shù)的模加和模乘運算，所以計算效率較高。但是方案密鑰長度較大，所以存儲代價較高，這也是當前格基密碼普遍存在的效率瓶頸。如何設計效率更高的格基環(huán)簽名方案值得進一步研究。

5 結論

利用盆景樹模型，借助盆景樹簽名，在格上構造了一個環(huán)簽名方案。實現(xiàn)了環(huán)簽名的完全匿名性和簽名的存在性不可偽造性，在標準模型下證明方案的不可偽造性是基于格上SIS問題的困難性，因此方案具有在量子計算環(huán)境下依然安全的優(yōu)點。

[1] Rivest R, Shamir A, and Tauman Y. How to leak a secret [C].AsiaCrypt2001. Berlin, Springer-Verlag, 2001, Vol. 2248:552-565.

[2] Zhang Fang-guo and Kim K. ID-based blind signature and ring signature from pairings[C]. ASIACRYPT 2002,Queenstown, New Zealand, 2002: 533-547.

[3] Chow S. M, Yiu S-M, and Hui L C K. Efficient identity based ring signature[C]. ACNS 2005, LNCS, 2005, Vol. 3531:499-512.

[4] Herranz J and S′aez G. New identity-based ring signature schemes[C]. ICICS2004, LNCS, 2004, Vol. 3269: 27-39.

[5] Dodis Y, Kiayias A, Nicolosi A, and Shoup V. Anonymous identification in Ad Hoc groups[C]. Eurocrypt’2004, LNCS,2004, Vol.3027: 609-626.

[6] Wei Gao, Wang Gui-lin, Wang Xue-li, and Xie Dong-qing.Controllable ring signatures[C]. WISA 2006, LNCS, 2007,Vol. 4298: 1-14.

[7] Li Jin, Chen Xiao-feng, Yuen Tsz-hon, and Wang Yan-ming.Proxy ring signature: formal definitions, efficient construction and new variant[C]. CIS2006, LNAI, 2007,Vol.4456: 545-555.

[8] 鮑皖蘇, 隗云, 鐘普查. 原始簽名人匿名的代理環(huán)簽名研究[J].電子與信息學報, 2009, 31(10): 2392-2396.Bao Wan-su, Wei Yun, and Zhong Pu-cha. Research on proxy ring signature with anonymity of the original signer. Journal of Electronics & Information Technology, 2009, 31(10):2392-2396.

[9] Shor P W. Polynomial-time algorithm for prime factorizeation and discrete logarithm on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5):1484-1509.

[10] Lyubashevsky V and Micciancio D. Asymptotically Efficient Lattice-Based Digital Signature[C]. TCC2008, LNCS, 2008,Vol. 4948: 37-54.

[11] Regev O. On Lattice, learning with errors, random linear codes, and cryptography[C]. STOC’05, Baltimore, MD 2005:84-93.

[12] Lyubashevsky V. Lattice-based identification schemes secure under active attacks[C]. PKC’ 2008, LNCS, 2008, Vol. 4939:162-179.

[13] Peikert C. Bonsai Trees [EB/OL]. http:// eprint.iacr.org/2009/359.

[14] Alwen J and Peikert C. Generating shorter bases for hard random lattices[C]. In STACS’2009, Freiburg-Germany, 2009:75-86.

[15] Micciancio D and Regev O. Worst-case to average-case reductions based on gaussian measures[J]. SIAM J.Compututer, 2007, 37(1): 267-302.

[16] Gentry C, Peikert C, and Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C].STOC’2008, Victoria, BC- Canada, 2008: 197-206.