理想格上基于身份的環簽名方案

孫意如 梁向前 商玉芳

摘要：現有的簽名方案大多是基于雙線性對，但在量子計算環境下此類方案被證明是不安全的。格具有運算簡單、困難問題難以破解等特點，為了抵抗量子攻擊，基于格中標準的小整數解（SIS）困難假設，利用Ducas等提出的理想格技術（DUCAS L， MICCIANCIO D. Improved short lattice signatures in the standard model. Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2014： 335-352），構造了一種能夠在標準模型下給出安全性證明的基于身份的環簽名方案。該方案主要分為4個步驟：主密鑰生成算法Kergen（n）、簽名私鑰生成算法Extract（R，ID）、簽名算法Sign（Ts，M）和驗證算法Verify（P，M，e）。輸出的簽名為單個向量。相比同類型格上的簽名方案，在一定程度上縮減了公鑰、簽名私鑰及簽名的長度，提高了運算效率，適用于輕量級認證，算法的安全性也間接保證了電子商務和云計算等領域的安全性。

關鍵詞：

理想格；標準模型；基于身份；環簽名；小整數解

中圖分類號： TP301.6； TP309.2 文獻標志碼：A

0引言

作為加密體制與數字簽名體制的結合物，基于身份的環簽名方案是一項輕量級認證中的重要技術，在電子商務、云計算等領域有著較高的實際應用價值。1991年，群簽名的概念首次由Chaum等[1]提出，在群簽名中，任一群成員均可代表所屬群進行匿名簽名，是一種可以對簽名者進行模糊操作的簽名方案，驗證者只能檢驗簽名是否出自此群，而不能確定該群中具體的簽名者。2001年，環簽名的概念由Rivest等[2]首次提出，被稱為群簽名的簡化，與群簽名不同的是，環簽名不設立環管理員，不需要對環進行創建和撤銷等操作，簽名者可以利用自己的私鑰和其他環成員的公鑰獨立產生簽名，因而環簽名滿足無條件匿名性。2002年，結合環簽名方案和基于身份的加密方案，首個基于身份的環簽名由Kim等[3]提出，解決了簽名方案中的證書驗證和存儲難題，并受到國內外學者們的關注。最近，眾多諸如這種類型的基于身份的環簽名方案也被陸續提出，如2005年，Chow等[4]構造了一個高效的、針對雙線性對的計算次數為常數的基于身份的環簽名方案；2006年，Liu等[5]構造了一種基于身份的環簽名方案，此方案可在標準模型下給出安全性證明。以上構造的簽名方案均是基于雙線性對，而在量子計算環境下，此類方案被證明是不安全的，如1994年，Shor[6]指出：基于數論困難問題假設的加密方案不能夠有效地抵抗量子攻擊。為了設計可以抵抗量子攻擊的基于身份環簽名方案，眾多國內外學者逐漸開始嘗試利用格及特殊格的優點和特性進行簽名方案的設計。如2010年，首個標準模型下基于身份的格上環簽名方案由Wang[7]提出，但作者并沒有給出相應的安全性證明或分析；2012年，參照Boyen在2010年提出的信息添加技術[8]，田苗苗等[9]給出了一種格上的環簽名方案，相比之前提出的格上的環簽名方案，作者給出了標準模型下的選擇子環、適應性選擇消息的安全性證明，提高了此類方案的安全性，但方案的簽名長度和密鑰長度較長，不利于計算效率的提高；2013年，參照Cash等[10]在2010年給出的格基生成算法和信息添加技術，基于格中標準的小整數解（Small Integer Solution， SIS）困難問題，李玉海等[11]在格上構造了一種基于身份的環簽名方案，與文獻[8，10]中的簽名方案相比，提高了方案的計算效率，并在標準模型下給出了方案在選擇身份和消息攻擊下具有不可偽造性的證明，但方案密鑰長度、簽名長度依然不是很理想；基于SIS困難問題，2014年，參照Micciancio等[12]給出的陷門生成算法，在標準模型下，Ducas等[13]給出了一個理想格上的短格簽名方案；2015年楊丹婷等[14]也利用理想格的特殊代數結構，文獻[12]中給出的理想格技術，構造了一種基于身份的簽名（IdentityBased Signature， IBS）方案。此方案在一定程度上減少了計算復雜度，縮短了簽名和公鑰長度，可在標準模型下給出安全性證明，并在文章最后分析了在選擇身份和固定選擇消息攻擊下，方案滿足不可偽造性，但只針對單一的身份id進行簽名，無法實現方案的匿名性。

目前，還不存在量子計算方法能夠求解格上的困難問題，因此，格上的加密方案和簽名方案能夠抵抗量子攻擊。本文基于SIS困難問題，依據Ducas等[13]提出的理想格技術，構造了一種標準模型下可證安全的基于身份的環簽名方案，能夠有效抵抗選擇身份和消息攻擊。與現有的方案比較，本文利用了理想格的一些特殊代數結構，構造的方案中具有較短的公鑰和簽名私鑰，在一定程度上縮短了簽名長度，并在不減弱其安全強度的前提下，提高了方案的運算效率。

1背景知識

1.1符號說明

為了方便簽名方案的理解，在此將部分文獻中用到的符號進行簡要說明：Rm為m維實向量空間；Zn為n維整向量空間；L（A）為由矩陣A生成的格；Rn×nq為n×n維模q的實向量空間；Rq為模q的多項式環；T為標記前綴集合。

1.2格和理想格

1.4相關算法

文獻[12]給出了一種新的方法來生成和運用格密碼學上的“強陷門”，這種方法簡單、有效，易于實現，包括了一種新的陷門，反轉錯誤學習（Learning With Error， LWE）的專門算法，隨機化SIS原象取樣，以及陷門的安全授權。隨后，Ducas等[13]參照文獻[12]中的格陷門生成算法，基于理想格上逼近最短向量問題（Shortest Vector Problem， SVP）的最壞情況復雜性，提出了一個在標準模型下可證安全的簽名方案，實現了短簽名（輸出的簽名為一個格向量）和相當短的公鑰（包含O（ lb n）個向量），降低了類似的短簽名方案的計算復雜性（如文獻[12]）。參照文獻[12]的格陷門生成算法和文獻[13]的理想格技術，提出理想格上基于身份的環簽名方案，具體執行過程在第3章給出。

2IBS方案的形式化定義和安全性定義

2.1簽名方案形式化定義

定義6基于身份的環簽名方案[5]包括如下4個概率多項式時間（Probabilistic Polynomial Time， PPT）算法。

1）Kergen（n）。輸入安全參數n，算法輸出主密鑰R及系統公開參數pp。

2）Extract（R，ID）。輸入公共參數pp、主密鑰R和用戶身份ID，輸出該用戶的簽名私鑰T。

3）Sign（Ts，M）。輸入公共參數pp、用戶環P=（ID1，ID2，…，IDl）、用戶IDs的簽名私鑰Ts以及待簽名消息M，輸出該用戶對消息M的環簽名e。

4）Verify（P，M，e）。輸入公共參數pp、用戶環P=（ID1，ID2，…，IDl）、消息M及其簽名e，若e為有效簽名，則輸出Valid；否則，輸出Invalid。

2.2簽名方案安全性定義

假設一個基于身份的環簽名方案滿足兩個條件：匿名性以及不可偽造性，則可稱為是安全的簽名方案。本文依據Bender等[15]構造的模型，給出如下形式化定義。

定義7匿名性[5]。假設敵手A在多項式時間內贏得以下Game的優勢為Padv=Psuc-1/2，其中Psuc為敵手A贏得Game的概率，若Padv可忽略，則稱簽名方案滿足匿名性。

1）輸入系統安全參數n，模擬者B運行算法Kergen（n），將主密鑰R以及系統公開參數pp輸出并發送給敵手A。

2）敵手A發送用戶環P，兩個用戶身份ID0，ID1∈P及消息M∈（0，1）進行簽名詢問，模擬者B隨機選擇i∈{0，1}，計算IDi的簽名私鑰Ti，并運行簽名算法Sign（Ts，M），將簽名結果e發送給敵手A。

3）敵手A對簽名身份進行猜測，假設為i′，若IDi′=IDi，則敵手A贏得此Game。

定義8不可偽造性[5]。若敵手A在多項式時間內贏得以下Game的概率Psuc可忽略，則稱簽名方案能夠抵抗適應性選擇身份和消息攻擊，滿足不可偽造性。

1）輸入系統安全參數n，B運行算法Kergen（n），將輸出的主密鑰R保密，公開參數pp發送給敵手A。

2）敵手A隨機選擇一個用戶身份ID∈P進行多項式次數私鑰提取詢問，模擬者B運行算法Extract（R，ID），并將輸出結果發送給敵手A。

3）敵手A選擇用戶環P和消息M∈（0，1）進行多項式次數簽名詢問，模擬者B運行算法Sign（Ts，M），并將輸出簽名結果e發送給敵手A。

4）敵手A對消息M′輸出一個偽造環簽名（P′，t′，e′），若驗證環簽名（P′，t′，e′）輸出結果為Valid，且環P′中的元素沒有進行私鑰提取詢問，（P′，M′）沒有進行簽名詢問，則敵手A贏得此Game。

3理想格上基于身份的環簽名方案

4簽名方案分析

本文利用理想格中的特殊代數結構，利用Micciancio等[12]提出的格陷門生成算法GenTrap，提出了一種標準模型下基于身份的環簽名方案。

4.1有效性分析

4.2效率性分析

與其他格上同類型的基于身份的簽名方案相比，本文利用理想格的特殊代數結構構造了一種標準模型下可證安全的基于身份的環簽名方案，將待簽名消息進行隱藏后簽名。簽名公鑰、私鑰的長度都相對較短，最終輸出的簽名為單個向量，在降低運算復雜度的同時，簽名長度也在一定程度上縮短，比如文獻[11]中最終輸出的簽名為l+k+1個m維向量，簽名長度比較長，增加了簽名方案的計算復雜性。

本文的簽名方案在步驟Extract和步驟Sign中，僅需運行DelTrap算法[12]和SampleD算法[12]以及少量的向量運算，不需要相對耗時的算法，比如2010年Rückert[16]提出的簽名方案中的Extlattice算法、Extbasis算法；2013年李玉海等[11]提出的簽名方案中的ExtBasis算法、RandBasis算法，因而在一定程度上提高了算法的運算速度。為了方便比較基于格上困難問題的簽名方案的優勢和缺陷，表1給出了幾種方案的主要參數（公共參數、簽名私鑰、簽名等）長度對比。

4.3安全性分析

4.3.1匿名性

定理9本文提出的理想格上基于身份的環簽名方案滿足無條件匿名性。

證明輸入安全參數n，系統隨機選擇兩個抗碰撞Hash函數，以及d+3個獨立隨機向量A0，B0，…，Bd，U∈R1×kq，v∈Rq，模擬者B運行算法Kergen（n），將輸出的系統公開參數pp={A，A0，B0，…，Bd，U，v}和主密鑰R發送給敵手A。

敵手A接收到公共參數pp和主密鑰R之后，發送用戶環P，兩個用戶身份ID0、ID1∈P及消息M∈（0，1）給模擬者B，進行簽名詢問，模擬者B隨機選擇i∈{0，1}，運行算法Extract（R，ID），得到用戶IDi的簽名私鑰Ti，然后運行簽名算法Sign（Ts，M），將用戶IDi對消息M的簽名結果e發送給敵手A。

假設模擬者B用ID1-i的私鑰T1-i進行簽名運算，得到的簽名為e′，對于固定的用戶環P和待簽名消息M，因為所有由本文中簽名方案輸出的合法簽名都是某一特定的集合中的隨機向量，簽名e和e′的驗證向量均為Pt，即Pt·e=Pt·e′=u（mod q），故簽名e和e′具有相同的離散高斯分布。也就是說敵手A的優勢Padv是可忽略的，即本文提出的基于身份的環簽名方案滿足匿名性。

4.3.2不可偽造性

5結語

格上基于身份的環簽名方案是數字簽名的一項重要發展，能夠抵抗量子攻擊，以保證電子交易和云計算的安全性。本文基于SIS困難假設，依據Ducas等[13]提出的理想格技術，構造了一種基于身份的可在標準模型下給出安全性證明的環簽名方案。該方案具有較短的公鑰和簽名的私鑰，在一定程度上縮減了簽名長度，提高了運算效率，并且可以抵抗選擇身份和消息攻擊。本文提出的簽名方案可以延拓為理想格上基于身份的代理（盲）簽名方案、簽密方案、代理（盲）簽密方案等，下一步的工作是設計構造密鑰和簽名更短的簽名方案和理想格上的簽密方案。

參考文獻：

[1]

CHAUM D， VAN HEYST E. Group signature [C]// EUROCRYPT91： Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques. Berlin： Springer， 1991： 257-265.

[2]

RIVEST R L， SHAMIR A R， TAUMAN Y. How to leak a secret [C]// ASIACRYPT01： Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security： Advances in Cryptology. Berlin： Springer， 2001： 552-565.

[3]

ZHANG F， KIM K. IDbased blind signature and ring signature from pairing [C]// ASIACRYPT02： Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security： Advances in Cryptology. Berlin： Springer， 2002： 533-547.

[4]

CHOW S S M， YIU S M， HUI L C K. Efficient identity based ring signature [C]// ACNS05： Proceedings of the Third International Conference on Applied Cryptography and Network Security. Berlin： Springer， 2005： 499-512.

[5]

AU M H， LIU J K， YUEN T H， et al. IDbased ring signature scheme secure in the standard model [C]// IWS 2006： Proceedings of the 2006 International Workshop on Security. Berlin： Springer， 2006： 1-16.

[6]

SHOR P W. Polynomialtime algorithm for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing， 1997， 26（5）： 1484-1509.

[7]

WANG J. Ring signature and identitybased ring signature from lattice basis delegation [EB/OL]. [20151019]. http：//eprint.iacr.org/2010/378.

[8]

BOYEN X. Lattice mixing and vanishing trapdoors： a framework for fully secure short signatures and more [C]// PKC 2010： Proceedings of the 2010 Public Key Cryptography. Berlin： Springer， 2010： 499-517.

[9]

田苗苗，黃劉生，楊威.高效的基于格的環簽名方案[J].計算機學報，2012，35（4）：712-718.（TIAN M M， HUANG L S， YANG W. An efficient ring scheme based on lattice [J]. Chinese Journal of Computers， 2012， 35（4）： 712-718.）

[10]

CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees or how to delegate a lattice basis [C]// EUROCRYPT10： Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 523-552.

[11]

李玉海，田苗苗，黃劉生.一種格上基于身份的環簽名方案[J].小型微型計算機系統，2013，34（8）：1768-1771.（LI Y H，TIAN M M， HUANG L S. An identity based ring signature scheme on lattice [J]. Journal of Chinese Computer Systems，2013， 34（8）： 1768-1771）.

[12]

MICCIANCIO D， PEIKERT C. Trapdoors for lattices： simpler， tighter， faster， smaller [C]// EUROCRYPT12： Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 700-718.

[13]

DUCAS L， MICCIANCIO D. Improved short lattice signatures in the standard model [C]// Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2014： 335-352.

[14]

楊丹婷，許春根，徐磊，等.理想格上基于身份的簽名方案[J].密碼學報，2015，2（4）：306-316.（YANG D T， XU C G， XU L， et al. Identitybased signature scheme over ideal lattices [J]. Journal of Cryptologic Research， 2015， 2（4）： 306-316.）

[15]

BENDER A， KATZ J， MORSELLI R. Ring signatures： stronger definitions and constructions without random oracles [J]. Journal of Cryptology， 2009， 22（1）： 114-138.

[16]

RCKERT M. Strongly unforgeable signatures and hierarchical identitybased signatures from lattices without random oracles [C]// PQC 2010： Proceedings of the 2010 PostQuantum Cryptography. Berlin： Springer， 2010： 182-200.

[17]

李明祥，劉陽，趙秀明.高效的格上基于身份的簽名方案[J].計算機應用研究，2014，31（3）：825-828.（LI M X， LIU Y， ZHAO X M. Efficient identitybased signature scheme from lattices [J]. Application Research of Computers， 2014， 31（3）： 825-828.）