孫意如 梁向前 商玉芳

摘要：現(xiàn)有的簽名方案大多是基于雙線(xiàn)性對(duì)，但在量子計(jì)算環(huán)境下此類(lèi)方案被證明是不安全的。格具有運(yùn)算簡(jiǎn)單、困難問(wèn)題難以破解等特點(diǎn)，為了抵抗量子攻擊，基于格中標(biāo)準(zhǔn)的小整數(shù)解（SIS）困難假設(shè)，利用Ducas等提出的理想格技術(shù)（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），構(gòu)造了一種能夠在標(biāo)準(zhǔn)模型下給出安全性證明的基于身份的環(huán)簽名方案。該方案主要分為4個(gè)步驟：主密鑰生成算法Kergen（n）、簽名私鑰生成算法Extract（R，ID）、簽名算法Sign（Ts，M）和驗(yàn)證算法Verify（P，M，e）。輸出的簽名為單個(gè)向量。相比同類(lèi)型格上的簽名方案，在一定程度上縮減了公鑰、簽名私鑰及簽名的長(zhǎng)度，提高了運(yùn)算效率，適用于輕量級(jí)認(rèn)證，算法的安全性也間接保證了電子商務(wù)和云計(jì)算等領(lǐng)域的安全性。

關(guān)鍵詞：

理想格；標(biāo)準(zhǔn)模型；基于身份；環(huán)簽名；小整數(shù)解

中圖分類(lèi)號(hào)： TP301.6； TP309.2 文獻(xiàn)標(biāo)志碼：A

0引言

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

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

1背景知識(shí)

1.1符號(hào)說(shuō)明

為了方便簽名方案的理解，在此將部分文獻(xiàn)中用到的符號(hào)進(jìn)行簡(jiǎn)要說(shuō)明：Rm為m維實(shí)向量空間；Zn為n維整向量空間；L（A）為由矩陣A生成的格；Rn×nq為n×n維模q的實(shí)向量空間；Rq為模q的多項(xiàng)式環(huán)；T為標(biāo)記前綴集合。

1.2格和理想格

1.4相關(guān)算法

文獻(xiàn)[12]給出了一種新的方法來(lái)生成和運(yùn)用格密碼學(xué)上的“強(qiáng)陷門(mén)”，這種方法簡(jiǎn)單、有效，易于實(shí)現(xiàn)，包括了一種新的陷門(mén)，反轉(zhuǎn)錯(cuò)誤學(xué)習(xí)（Learning With Error， LWE）的專(zhuān)門(mén)算法，隨機(jī)化SIS原象取樣，以及陷門(mén)的安全授權(quán)。隨后，Ducas等[13]參照文獻(xiàn)[12]中的格陷門(mén)生成算法，基于理想格上逼近最短向量問(wèn)題（Shortest Vector Problem， SVP）的最壞情況復(fù)雜性，提出了一個(gè)在標(biāo)準(zhǔn)模型下可證安全的簽名方案，實(shí)現(xiàn)了短簽名（輸出的簽名為一個(gè)格向量）和相當(dāng)短的公鑰（包含O（ lb n）個(gè)向量），降低了類(lèi)似的短簽名方案的計(jì)算復(fù)雜性（如文獻(xiàn)[12]）。參照文獻(xiàn)[12]的格陷門(mén)生成算法和文獻(xiàn)[13]的理想格技術(shù)，提出理想格上基于身份的環(huán)簽名方案，具體執(zhí)行過(guò)程在第3章給出。

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

2.1簽名方案形式化定義

定義6基于身份的環(huán)簽名方案[5]包括如下4個(gè)概率多項(xiàng)式時(shí)間（Probabilistic Polynomial Time， PPT）算法。

1）Kergen（n）。輸入安全參數(shù)n，算法輸出主密鑰R及系統(tǒng)公開(kāi)參數(shù)pp。

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

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

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

2.2簽名方案安全性定義

假設(shè)一個(gè)基于身份的環(huán)簽名方案滿(mǎn)足兩個(gè)條件：匿名性以及不可偽造性，則可稱(chēng)為是安全的簽名方案。本文依據(jù)Bender等[15]構(gòu)造的模型，給出如下形式化定義。

定義7匿名性[5]。假設(shè)敵手A在多項(xiàng)式時(shí)間內(nèi)贏(yíng)得以下Game的優(yōu)勢(shì)為Padv=Psuc-1/2，其中Psuc為敵手A贏(yíng)得Game的概率，若Padv可忽略，則稱(chēng)簽名方案滿(mǎn)足匿名性。

1）輸入系統(tǒng)安全參數(shù)n，模擬者B運(yùn)行算法Kergen（n），將主密鑰R以及系統(tǒng)公開(kāi)參數(shù)pp輸出并發(fā)送給敵手A。

2）敵手A發(fā)送用戶(hù)環(huán)P，兩個(gè)用戶(hù)身份ID0，ID1∈P及消息M∈（0，1）進(jìn)行簽名詢(xún)問(wèn)，模擬者B隨機(jī)選擇i∈{0，1}，計(jì)算IDi的簽名私鑰Ti，并運(yùn)行簽名算法Sign（Ts，M），將簽名結(jié)果e發(fā)送給敵手A。

3）敵手A對(duì)簽名身份進(jìn)行猜測(cè)，假設(shè)為i′，若IDi′=IDi，則敵手A贏(yíng)得此Game。

定義8不可偽造性[5]。若敵手A在多項(xiàng)式時(shí)間內(nèi)贏(yíng)得以下Game的概率Psuc可忽略，則稱(chēng)簽名方案能夠抵抗適應(yīng)性選擇身份和消息攻擊，滿(mǎn)足不可偽造性。

1）輸入系統(tǒng)安全參數(shù)n，B運(yùn)行算法Kergen（n），將輸出的主密鑰R保密，公開(kāi)參數(shù)pp發(fā)送給敵手A。

2）敵手A隨機(jī)選擇一個(gè)用戶(hù)身份ID∈P進(jìn)行多項(xiàng)式次數(shù)私鑰提取詢(xún)問(wèn)，模擬者B運(yùn)行算法Extract（R，ID），并將輸出結(jié)果發(fā)送給敵手A。

3）敵手A選擇用戶(hù)環(huán)P和消息M∈（0，1）進(jìn)行多項(xiàng)式次數(shù)簽名詢(xún)問(wèn)，模擬者B運(yùn)行算法Sign（Ts，M），并將輸出簽名結(jié)果e發(fā)送給敵手A。

4）敵手A對(duì)消息M′輸出一個(gè)偽造環(huán)簽名（P′，t′，e′），若驗(yàn)證環(huán)簽名（P′，t′，e′）輸出結(jié)果為Valid，且環(huán)P′中的元素沒(méi)有進(jìn)行私鑰提取詢(xún)問(wèn)，（P′，M′）沒(méi)有進(jìn)行簽名詢(xún)問(wèn)，則敵手A贏(yíng)得此Game。

3理想格上基于身份的環(huán)簽名方案

4簽名方案分析

本文利用理想格中的特殊代數(shù)結(jié)構(gòu)，利用Micciancio等[12]提出的格陷門(mén)生成算法GenTrap，提出了一種標(biāo)準(zhǔn)模型下基于身份的環(huán)簽名方案。

4.1有效性分析

4.2效率性分析

與其他格上同類(lèi)型的基于身份的簽名方案相比，本文利用理想格的特殊代數(shù)結(jié)構(gòu)構(gòu)造了一種標(biāo)準(zhǔn)模型下可證安全的基于身份的環(huán)簽名方案，將待簽名消息進(jìn)行隱藏后簽名。簽名公鑰、私鑰的長(zhǎng)度都相對(duì)較短，最終輸出的簽名為單個(gè)向量，在降低運(yùn)算復(fù)雜度的同時(shí)，簽名長(zhǎng)度也在一定程度上縮短，比如文獻(xiàn)[11]中最終輸出的簽名為l+k+1個(gè)m維向量，簽名長(zhǎng)度比較長(zhǎng)，增加了簽名方案的計(jì)算復(fù)雜性。

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

4.3安全性分析

4.3.1匿名性

定理9本文提出的理想格上基于身份的環(huán)簽名方案滿(mǎn)足無(wú)條件匿名性。

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

敵手A接收到公共參數(shù)pp和主密鑰R之后，發(fā)送用戶(hù)環(huán)P，兩個(gè)用戶(hù)身份ID0、ID1∈P及消息M∈（0，1）給模擬者B，進(jìn)行簽名詢(xún)問(wèn)，模擬者B隨機(jī)選擇i∈{0，1}，運(yùn)行算法Extract（R，ID），得到用戶(hù)IDi的簽名私鑰Ti，然后運(yùn)行簽名算法Sign（Ts，M），將用戶(hù)IDi對(duì)消息M的簽名結(jié)果e發(fā)送給敵手A。

假設(shè)模擬者B用ID1-i的私鑰T1-i進(jìn)行簽名運(yùn)算，得到的簽名為e′，對(duì)于固定的用戶(hù)環(huán)P和待簽名消息M，因?yàn)樗杏杀疚闹泻灻桨篙敵龅暮戏ê灻际悄骋惶囟ǖ募现械碾S機(jī)向量，簽名e和e′的驗(yàn)證向量均為Pt，即Pt·e=Pt·e′=u（mod q），故簽名e和e′具有相同的離散高斯分布。也就是說(shuō)敵手A的優(yōu)勢(shì)Padv是可忽略的，即本文提出的基于身份的環(huán)簽名方案滿(mǎn)足匿名性。

4.3.2不可偽造性

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]

田苗苗，黃劉生，楊威.高效的基于格的環(huán)簽名方案[J].計(jì)算機(jī)學(xué)報(bào)，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]

李玉海，田苗苗，黃劉生.一種格上基于身份的環(huán)簽名方案[J].小型微型計(jì)算機(jī)系統(tǒng)，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].密碼學(xué)報(bào)，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]

李明祥，劉陽(yáng)，趙秀明.高效的格上基于身份的簽名方案[J].計(jì)算機(jī)應(yīng)用研究，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.）