格上基于盆景樹模型的環(huán)簽名

王鳳和 胡予濮 王春曉

①(西安電子科技大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 710071)

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

1 引言

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

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

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

2 基礎(chǔ)知識(shí)

2.1 格

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

2.2 格上的幾個(gè)困難問題

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

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

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

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

2.3 盆景樹原理

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

文獻(xiàn)[13]說明在盆景樹模型下可以利用上述擴(kuò)展控制算法構(gòu)造盆景樹簽名。

2.4 盆景樹簽名

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

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

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

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

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

3.1 系統(tǒng)生成

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

3.2 簽名

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

3.3 驗(yàn)證

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

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

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

4.1 匿名性

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

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

4.2 存在性不可偽造性

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

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

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

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

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

4.3 效率分析

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

5 結(jié)論

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

[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].電子與信息學(xué)報(bào), 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.