利用環上容錯學習問題構造可鏈接環簽名方案*

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

河南理工大學 計算機科學與技術學院，河南 焦作454000

1 引言

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

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

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

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

2 符號說明

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

Table 1 Symbol description表1 符號說明

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

3 預備知識

3.1 格

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

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

3.2 RLWE問題

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

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

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

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

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

3.3 安全模型

本節給出安全模型及相關的安全定義。

3.3.1 可鏈接的環簽名

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

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

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

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

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

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

3.3.2 可鏈接環簽名安全模型

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

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

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

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

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

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

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

4 基于RLWE難題的可鏈接環簽名方案

4.1 基于RLWE難題的同態承諾方案

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

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

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

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

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

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

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

定理3（所提承諾方案滿足同態性）

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

故所提承諾方案滿足多項式環上的加法同態性。□

4.2 基于RLWE承諾的可鏈接環簽名方案

本文基于RLWE承諾方案，依據文獻[14]的技術路線，重新構造一個格上可鏈接環簽名方案。與文獻[14]不同的是，本文是基于4.1 節的RLWE 同態承諾方案，并結合∑-協議、Fiat-Shamir轉化方法來構造可鏈接環簽名，而文獻[14]是基于理想格上的同態承諾方案，結合∑-協議、Fiat-Shamir[24]轉化方法來構造可鏈接環簽名。

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

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

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

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

（1）計算I?=ae?；

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

計算：

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

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

①fj=x?j+uj

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

Vfy(pp,μ,U,σ)：

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

③xnI?+

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

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

5 安全性與效率分析

5.1 安全性分析

下面將對方案的安全性進行分析。

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

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

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

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

當s=0 時，，即Vfy

算法中的等式④成立。

可鏈接性：關于本文所提可鏈接環簽名方案的可鏈接性由以下定理刻畫。

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

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

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

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

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

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

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

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

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

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

5.2 效率分析

本節將本文方案與基于格的環簽名方案文獻[11]、文獻[14]在以下幾方面進行比較。

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

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

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

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

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

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

6 應用場景——簡易的數字貨幣模型

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

系統建立：輸入安全參數，運行R2LRS和公鑰加密算法（文獻[20]）進行初始化，生成整個模型的全部參數PP。

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

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

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

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

7 結束語

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