利用環(huán)上容錯學(xué)習(xí)問題構(gòu)造可鏈接環(huán)簽名方案*

葉 青，王文博，李瑩瑩，秦攀科，趙宗渠，王永軍

河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作454000

1 引言

環(huán)簽名的概念由Rivest 等[1]在2001 年首次提出。該方案允許簽名者匿名選擇一個簽名組。簽名者對消息進(jìn)行簽名，驗(yàn)證者僅能確定簽名者為組中一員，但無法確定哪一個成員。2004年，Liu等[2]在環(huán)簽名中引入了一種稱為可鏈接性的擴(kuò)展屬性，相應(yīng)的環(huán)簽名方案現(xiàn)在被稱為可鏈接環(huán)簽名。可鏈接環(huán)簽名在保持簽名者匿名性的同時，能夠檢測出兩個環(huán)簽名是否由同一簽名者（使用同一私鑰）生成?？涉溄迎h(huán)簽名在加密貨幣、電子選舉、電子現(xiàn)金等應(yīng)用場景[3-5]中有重要應(yīng)用。2007 年，Au 等[6]將基于證書的密碼體制（certificate based cryptography，CBC）與可鏈接環(huán)簽名結(jié)合，提出了一種基于證書的可鏈接環(huán)簽名方案。2013 年，Liu 等[7]將可鏈接環(huán)簽名的安全性進(jìn)一步提高，提出了無條件匿名的可鏈接環(huán)簽名方案（以往的可鏈接環(huán)簽名方案的匿名性均為計算匿名性）。

然而，上述環(huán)簽名（可鏈接環(huán)簽名）方案都是基于經(jīng)典的數(shù)論難題假設(shè)（如離散對數(shù)難題[8]和大整數(shù)因子分解難題[9]），由于這類難題存在高效的量子破譯算法[10]，如果未來量子計算機(jī)成熟，基于經(jīng)典數(shù)論難題的密碼體制將不再安全。這種情況下，密碼領(lǐng)域的學(xué)者們開始研究后量子密碼學(xué)。在這些替代方案中，基于格的密碼學(xué)由于其高效簡單、高度可并行化，并可提供強(qiáng)有力的可證明安全保證而備受關(guān)注。文獻(xiàn)[11]提出了一種高效的基于格的環(huán)簽名，但是主要缺點(diǎn)是公鑰、私鑰及簽名長度較大。文獻(xiàn)[12]基于格上弱偽隨機(jī)函數(shù)（weak pseudo random function，wPRF）、累加器和零知識證明構(gòu)建了第一個格上可鏈接環(huán)簽名方案。該方案的安全性基于小整數(shù)解（short integer solution，SIS）難題假設(shè)[13]。文獻(xiàn)[14]基于理想格上同態(tài)承諾方案和∑-協(xié)議框架[15]，構(gòu)建一個理想格上可鏈接環(huán)簽名方案，并基于理想格上最短向量問題（shortest vector problem，SVP）證明方案的安全性。文獻(xiàn)[16]基于格上抗沖突的哈希函數(shù)構(gòu)建了一個格上可鏈接環(huán)簽名方案，方案的安全性基于模格小整數(shù)解（module short integer solution，Module-SIS）困難問題（SIS 困難問題的變體）和模格容錯學(xué)習(xí)（module learing with errors，Module-LWE）困難問題（LWE困難問題的變體）。

最近，文獻(xiàn)[17]基于BLISS（bimodal lattice signature scheme）[18]構(gòu)造了一個格上無條件匿名的可鏈接環(huán)簽名方案。該方案基于環(huán)上小整數(shù)解（ring short integer solution，RSIS）[19]困難問題，其簽名長度為O(N)。一般來說，格上密碼方案常用的困難問題是SIS 和容錯學(xué)習(xí)問題（learing with errors，LWE），但是基于LWE困難問題的格上密碼方案通常存在密鑰尺寸過長，密文空間較大，效率較低的問題，而RSIS 和環(huán)上容錯學(xué)習(xí)問題（ring learning with errors，RLWE）[20]（由Lyubashevsky等2010年提出）兩個困難問題分別是SIS 和LWE 難題在環(huán)上的改進(jìn)版本，在相同的安全程度下，基于RSIS 和RLWE 難題的密碼方案比基于SIS 和LWE 難題的密碼方案所需的密鑰長度更短，計算速度更快。

為解決格上可鏈接環(huán)簽名方案的密鑰尺寸過長，效率較低問題，本文基于RLWE 難題，依據(jù)文獻(xiàn)[14]的技術(shù)路線，重新構(gòu)造一個格上可鏈接環(huán)簽名方案并提出一個應(yīng)用場景——簡易的數(shù)字貨幣模型。與文獻(xiàn)[15]不同的是，文獻(xiàn)[14]首先構(gòu)造一個理想格上的同態(tài)承諾方案，然后結(jié)合∑-協(xié)議、Fiat-Shamir轉(zhuǎn)化方法來構(gòu)造可鏈接環(huán)簽名，而本文是首先構(gòu)造一個基于RLWE 難題的多項(xiàng)式環(huán)上的同態(tài)承諾方案，然后結(jié)合∑-協(xié)議、Fiat-Shamir 轉(zhuǎn)化方法來構(gòu)造可鏈接環(huán)簽名。與以往格上可鏈接環(huán)簽名方案相比，由于所提方案基于RLWE 困難問題構(gòu)建，不但可規(guī)約至格上困難問題，抵抗量子計算機(jī)攻擊，且由于環(huán)元素取自小多項(xiàng)式，方案具有更短的密鑰尺寸和更高計算效率，且方案描述更簡單。

2 符號說明

為表述方便，對本文的符號進(jìn)行說明，如表1所示。

Table 1 Symbol description表1 符號說明

除了表1 中的符號，文中還用到O、、ω等符號，為常用計算復(fù)雜度符號。

3 預(yù)備知識

3.1 格

定義1（格）設(shè)b1,b2,…,bm是n維歐式空間?n上m個線性無關(guān)向量，格Λ定義為所有這些向量的整系數(shù)線性組合，即Λ=，其中向量組b1,b2,…,bm稱為格的一組基。

定義2（格上離散高斯分布）對任意σ＞0，定義以向量c為中心，σ為參數(shù)的格Λ上的離散高斯分布為DΛ,σ,c(y)=，其中y∈Λ，ρσ,c(y)=。

3.2 RLWE問題

Lyubashevsky等[20]于2010年提出RLWE問題，并指出多項(xiàng)式環(huán)理想格最壞情況下近似最短向量問題（approximate shortest vector problem，aSVP）可量子歸約至計算性RLWE 問題，而計算性RLWE 問題可一般規(guī)約至判定性RLWE（decision ring learning with errors，DRLWE）問題。

定義3（RLWE分布）對于安全參數(shù)n，令f(x)=xn+1 為n次首一不可約多項(xiàng)式，其中n是2的次冪；令q=1 mod 2n是一個足夠大的素數(shù)，設(shè)多項(xiàng)式環(huán)R=Z[x]/f(x)，Rq=R/qR。誤差分布χ為Rq上的高斯分布。設(shè)s∈Rq為秘密值，隨機(jī)均勻選取a←Rq，從高斯分布隨機(jī)選取e←χ，計算b=a?s+e，輸出(a,b)，由(a,b)所構(gòu)成的新分布定義為As,χ，而Rq×Rq上的均勻分布定義為U。

定義4（計算性RLWE 問題假設(shè)）從As,χ分布中取一組互相獨(dú)立的變量(a,b=a?s+e)，求解其中包含的值s，即給定a、b恢復(fù)多項(xiàng)式s在計算上是不可行的。

定義5（判定性RLWE 問題）由(a,b=a?s+e)產(chǎn)生的分布As,χ與Rq×Rq上的均勻分布U是計算不可區(qū)分的，即判定參數(shù)(a,b)是取自分布As,χ還是取自均勻分布U的概率是可忽略的。

定義6（β有界分布）如果一個分布χ滿足Pre←χ[||e||∞＜β]≤1-negl(n)，則稱其為β有界分布。

3.3 安全模型

本節(jié)給出安全模型及相關(guān)的安全定義。

3.3.1 可鏈接的環(huán)簽名

一個可鏈接的環(huán)簽名方案[7，21]由5 個概率多項(xiàng)式算法(Setup,KGen,Sign,Vfy,Link)組成。

（1）Setup(1n)：輸入安全參數(shù)n，輸出公共參數(shù)pp。

（2）KGen(pp)：輸入安全參數(shù)pp，生成用戶驗(yàn)證密鑰vk和簽名密鑰sk。

（3）Sign(ski,U,μ)：輸入環(huán)U，簽名者的私鑰ski，消息μ，該算法輸出環(huán)U對消息μ的簽名σ。

（4）Vfy(μ,U,σ)：輸入環(huán)U，消息μ及環(huán)簽名σ，接受輸出1；否則，輸出0。

（5）Link(pp,σ,σ′)：輸入公共參數(shù)pp，兩個環(huán)簽名σ、σ′，該算法用于驗(yàn)證兩個環(huán)簽名σ、σ′是否為同一個簽名者產(chǎn)生。如果為同一簽名者產(chǎn)生，則輸出1；否則，輸出0。

3.3.2 可鏈接環(huán)簽名安全模型

下面分別給出匿名性、不可偽造性定義：

定義7（匿名性）如果消息μ在環(huán)U和密鑰下的簽名形式上與消息μ在環(huán)U和密鑰下的簽名完全相同，則可鏈接環(huán)簽名方案(Setup,KGen,Sign,Vfy,Link)具有匿名性。正式地，要求任意對手A：

其中，A選擇i0、i1，由密鑰預(yù)言KGen(pp)生成并且。

定義8（不可偽造性）可鏈接環(huán)簽名方案(Setup,KGen,Sign,Vfy,Link)是不可偽造的，如果攻擊者A只知道公鑰和消息簽名對的情況下，對未詢問的消息偽造環(huán)簽名是不可行的，形式上對于所有概率多項(xiàng)式時間的攻擊者A：

（1）第i個查詢中VKGen隨機(jī)選取ri，運(yùn)行(vki,ski)←KGen(pp,ri)，返回vki；

（2）若(vki,ski)由KGen(pp,ri)生成且vki∈U，則Sign(i,μ,U)返回；

（3）A輸出環(huán)簽名(μ′,U′,σ′)，使得Sign沒有被(μ′,U′,*)詢問，并且U中僅包含由VKGen生成的密鑰vki。

4 基于RLWE難題的可鏈接環(huán)簽名方案

4.1 基于RLWE難題的同態(tài)承諾方案

對于RLWE難題，即從As,χ分布中取一組互相獨(dú)立的變量(a,b=a?s+e)，求解其中包含的值s，即給定a、b恢復(fù)多項(xiàng)式s在計算上是不可行的，如果把s看作被承諾消息，e看作隨機(jī)數(shù)，這樣則構(gòu)造出一個基于RLWE難題的同態(tài)承諾方案[22]。具體地說，基于RLWE難題的同態(tài)承諾方案包括以下兩個算法：

參數(shù)建立算法（KGen）：輸入安全參數(shù)n，令Rq=Zq[x]/＜xn+1＞，其中q是一個足夠大的公共素數(shù)，n是2 的次冪。隨機(jī)選取元素a←Rq，設(shè)置消息空間為M=Rq，隨機(jī)數(shù)空間R=Rq，生成Rq上的高斯分布χ，承諾空間為C=Rq，產(chǎn)生承諾密鑰ck={a,n,q}。

承諾算法（Com）：輸入一個待承諾消息s∈M，隨機(jī)選取小的錯誤向量e∈R，e服從χ分布且||e||∞≤β，β是一個正整數(shù)，計算承諾c=a?s+e∈Rq。

定理1（所提承諾方案滿足隱藏性）

證明由計算性RLWE 問題可知，對于給定若干組獨(dú)立的(a,b=a?s+e)，計算出s是不可行的（具體安全證明參考文獻(xiàn)[20]），因此所提承諾方案的隱藏性是顯而易見的，即給定承諾值c，想計算出被承諾消息s，在計算上是不可行的。 □

定理2（所提承諾方案滿足綁定性）

證明令s=ω(lbn)，β＜q/2d（d=φ(n)為歐拉函數(shù)），所提方案滿足綁定性。假設(shè)對于不同的消息s0、s1，可得到同一承諾值c，即對于c0=Com(s0;e0)，c1=Com(s1;e1)，有c0=c1。由于每個ei=c-asi(i=0,1)的無窮范數(shù)至多為β，因此對于e0-e1=a(s1-s0)無窮范數(shù)有||e0-e1||∞≤||e0||∞+||e1||∞＜2β。由于a是從Rq中均勻隨機(jī)選取的多項(xiàng)式，根據(jù)文獻(xiàn)[23]（引理21），可以把多項(xiàng)式環(huán)a的系數(shù)a看作是整數(shù)矩陣A中的一個列向量，對于任意的非零向量x∈，則存在很大的概率選擇向量a，有||ax||∞≥2β，這與||e0-e1||∞＜2β矛盾，因此本文承諾方案滿足綁定性。 □

定理3（所提承諾方案滿足同態(tài)性）

證明假設(shè)s0,s1∈M，e0,e1∈R，有以下等式：

故所提承諾方案滿足多項(xiàng)式環(huán)上的加法同態(tài)性?！?/p>

4.2 基于RLWE承諾的可鏈接環(huán)簽名方案

本文基于RLWE承諾方案，依據(jù)文獻(xiàn)[14]的技術(shù)路線，重新構(gòu)造一個格上可鏈接環(huán)簽名方案。與文獻(xiàn)[14]不同的是，本文是基于4.1 節(jié)的RLWE 同態(tài)承諾方案，并結(jié)合∑-協(xié)議、Fiat-Shamir轉(zhuǎn)化方法來構(gòu)造可鏈接環(huán)簽名，而文獻(xiàn)[14]是基于理想格上的同態(tài)承諾方案，結(jié)合∑-協(xié)議、Fiat-Shamir[24]轉(zhuǎn)化方法來構(gòu)造可鏈接環(huán)簽名。

基于RLWE 承諾的可鏈接環(huán)簽名（linkable ring scheme based on RLWE，R2LRS）包括五個算法(Setup,KGen,Sign,Vfy,Link)，具體描述如下：

Setup(1n,N)：輸入安全參數(shù)n，環(huán)成員個數(shù)N，調(diào)用4.1 節(jié)同態(tài)承諾方案的KGen算法，產(chǎn)生承諾密鑰ck={a,n,q}，消息空間為M=Rq，隨機(jī)數(shù)空間R=Rq和承諾空間為C=Rq，選擇一個散列函數(shù)H:{0,1}*→{-1,0,1}n，最終輸出pp=(n,q,H,a,N)。

KGen(pp)：對于第? 個用戶，隨機(jī)選取s←Rq且隨機(jī)抽樣一個差錯e←χ，計算c?=as+e?，令第? 個用戶的驗(yàn)證公鑰vk?=c?，簽名私鑰sk?=e?。

Sign(pp,e?,μ,U)：設(shè)U=(c0,c1,…,cN-1)是環(huán)成員公鑰的集合，在輸入消息μ時，第? 個用戶代表U生成的簽名如下。

（1）計算I?=ae?；

（2）對于j∈{1,2,…,n}，其中n=，隨機(jī)選擇rj,uj,yj,tj,ρk←Rq。

計算：

土老帽：“哈哈哈！看大家說得如此熱鬧，我也忍不住看了一下，覺得有些感慨，在手機(jī)照相流行的今天，除了全家福、大合照、結(jié)婚照一類的有特殊意義的照片會沖印出來，大家現(xiàn)在很少會把照片洗出來，放在相冊里留待翻看。想想以前爸媽幫我們拍照，再去照相館精心選出來，那種期待的心情，之后回想起當(dāng)時的場景，感受到親人的陪伴，生活的有趣，與現(xiàn)在拍照一秒鐘，精修美顏一小時的心情，截然不同了。拍照其實(shí)是次要的，我們更需要去關(guān)注的是身邊的人，更需要去感受和發(fā)現(xiàn)的是身邊的趣和美。這才是生活啊?！?/p>

（3）對于j∈{1,2,…,n}，計算：

①fj=x?j+uj

令S2=，公開σ={S1,S2,zw,I?,U}作為第? 個用戶對消息μ的環(huán)簽名。

Vfy(pp,μ,U,σ)：

（2）對應(yīng)j={1,2,…,n}，判斷以下是否成立：

③xnI?+

如果其中任何一個不成立，輸出0 并中止；否則輸出1。

Link(pp,σ,σ′)：對于兩個簽名σ=(…,I,U)和σ′=(…,I′,U′)，如果I=I′，返回1（可鏈接）則是同一個簽名者產(chǎn)生；否者返回0（不可鏈接）。

5 安全性與效率分析

5.1 安全性分析

下面將對方案的安全性進(jìn)行分析。

正確性：假設(shè)一個由Sign算法產(chǎn)生的環(huán)U關(guān)于消息μ的簽名為σ={S1,S2,zw,I?,U}，其中，則必有∈Cck，f1,…,zw∈Rq，且：

即Vfy算法中的等式①成立。

即Vfy算法中的等式②成立。

即Vfy算法中的等式③成立。

當(dāng)s=0 時，，即Vfy

算法中的等式④成立。

可鏈接性：關(guān)于本文所提可鏈接環(huán)簽名方案的可鏈接性由以下定理刻畫。

定理4假設(shè)使用N個簽名密鑰SK={e0,e1,…,eN-1}產(chǎn)生N+1 個簽名，這些N+1 個簽名中有兩個簽名由同一簽名者產(chǎn)生，其余N-1 個簽名均分別由其他簽名者產(chǎn)生，則同一簽名者產(chǎn)生的兩個簽名可通過鏈接算法，其他簽名均不能通過鏈接算法。

證明假設(shè)敵手可以產(chǎn)生N+1個有效的簽名σi=，使得Ii是兩兩不同的，其中i∈{0,1,…,N}。因?yàn)閨SK|=N（|SK|表示簽名密鑰集合中元素的個數(shù)），所以至少存在一個Ii不屬于集合{aej:ej∈SK}。為了不失一般性，對于π∈{0,1,…,N}，假設(shè)這種情況在σπ上發(fā)生，由于σπ是一個有效的簽名，從驗(yàn)證等式有：

定理5假設(shè)承諾方案滿足隱藏性，則本文提出的環(huán)簽名方案具有匿名性。

證明首先假設(shè)攻擊者A得到簽名σ，從簽名本身σ和消息μ∈Rq，攻擊者不能識別簽名者身份。由于任何一個環(huán)成員都具有生成簽名的能力，因此從具有n個成員的環(huán)中識別實(shí)際簽名者的概率不超過1/n。

而對于本文的承諾方案c=ais+ei具有隱藏性，不會泄露被承諾的消息s。由于s、e是在各自的空間均勻隨機(jī)選取，則計算得到承諾c的分布是偽隨機(jī)的。另一方面由∑-協(xié)議的見證不可區(qū)分性（文獻(xiàn)[15]定義8），保證了不可能區(qū)分使用哪個密鑰來生成環(huán)簽名。因此可以得出承諾方案具有隱藏性，環(huán)簽名方案滿足匿名性。 □

定理6假設(shè)所提承諾方案滿足隱藏性和計算綁定性，則本文環(huán)簽名方案是不可偽造的。

證明考慮一個多項(xiàng)式時間攻擊者A，將散列函數(shù)H視為預(yù)言機(jī)，對VKGen、Sign和隨機(jī)預(yù)言至多為qV(n)、qS(n)和qH(n)次查詢，并且對于無窮多個n∈N 具有至少1/p(n)的概率來攻破正多項(xiàng)式p的不可偽造性。將證明它可以用來構(gòu)造一個多項(xiàng)式時間攻擊，該攻擊在極多的λ∈N中以約1/2qV(λ)p(λ)的機(jī)會破壞承諾方案的綁定屬性。

當(dāng)A查詢VKGen時，按照環(huán)簽名方案運(yùn)行，在第j個查詢中返回vkj。如果A查詢Sign(j,μ,U)，隨機(jī)選擇x←{0,1}n并使用特殊的誠實(shí)驗(yàn)證者零知識模擬器（文獻(xiàn)[15]，定義7）來模擬證明{S1,S2,zw,I?,U}。然后通過隨機(jī)預(yù)言H(?)計算H(pp,μ,U,S1,I?)=x，如果H(pp,μ,U,S1,I?)之前已經(jīng)查詢過，在這種情況下中止。

最后，A嘗試在環(huán)中創(chuàng)建偽造的環(huán)簽名，其中簽名不是來自簽名預(yù)言，即(μ′,U′,*)未被詢問過。如果A無法創(chuàng)建偽造，將會停止。否則，使用來自用于獲取挑戰(zhàn)值x(0)的隨機(jī)預(yù)言查詢H(pp,μ,U,S1,I?)的環(huán)U在μ上獲得成功的偽造環(huán)簽名σ={S1,S2,zw,I?,U}?，F(xiàn)在將攻擊者倒回到進(jìn)行偽造簽名使用的查詢H(pp,μ,U,S1,I?)的位置，并隨機(jī)回答預(yù)言查詢，直到它使用相同的查詢生成n個額外的帶有挑戰(zhàn)x(1),x(2),…,x(n)的偽造環(huán)簽名。如上所述，在每次倒回中，如果對簽名的模擬導(dǎo)致對預(yù)言查詢的重用，則中止。此外，如果倒回次數(shù)超過2p(λ)n，則停止。

如果倒回后的攻擊者對總共n+1 個不同的挑戰(zhàn)給出了答案，現(xiàn)在可以使用（n+1）-特殊的穩(wěn)健性（文獻(xiàn)[15]定理3）來打破承諾方案的約束屬性或者打開某個vki=Com(0;ri)的(0;ri)。概率為1/qv時，有vki=vkj，這與承諾方案的綁定屬性相矛盾?？傊瑢τ跓o窮多的λ∈N，攻擊有接近或高于1/2qV(λ)p(λ)的機(jī)會打破承諾方案的綁定性。因此承諾方案滿足隱藏性和計算綁定性，則所提環(huán)簽名方案是不可偽造的。 □

5.2 效率分析

本節(jié)將本文方案與基于格的環(huán)簽名方案文獻(xiàn)[11]、文獻(xiàn)[14]在以下幾方面進(jìn)行比較。

表2中假設(shè)簽名環(huán)中的成員個數(shù)為l（1＜l≤N，N為環(huán)的最大尺寸），n為輸入的安全參數(shù)，q是大素數(shù)。文獻(xiàn)[11]中m的取值范圍為m≥5nlbq，文獻(xiàn)[14]中m的范圍為m=Θ(lbn)；在比較簽名和驗(yàn)證代時，用?表示計算復(fù)雜度，主要考慮耗時較長的矩陣乘法和多項(xiàng)式乘法運(yùn)算，忽略hash 函數(shù)等耗時較少的運(yùn)算。具體比較結(jié)果如表2所示。

Table 2 Efficiency analysis and comparison表2 效率分析對比

在公私鑰尺寸方面，文獻(xiàn)[11]采用的是GPV08陷門函數(shù)生成的小基作為私鑰，文獻(xiàn)[14]則隨機(jī)選取矩陣Xi∈Dm×m作為私鑰，而本文方案采用小整數(shù)多項(xiàng)式作為私鑰，并且系數(shù)范圍較小，而對于公鑰，文獻(xiàn)[11]通過GPV08 格點(diǎn)篩選算法生成公鑰，文獻(xiàn)[14]和本文方案分別通過矩陣和小多項(xiàng)式乘法得到公鑰，表2顯示本文公私鑰尺寸小于上述兩個方案。

在簽名長度方面，文獻(xiàn)[11]中m的取值范圍m≥5nlbq，因此n(5l+10)lb2q＞n(10+l)lbq=m(l+2)lbq≥5n(l+2)lb2q，顯然文獻(xiàn)[11]的簽名長度大于本文方案簽名長度；而文獻(xiàn)[14]中m一般情況下都是大于1的，因而文獻(xiàn)[14]簽名長度也大于本文方案的簽名長度。

在簽名運(yùn)算代價方面，文獻(xiàn)[11]采用陷門函數(shù)、格基生成算法，涉及計算代價較高的矩陣求逆操作，而本文方案沒有涉及陷門函數(shù)，因此文獻(xiàn)[11]簽名效率低于本文方案。

對于Rq上的一個元素u(x)=u0+u1x+…+un-1xn-1，可以將其寫成向量形式u=(u0,u1,…,un-1)，向量u維數(shù)為n，且每個分量項(xiàng)都是模q得到。由于本文方案中私鑰是在Rq上隨機(jī)選取的n維多項(xiàng)式（n維向量），因此私鑰長度為nlbq，而公鑰也是n維向量，公鑰長度也為nlbq。此外，環(huán)Rq中2 個元素相乘，相當(dāng)于并行進(jìn)行了n次向量內(nèi)積。涉及到多項(xiàng)式環(huán)乘法運(yùn)算可以通過快速傅里葉變換來實(shí)現(xiàn)，這也會很大程度上提高方案的效率。綜合比較，本文方案效率優(yōu)于文獻(xiàn)[11，14]，具有更低的存儲空間和更高的計算效率。

6 應(yīng)用場景——簡易的數(shù)字貨幣模型

本章基于RLWE 難題的可鏈接環(huán)簽名（R2LRS）提出一個新的數(shù)字貨幣模型。采用文獻(xiàn)[25]提出一次性目的地址技術(shù)，并且依據(jù)文獻(xiàn)[14]的路線，重新構(gòu)造一個基于R2LRS 的數(shù)字貨幣模型。該模型有4個算法，分別為系統(tǒng)建立、用戶密鑰生成、目的密鑰生成、目的密鑰恢復(fù)（其中目的密鑰也稱為一次性目的地址）。

系統(tǒng)建立：輸入安全參數(shù)，運(yùn)行R2LRS和公鑰加密算法（文獻(xiàn)[20]）進(jìn)行初始化，生成整個模型的全部參數(shù)PP。

用戶密鑰生成：此算法產(chǎn)生兩對公私鑰(epk,esk)和(c,e)。

目的密鑰生成：發(fā)送者選擇一個隨機(jī)數(shù)ep←χ并利用接收者密鑰，來產(chǎn)生一次性目的地址cd=cp+c。除了接收者外，其他任何人無法恢復(fù)出完整的簽名密鑰。接著選擇對稱加密算法Enc和對稱密鑰k，首先用第一步中的公鑰加密算法加密對稱密鑰k，然后利用對稱加密算法加密hash(epk)||ep。

目的密鑰恢復(fù)：對于接收者，首先利用私鑰解密出對稱密鑰k，隨后利用對稱密鑰k解密出hash(epk||ep)，進(jìn)而提取出ep，計算，比較=cd，則說明cd是有效目的地址，ed是cd對應(yīng)的有效簽名密鑰。

對于用戶A、B，假設(shè)A把錢轉(zhuǎn)給B，首先由系統(tǒng)給雙方產(chǎn)生密鑰對，A利用B的公鑰產(chǎn)生一次性目的地址，然后產(chǎn)生公鑰加密信息Enc(k)以及對稱加密信息hash(epk)||ep，A另外收集其他N-1 個一次性地址，鏈接密鑰，簽名密鑰用來生成可鏈接環(huán)簽名，最后A輸入金額、一次性目的地址、加密信息、環(huán)簽名等信息進(jìn)行哈希運(yùn)算，最后A廣播此信息。B檢查接收到的交易，提取一次性目的地址，對加密信息進(jìn)行相應(yīng)的解密，利用目的密鑰恢復(fù)算法，如果此交易是發(fā)送給B，則B接受該交易，提取對應(yīng)的簽名密鑰ed，把cd、ed放入錢包，B隨后可以花費(fèi)cd地址的錢。

7 結(jié)束語

隨著對抗量子攻擊的密碼方案關(guān)注度的提高，基于格的簽名體制也逐漸成為研究熱點(diǎn)。本文主要貢獻(xiàn)是首先構(gòu)造一個基于RLWE難題的多項(xiàng)式環(huán)上的同態(tài)承諾方案，然后結(jié)合∑-協(xié)議、Fiat-Shamir轉(zhuǎn)化方法來構(gòu)造可鏈接環(huán)簽名，并且在隨機(jī)預(yù)言模型下基于計算性RLWE 問題證明本文方案的安全性，同時給出詳細(xì)的效率分析，最后基于本文方案提出了一個應(yīng)用場景——簡易的數(shù)字貨幣模型。接下來計劃對本文方案進(jìn)行實(shí)驗(yàn)分析，對應(yīng)用場景作進(jìn)一步的研究。