格上的簡短可鏈接環簽名

收稿日期：2022-02-15；修回日期：2022-04-02

基金項目：國家自然科學基金資助項目（U1904119）；河南省科技攻關項目（222102210079，212102310264）

作者簡介：王杰昌（1985-），男，河南伊川人，講師，碩士，主要研究方向為信息安全、區塊鏈；張平（1976-），男，黑龍江牡丹江人，副教授，碩導，博士，主要研究方向為信息安全與密碼學；李杰（1978-），男，河南禹州人，副教授，碩士，主要研究方向為信息安全；常琳林（1983-），女，河南項城人，講師，碩士，主要研究方向為信息安全；段瑩（1983-），女（通信作者），河南偃師人，副教授，博士，主要研究方向為工業物聯網安全（able0607@163.com）.

摘 要：可鏈接環簽名可防止區塊鏈中的雙花攻擊，基于格的簽名可抵抗量子攻擊，但已有格基可鏈接環簽名的大小隨環成員的增多而增大。針對該問題，提出了一種格上的簡短可鏈接環簽名方案。該方案用隊列實現了向量數制的特殊轉換，利用格上的累加器對環成員的公鑰進行累加，使得簽名大小不會隨環成員的增多而增大；利用拒絕采樣定理，構造出格上的知識證明簽名，在防止簽名私鑰泄露的同時，提高了計算效率。在隨機預言機模型下，證明了方案具有不可偽造性、匿名性、可鏈接性。性能分析與實驗評估表明，所提方案節省了時間開銷和存儲開銷，且隨著環成員的增多簽名大小固定不變。

關鍵詞：格； 知識證明簽名； 累加器； 簡短可鏈接環簽名

中圖分類號：TP309.2"" 文獻標志碼：A

文章編號：1001-3695（2022）09-044-2843-07

doi：10.19734/j.issn.1001-3695.2022.02.0057

Lattice-based short linkable ring signatures

Wang Jiechang1， Zhang Ping2， Li Jie1， Chang Linlin1， Duan Ying3

（1.Sports Big Data Center， College of Physical Education， Zhengzhou University， Zhengzhou 450000， China; 2.School of Mathematics amp; Statistics， Henan University of Science amp; Technology， Luoyang Henan 471023， China; 3. School of Intelligent Engineering， Zhengzhou University of Aeronautics， Zhengzhou 450003， China）

Abstract：Linkable ring signatures could avoid double-spending attacks in the blockchain. Lattice-based signatures were quantum-resistant. However， as the number of ring members increased， the size of existing lattice-based linkable ring signatures increased. To solve this problem， this paper proposed a lattice-based linkable ring signatures scheme. This scheme used queues to implement a special conversion of vector number system， and used lattice-based accumulators to accumulate the public keys of ring members， so that the signature size didn’t increase with the number of ring members. And using the rejection sampling theorem， this scheme constructed signatures based on proofs of knowledge on lattices， prevented the signature private key from leaking， and improved the computational efficiency. In the random oracle model， the scheme was proved to be unforgeable， anonymous and linkable. Performance analysis and experimental evaluation show that， this scheme saves time and storage， and the signature size is constant with the increase of ring members.

Key words：lattice; signatures based on proofs of knowledge; accumulators; short linkable ring signatures

0 引言

區塊鏈［1］具有去中心化、開放性、不可竄改性、自治性、匿名性等特點，目前越來越受到業界的推崇。然而區塊鏈技術在安全上還有很多不足，如比特幣系統中的匿名性是通過假名實現的，并不是真正的匿名性［2］。針對該問題，很多學者提出改善區塊鏈系統匿名性的方案，環簽名［3］便是主流方案之一。在環簽名機制下，簽名者自發選擇多個用戶組成環，利用自己的公私鑰對及環成員的公鑰對消息進行簽名，驗證者只知道簽名出自環中某一個成員，但不能確定簽名者真實身份［4］。

對于區塊鏈電子貨幣系統的雙花攻擊與區塊鏈電子選舉系統的重復投票問題，可鏈接環簽名［5］的可鏈接性確保簽名者不能重復簽名，能有效解決區塊鏈的這些問題。文獻［6］利用可鏈接環簽名設計了基于智能合約的電子投票系統，確保了投票結果的可信度，解決了投票過程中的安全問題。但是隨著環成員的增多，單個可鏈接環簽名的大小也在增大。簡短可鏈接環簽名（short linkable ring signatures，SLRS）［7，8］先使用累加器對公鑰環進行累加計算，然后再進行簽名，不僅保留了可鏈接環簽名的一些特性，而且隨著環成員的增多，單個簽名的大小保持不變［9］。文獻［9］利用消息編碼、Paillier同態加密、簡短可鏈接環簽名［7，8］，提出了一個獨立平臺的安全的區塊鏈投票系統。然而上述方案的密碼體制均基于傳統數學難題，隨著量子計算技術的發展，它們的安全性逐漸降低。

基于格的密碼體制具有抗量子攻擊、運算簡單、可并行化、抗量子攻擊、存在最壞情況下的隨機實例和較高的漸進效率等優點，因而成為后量子時代的研究熱點［10］。文獻［11］ 提出了基于格的一次性可鏈接環簽名L2RS， 并將其應用至區塊鏈上的環可信交易（Lattice RingCT v1.0）。在此基礎上，文獻［12］構造了可鏈接環簽名MIMO.L2RS，進一步提出升級版應用協議——Lattice RingCT v2.0，在交易中支持多輸入及多輸出電子錢包。文獻［13］提出了切合實際的格基一次性可鏈接環簽名方案，其簡單有效、實用性強。針對門羅幣的安全問題，文獻［14］提出了支持匿名地址［15］的格基可鏈接環簽名。文獻［16］利用環上容錯學習問題提出了一個可鏈接環簽名方案，其密鑰尺寸較短、效率較高。文獻［10］利用原像抽樣和拒絕采樣算法構造了一個格上基于身份的可鏈接環簽名方案，提升了用戶密鑰生成和簽名驗證的效率。文獻［17］利用格密碼、消息塊共享技術、填充排列技術，提出一種基于格的可鏈接門限環簽名方案，并將其應用至電子投票協議。然而隨著環成員個數的增大，這些方案的簽名長度也在增大。

為解決上述問題，本文提出格上的簡短可鏈接環簽名方案，主要貢獻如下：

a）鑒于隊列先進先出的特點［18］，利用其實現了向量數制的特殊轉換；

b）將Camenish等人［19］提出的知識證明簽名（signatures based on proofs of knowledge，SPK）推廣至格上，構造出新的SPK；

c）根據文獻［7，8］定義的簡短可鏈接環簽名算法，結合格上的累加器［20］，利用拒絕采樣定理［21］，構造出格上的簡短可鏈接環簽名方案（lattice-based short linkable ring signatures，LSLRS），隨著環成員的增加，簽名大小保持不變，同時提高了計算效率。

1 預備知識

1.1 基礎符號

對于b∈{0，1}，用表示1－b∈{0，1}，矩陣A∈Euclid Math TwoZApk×i和B∈Euclid Math TwoZApk×j的拼接表示為［A|B］∈Euclid Math TwoZApk×（i+j），用x←sS表示從有限集S中均勻隨機選擇x，用x←sD表示按照分布D選擇x。對于正整數n、q、k、m，n為安全參數，q=（n），k=「log q，m=2nk。對于矩陣G=1 2 4 … 2k－11 2 4 … 2k－1…1 2 4 … 2k－1∈Euclid Math TwoZApn×nkq，向量v=（v0，…，vi，…，vn－1）T∈Euclid Math TwoZApnq，有v=G·bin（v），其中bin（v）∈{0，1}nk為向量v的二進制表示。

1.2 格上的困難問題

定義1 SIVPγ問題。給定秩為n的格L=L（B），找n的線性無關的向量v1，…，vn∈L，使得對任意的1≤i≤n，‖vi‖≤γ×λn（L），這里γ≥1為逼近因子，λn（L）為格L的逐次最小長度。

定義2 SIS∞n，m，q，β問題［20］。給定均勻隨機選擇的矩陣A∈Euclid Math TwoZApn×mq，找到一個非零向量x∈Euclid Math TwoZApm滿足條件‖x‖∞≤β且A·x=0 mod q。

如果m，β=poly（n），并且qgt;β×（n），那么SIS∞n，m，q，β問題至少和最壞情況下的SIVPγ（γ=β×（nm））問題一樣難解。特別地，當β=1，q=（n），m=2n「log q，SIS∞n，m，q，1問題至少和SIVP（n）問題一樣難解［20］。

1.3 格上的累加器

定義3 函數族Euclid Math OneHAp：{0，1}nk×{0，1}nk→{0，1}nk被定義為Euclid Math OneHAp={HA|A∈Euclid Math TwoZApn×mq}，其中A=［A0|A1］，A0，A1∈Euclid Math TwoZApn×nkq，并且對于任何（u0，u1）∈{0，1}nk×{0，1}nk，有

HA（u0，u1）=bin（A0·u0+A1·u1mod q）∈{0，1}nk

注意HA（u0，u1）=uA0·u0+A1·u1=G·u mod q。

引理1 假設SIVP（n）問題是難解的，則定義3中的函數族Euclid Math OneHAp是抗碰撞的。

基于上面定義的格基哈希函數族Euclid Math OneHAp，構造一個默克爾樹，具有N=2l個葉子節點，l為一個正整數，下面為格上累加器［20］的算法：

a）TSetup（n）。抽樣A←sEuclid Math TwoZApn×mq，輸出pp=A。

b）TAccA（R）。R={d0∈{0，1}nk，…，dN－1∈{0，1}nk}，對每個j∈［0，N－1］，（j1，…，jl）∈{0，1}l為j的二進制表示，令dj=uj1，…，jl。深度為l=log N的默克爾樹，有N個葉子節點u0，0，…，0，…，u1，1，…，1，且有如下定義：

（a）在深度i∈{1，…，l}，對于所有的（b1，…，bi）∈{0，1}i，節點ub1，…，bi∈{0，1}nk被定義為HA（ub1，…，bi，0，ub1，…，bi，1）；

（b）在深度0，根節點u∈{0，1}nk被定義為HA（u0，u1）。

該算法輸出為累加值u。

c）TWitnessA（R，d）。如果dR，返回⊥；否則d=dj（某個j∈［0，N－1］，這個j的二進制表示（j1，…，jl）），輸出證據w被定義為

w=（（j1，…，jl），（uj1，…，jl－1，l，…，uj1，2，u1））∈{0，1}l×（{0，1}nk）l

其中：uj1，…，jl－1，l，…，uj1，2，u1可以通過TAccA（R）算法計算得出。

d）TVerifyA（u，d，w）。將給定的證據w寫成如下形式：

w=（（j1，…，jl），（wl，…，w1））∈{0，1}l×（{0，1}nk）l

按以下方式遞歸地計算vl，vl－1，…，v1，v0∈{0，1}nk：

vl=d

i∈{l－1，…，1，0}，vi=hA（vi+1，wi+1） 若ji+1=0hA（wi+1，vi+1）若ji+1=1

如果v0=u，返回1；否則返回0。

定理1 假設SIVP（n）問題是難解的，則格上的累加器是安全的，即對于所有的PPT敵手Euclid Math OneAAp：

Pr［pp←TSetup（n）;（R，d*，w*）←Euclid Math OneAAp（pp）：

d*R∧TVerifypp（TAccpp（R），d*，w*）=1］=negl（n）

1.4 知識證明簽名SPK

Camenisch等人[19]提出了基于知識證明的簽名，簡稱SPK。若證明者想向驗證者證明其知道離散對數{（x）：y=gx mod n}的知識，并用這個知識對消息μ進行簽名，可通過以下的協議來實現：

證明者：隨機選取r∈REuclid Math TwoZApn，計算c=H（μ‖y‖g‖gr）s=r－cx（mod n），其中H為抗碰撞單向哈希函數，然后將（c，s）傳送給驗證者。

驗證者：檢驗c=？H（μ‖y‖g‖gsyc），若等式成立，驗證者接受證明者的證明；否則拒絕。

此處稱（c，s）為證明者根據y關于g的離散對數對消息μ進行知識證明簽名，記為SPK{（x）：y=gxmod n}（μ）。

1.5 拒絕采樣定理

定理2 拒絕采樣定理［21］。集合V={v∈Euclid Math TwoZApm：‖v‖lt;T}為Euclid Math TwoZApm的一個子集，Euclid Math TwoRAp中某個元素s=ω（Tlog m），概率分布h：V→Euclid Math TwoRAp，則存在常數M=O（1），使得以下兩個算法的輸出分布統計距離在2－ω（log m）/M以內：

a）算法A。第一步v←sh，然后z←sDmv，s，最后以minDms（z）MDmv，s（z），1的概率輸出（z，v）。

b）算法F。第一步v←sh，然后z←sDms，最后以1/M的概率輸出（z，v）。

進一步，算法A有輸出的概率至少為（1－2－ω（log m））/M。

2 簽名定義及安全模型

2.1 簽名定義

格上的簡短可鏈接環簽名方案包括以下五個PPT算法：

a）LSetup（n）。輸入安全參數n，輸出公共參數pp，該參數對所有用戶是公開的。

b）LKgen（pp）。輸入公共參數pp，輸出公私鑰對（pk，sk） 。

c）LSignpp（sk，μ，R）。輸入簽名者的密鑰sk、待簽名消息μ以及環R=（pk0，…，pkN－1），輸出簽名σR（M），簽名包含可鏈接標簽I。其中（pk，sk）為LKgen（pp）生成的有效公私鑰對，且pk∈R。

d）LVerifypp（μ，R，σR（μ））。輸入消息μ在環R上的簽名σR（μ），若σR（μ）是有效的，本算法輸出1；否則輸出0。

e）LLink（σR（μ1），σR（μ2））。輸入簽名σR（μ1）、σR（μ2），若I1=I2，則輸出linked；否則輸出unlinked。

2.2 安全模型

2.2.1 不可偽造性

不可偽造性游戲如下：

a）初始化。系統運行LSetup得到公共參數，并將公共參數發送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp可以進行多項式次訪問隨機預言機。

c）偽造階段。敵手Euclid Math OneAAp輸出（μ*，R*，σ*），若滿足以下條件：

（a）敵手進行第j次公鑰詢問，公鑰預言機Euclid Math OnePApEuclid Math OneOAp生成公私鑰對（pkj，skj），將公鑰加入環中，并返回公鑰pkj；

（b）敵手輸入（j，μ，R）進行簽名詢問，若（pkj，skj）由Euclid Math OnePApEuclid Math OneOAp生成且pkj∈R，則簽名預言機Euclid Math OneSApEuclid Math OneOAp輸出與（j，μ，R）相對應的簽名σR（μ），否則輸出⊥；

（c）敵手輸入pkj詢問其對應的私鑰，私鑰預言機Euclid Math OneCApEuclid Math OneOAp返回skj；

（d）（·，μ*，R*）從未被敵手詢問過，環R*中的公鑰均為Euclid Math OnePApEuclid Math OneOAp生成，且其對應的私鑰均未被詢問過。

則敵手Euclid Math OneAAp贏得不可偽造性游戲，敵手贏得游戲的優勢定義為

AdvFA=Pr［pp←LSetup（1n）;（μ*，R*，σ*）←Euclid Math OneAApPO，SO，CO（pp）：

LVerifypp（μ*，R*，σ*）=1］

定義4 對于任意多項式時間敵手Euclid Math OneAAp， AdvFA=negl（n），則稱該簡短可鏈接環簽名是不可偽造的。

2.2.2 匿名性

匿名性游戲如下：

a）初始化。挑戰者Euclid Math OneBAp運行算法LSetup得到公共參數pp，并且運行算法LKgen生成公私鑰對（di，xi），將公鑰加入環中，然后將環R=（d0，…，dN－1）和公共參數pp發送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp可以進行多項式次訪問預言機。

c）挑戰階段。敵手Euclid Math OneAAp挑選待簽消息μ∈{0，1}*以及任意兩個公鑰di0，di1∈R進行簽名詢問，挑戰者隨機選擇b∈{0，1}并利用dib對應的私鑰xib，運行LSign對消息μ進行簽名，將生成的簽名σR（μ）返回給敵手Euclid Math OneAAp。

d）猜測階段。敵手Euclid Math OneAAp輸出b*作為對簽名者身份的猜測，若b*=b，則敵手獲勝。

敵手Euclid Math OneAAp在匿名性游戲中獲勝的優勢定義為

AdvAnoEuclid Math OneAAp=Pr［b*=b］－12

定義5 對任意多項式時間敵手Euclid Math OneAAp，AdvAnoEuclid Math OneAAp=negl（n），則稱該簽名方案是匿名的。

2.2.3 可鏈接性

可鏈接性游戲如下：

a）初始化。挑戰者Euclid Math OneBAp運行算法LSetup得到公共參數pp，并運行算法LKgen生成公私鑰對（di，xi），將公鑰加入環中，然后將環R=（d0，…，dN－1）和公共參數pp發送給敵手Euclid Math OneAAp。

b）詢問階段。敵手Euclid Math OneAAp可以進行多項式次訪問預言機。

c）偽造階段。敵手Euclid Math OneAAp給出兩簽名（μ1，R1，σR1（μ1））、（μ2，R2，σR2（μ2）），簽名σR1（μ1）、σR2（μ2）中分別包含相應的可鏈接標簽I1，I2若滿足以下條件：

（a）LVerifypp（μi，Ri，σRi（μi））=1，i∈{1，2}；

（b）LLink（σR1（μ1），σR2（μ2））=unlinked，即I1≠I2；

（c）敵手Euclid Math OneAAp未發起過（μ1，R1）、（μ2，R2）的簽名詢問；

（d）環R1、R2中任一用戶的公鑰均由挑戰者給出；

（e）敵手Euclid Math OneAAp發起私鑰詢問的次數少于兩次（敵手Euclid Math OneAAp至多擁有一個用戶的私鑰）。

則敵手Euclid Math OneAAp贏得可鏈接性游戲，敵手Euclid Math OneAAp贏得游戲的優勢定義為AdvLA=Pr［Euclid Math OneAApwins］。

定義6 對于任意多項式時間敵手Euclid Math OneAAp，AdvLA是可忽略的，則稱該簡短可鏈接環簽名是可鏈接的。

3 格上的簡短可鏈接環簽名

Camenisch等人［19］首先提出了基于知識證明的簽名，根據離散對數x這一知識對消息μ進行了知識證明簽名，即σ=SPK{（x）：y=gxmod n}（μ）。Tsang等人[7]使用了基于知識證明的簽名，根據知識（w，ys，x）對消息M進行知識證明簽名，即σ=SPK{（w，ys，x）：（ys，x）∈Euclid Math TwoRAp∧f（w，ys）=v∧=θd（x）}（M），并結合累加器，提出了簡短可鏈接環簽名。文獻［7，8］中的簡短可鏈接環簽名均是先使用累加器對環中公鑰進行累加，然后再進行基于知識證明的簽名。隨著環成員的增多，可鏈接環簽名大小隨之增大，而簡短可鏈接環簽名的大小保持不變，同時保留不可偽造性、匿名性、可鏈接性等優點［9］。但上述累加器、SPK及其構造的簡短可鏈接環簽名均基于傳統的數學難題，且目前僅有學者提出的格上的可鏈接環簽名方案［10，11］，還沒有格上的簡短可鏈接環簽名方案。因此本文根據簡短可鏈接環簽名［7，8］的構造，先利用格上的累加器［20］對環中公鑰進行累加，然后依據文獻［7，8，19］算法提出格上的SPK，最終構造出格上的簡短可鏈接環簽名LSLRS。

LSLRS方案中有N=2l個環成員，參數n、m、q、k在預備知識中已定義。LSLRS包含五個算法（LSetup，LKgen，LSignpp，LVerifypp，LLink），具體描述如下：

a）LSetup（n）。輸入安全參數n，從Euclid Math TwoZApn×mq中均勻隨機抽樣得到A，選取抗碰撞的單向哈希函數HA∈Euclid Math OneHAp：{0，1}nk×{0，1}nk→{0，1}nk，H1：Euclid Math TwoZApn×mq×{0，1}m→Euclid Math TwoZApq，H2：{0，1}l×（{0，1}nk）l→Euclid Math TwoZApq，H3：{0，1}*×Euclid Math TwoZApn×mq×Euclid Math TwoZApnq×{0，1}nk×Euclid Math TwoZApq→Euclid Math TwoZApq，輸出公共參數pp=（A，HA，H1，H2，H3）。

b）LKgen（pp）。輸入pp，從{0，1}m中均勻隨機選擇xi，i∈［0，N－1］，分別計算di=bin（A·xi mod q），di∈{0，1}nk，輸出公私鑰對（ski，pki）=（xi，di），i∈［0，N－1］。

c）LSignpp（sk，μ，R）。輸入環R=（d0，…，dN－1），di∈{0，1}nk，i∈［0，N－1］，簽名私鑰sk=x∈{0，1}m，其對應的公鑰為

pk=d=bin（A·x mod q）∈R（1）

按以下步驟生成消息μ∈{0，1}*的簽名σ：

（a）計算可鏈接標簽

I=H1（A，x）（2）

（b）運行算法TAccA（R），輸出環R中所有環成員公鑰的累加值

u=HA（u0，u1）∈{0，1}nk（3）

（c）運行算法TWitnessA（R，d）得到證據

w=（（j1，…，jl），（wl，…，w1））∈{0，1}l×（{0，1}nk）l（4）

（d）計算知識證明簽名

SPK{（w，d，x）：

w=（（j1，…，jl），（uj1，…，jl－1，l，…，uj1，2，u1））∧d=bin（A·x mod q）}（μ）（5）

將Camenisch等人的SPK推廣至格上，同時利用拒絕采樣定理，構造格上的知識證明簽名。

證明者（即簽名者）：按照分布Dms隨機選擇r∈{0，1}m，分別進行如下計算：

W=H2（w）（6）

c=bin（A·r mod q）（7）

z=H3（μ，A，G·d，c，W）（8）

k=r－z·x（mod q）（9）

然后將（W，c，z，k）傳送給驗證者，根據拒絕采樣定理，發送成功的概率為minDms（k）MDm－zx，s（k），1，如果發送失敗，則重新計算后再發送。

驗證者：檢驗

z=？H3（μ，A，z－1·G·c－z－1·A·k（mod q），c，W）（10）

若上式成立，驗證者接受證明；否則拒絕。（W，c，z，k）為證明者（即簽名者）根據知識（w，d，x）對消息μ進行的簽名，即

SPK{（w，d，x）：w=（（j1，…，jl），（uj1，…，jl－1，l，…，uj1，2，u1））∧

d=bin（A·x mod q）}（μ）=（W，c，z，k）（11）

（e）輸出格上的簡短可鏈接環簽名

σR（μ）=（u，I，SPK）=（u，I，W，c，z，k）（12）

d）LVerifypp（μ，R，σR（μ））。輸入簽名消息μ，環R=（d0，…，dN－1）以及簽名σR（μ）=（u，I，SPK）；從R中任意選取一個dj，j∈［0，N－1］，計算TAccA（R）→u′，驗證u=？u′，并驗證式（11）的有效性，若都驗證通過，則輸出1，否則輸出0。

e）LLink（σR（μ1），σR（μ2））。給定兩個簽名σR（μ1）、σR（μ2），提取它們的可鏈接標簽，若I1=I2，則輸出linked；否則輸出unlinked。

設v∈Euclid Math TwoZApnq，有v=（v0，v1，…，vn－1）T，vi∈Euclid Math TwoZApq，i∈［0，n－1］，bin（v）∈{0，1}nk為向量v的二進制表示。v=G·bin（v），十進制數vi應轉換為具有特殊寫法的二進制數（與正常的二進制數寫法順序相反，從最低位數開始寫起，且自上而下書寫，依次寫到最高位數而止），然后自上而下依次書寫v0，v1，…，vn－1所對應的特殊寫法二進制數，最終得到向量bin（v）。由于隊列具有先進先出的特點，這里可通過隊列實現v的數制轉換，其算法的具體實現過程如下所示。

輸入：十進制向量v。

輸出：bin（v）。

void coversion（int N）

{//對于任一十進制數，輸出其對應的二進制數

InitQueue（Q）;""" //初始化空隊列Q

while （log2N≥2）

{

EnQueue（Q，N%2）; /*調用函數EnQueue（），將N與2求余得到的二進制數加入隊列Q*/

N=N/2;

}

while （！QueueEmpty（Q）） //當隊列Q非空時，循環

{

DeQueue（Q，e）；""" /*調用函數DeQueue（），彈出隊列Q的隊頭元素e */

countlt;lt;e;

}

}

void main（）

{//將n維向量v轉換為其對應的二進制向量bin（v）

int v［n］;

for （i=0; ilt;n; i++）

coversion（int v［i］）;" /*調用函數coversionf（），將十進制數v［i］轉換為二進制數*/

}

4 安全性分析

4.1 正確性

格上累加器的正確性在文獻［20］中已進行了論證，這里主要論證知識簽名證明的正確性。

H3（μ，A，z－1·G·c－z－1·A·k（mod q），c，W）=

H3（μ，A，z－1·（G·bin（A·r mod q）－A·k（mod q）），c，W）=

H3（μ，A，z－1·（A·r－A·k（mod q）），c，W）=

H3（μ，A，A·z－1·（r－k）mod q，c，W）=

H3（μ，A，A·z－1·z·x mod q，c，W）=

H3（μ，A，A·x mod q，c，W）=

H3（μ，A，G·d，c，W）=z

4.2 不可偽造性

定理3 如果SIVP（n）問題是困難的，那么在隨機預言機模型下，格上的簡短可鏈接環簽名是不可偽造的。

證明 在隨機預言機模型下，假設敵手Euclid Math OneAAp以ε的優勢贏得不可偽造性游戲，那么一定存在模擬器Euclid Math OneBAp或者攻破格上累加器的安全性，或者以不可忽略的優勢解決一個SIS∞n，m，q，1問題實例。

為達到目的，Euclid Math OneBAp將公共參數（A，HA，H1，H2）發送給Euclid Math OneAAp，在游戲期間，Euclid Math OneBAp誠實地回答Euclid Math OneAAp的公鑰詢問，并將公鑰pk=bin（A·x mod q）返回給Euclid Math OneAAp。在每次公鑰詢問中，Euclid Math OneBAp秘密保留其選擇的私鑰sk=x∈{0，1}m。掌握所有的私鑰，Euclid Math OneBAp就能回答所有的私鑰詢問以及簽名詢問。

游戲結束時，Euclid Math OneAAp輸出通過驗證的（μ*，R*，σ*），并且Euclid Math OneAAp從未詢問過環R*成員的私鑰，同時也未對（·，μ*，R*）進行過簽名詢問。這里R*=（pki1，…，pki|R*|）為一組二進制向量（d0，…，d|R*|－1），σ*=（u*，I*，W*，c*，z*，k*），u*=TAccA（R*）。

設H3（ ）為隨機預言機，敵手Euclid Math OneAAp至多進行qH次哈希詢問，根據分叉引理［22］，Euclid Math OneAAp能以（1－e－1）εqH的概率輸出兩個有效的簽名（u*，I*，W*，c*，z*，k*）和（u*，I*，W*，c*，z*0，k*0），其中z*≠z*0。

根據簽名機制，模擬器Euclid Math OneBAp可得到方程組

k*=r*-z*·x*（b mod q）

k*0=r*-z*0·x*（b mod q）

兩式相減可計算出

x*=（z*0－z*）－1（k*－k*0）mod q

然后可計算出

d*=bin（A·x*mod q）

進一步根據算法TWitnessA（R*，d*）可得到w*。

最終Euclid Math OneBAp得以提取知識（w*，d*，x*），這里w*=（（j*1，…，j*l），（w*l，…，w*1）），而（j*1，…，j*l）∈{0，1}l是某個下標j*∈{0，…，|R*|－1}的二進制展開，同時滿足

G·d*=A·x*mod q

TVerifyA（u*，d*，w*）=1（13）

此時，分兩種情況討論：

a）d*R*=（d0，…，d|R*|－1），則上面的TVerifyA（u*，d*，w*）=1就意味著Euclid Math OneBAp可以用（d*，R*，u*）攻破格上累加器的安全性。

b）d*∈R*=（d0，…，d|R*|－1），所以d*=dj*=pkj*，提取的知識（dj*，x*）滿足

G·dj*=A·x*mod q（14）

回憶skj*為在某次公鑰詢問中模擬器Euclid Math OneBAp選擇的向量xj*∈{0，1}m，滿足

G·dj*=A·xj*mod q（15）

由于敵手Euclid Math OneAAp不能詢問用戶j*的私鑰，所以有1/2的概率xj*≠x*。式（14）和（15）兩式相減可得A·（xj*－x*）=0 mod q，進而可得到SIS∞n，m，q，1問題的一個有效解ω=xj*－x*∈{－1，0，1}m。

從以上兩種情況的討論可知，若敵手Euclid Math OneAAp偽造簽名成功，則模擬器Euclid Math OneBAp要么破壞格上累加器的安全性，要么解決一個SIS∞n，m，q，1問題實例。這顯然與SIVP（n）問題困難假設相矛盾，定理得證。

4.3 匿名性

定理4 本文方案具備匿名性。

證明 通過挑戰者Euclid Math OneBAp與敵手Euclid Math OneAAp間的匿名性游戲進行證明，Game0模擬Euclid Math OneBAp利用di0對應的私鑰xi0進行簽名，Game1模擬Euclid Math OneBAp利用di1對應的私鑰xi1進行簽名，若敵手Euclid Math OneAAp對兩個簽名的概率分布不可區分，那么本文方案滿足匿名性。

Game0：

a）Euclid Math OneBAp輸入安全參數n，從Euclid Math TwoZApn×mq中均勻隨機抽樣得到A，選取抗碰撞單向哈希函數：HA∈Euclid Math OneHAp，H1，H2，H3，輸出這些公共參數；然后從{0，1}m中均勻隨機選擇xi，i∈［0，N－1］，分別計算di=bin（A·xi mod q），di∈{0，1}nk，加入環R，保留私鑰xi，i∈［0，N－1］，輸出環R=（d0，…，dN－1）。

b）敵手Euclid Math OneAAp將待簽名消息μ∈{0，1}*、環R=（d0，…，dN－1）以及環中任意兩個公鑰di0，di1∈R發送給Euclid Math OneBAp；Euclid Math OneBAp選取b=0即選取di0對應的私鑰xi0進行簽名。

c）Euclid Math OneBAp運行算法LSignpp（xi0，μ，R），利用拒絕采樣定理，生成簽名σR（μ）=（u，I，W，c，z，k），并將其返回給敵手Euclid Math OneAAp。

d）敵手Euclid Math OneAAp收到簽名后給出對b的猜測。

Game1：

Game1與Game0的不同在于Euclid Math OneBAp選取b=1，即選取di1對應的私鑰xi1，運行簽名算法LSignpp（xi1，μ，R），利用拒絕采樣定理生成σ*R（μ）=（u，I*，W*，c*，z*，k*），將其返回給敵手Euclid Math OneAAp，敵手Euclid Math OneAAp給出對b的猜測，其余部分均與Game0相同。

Game0與Game1生成的簽名分別為σR（μ）與σ*R（μ），因為σR（μ）與σ*R（μ）均是利用拒絕采樣定理得到的，故兩個簽名的分布統計距離可忽略不計，兩者是不可區分的，所以敵手Euclid Math OneAAp在匿名性游戲中獲勝的優勢是可忽略的，本方案滿足匿名性。

4.4 可鏈接性

定理5 若本文方案是不可偽造的，在隨機預言機模型下，對于任意多項式時間敵手Euclid Math OneAAp，本文方案簽名滿足可鏈接性。

證明 根據可鏈接性的定義，假設敵手Euclid Math OneAAp能以不可忽略的優勢ε贏得定義6中的游戲，則敵手Euclid Math OneAAp將與挑戰者Euclid Math OneBAp進行如下交互：

a）Euclid Math OneBAp輸入安全參數n，從Euclid Math TwoZApn×mq中均勻隨機抽樣得到A，選取抗碰撞單向哈希函數HA∈Euclid Math OneHAp，輸出這些公共參數；然后從{0，1}m中均勻隨機選擇xi，i∈［0，N－1］，分別計算di=bin（A·xi mod q），di∈{0，1}nk，加入環R，保留私鑰xi，i∈［0，N－1］，輸出環R=（d0，…，dN－1）。

b）敵手Euclid Math OneAAp可以進行多項式次的訪問預言機，包括哈希詢問、私鑰詢問及簽名詢問，Euclid Math OneBAp將詢問結果返回給Euclid Math OneTAp1。

（a）私鑰詢問：Euclid Math OneAAp可以選擇d∈R進行詢問，Euclid Math OneBAp將其對應的私鑰x返回給Euclid Math OneAAp。

（b）哈希詢問：①H1詢問，Euclid Math OneAAp可以利用私鑰x進行詢問，Euclid Math OneBAp將I返回給Euclid Math OneAAp;②H2詢問，Euclid Math OneAAp可以選擇d的w進行詢問，Euclid Math OneBAp將W返回給Euclid Math OneAAp;③H3詢問，Euclid Math OneAAp可以選擇μ∈{0，1}*，及d∈R進行詢問，Euclid Math OneBAp將z返回給Euclid Math OneAAp。

（c）簽名詢問：Euclid Math OneAAp選擇環R=（d0，…，dN－1）、μ∈{0，1}*及d∈R進行詢問，Euclid Math OneBAp執行算法LSignpp（sk，μ，R），用d對應的私鑰x進行簽名，生成σR（μ）并返回給Euclid Math OneAAp。

c）敵手Euclid Math OneAAp輸出兩個簽名σR1（μ1）=（u1，I1，W1，c1，z1，k1）與σR2（μ2）=（u2，I2，W2，c2，z2，k2）。

假設敵手Euclid Math OneAAp能在僅持有一個私鑰的情況下以不可忽略的優勢ε生成兩個環簽名σR1（μ1）、σR2（μ2），并且LVerifypp（μi，Ri，σRi（μi））=1，i∈{1，2}，因為本文提出的簡短可鏈接環簽名具有不可偽造性，所以只有當敵手Euclid Math OneAAp誠實地按簽名機制生成σR1（μ1）、σR2（μ2）時，這兩個簽名才能通過驗證返回1。

另一方面，本文有I1=H1（A，x1），I2=H1（A，x2），因為敵手Euclid Math OneAAp僅擁有一個私鑰，則有x1=x2，在詢問隨機預言機H1（·，·）時，相同的詢問會有相同的回應，此時有I1=I2，則LLink（σR1（μ1），σR2（μ2））=linked。這與假設相矛盾，所以敵手Euclid Math OneAAp的優勢是可忽略的。定理得證。

5 性能分析與實驗評估

5.1 性能分析

文獻[10]方案及L2RS［11］均為格上的可鏈接環簽名方案，本文方案LSLRS將與這兩個方案在時間開銷和存儲開銷方面分別進行對比分析。

三種方案的時間開銷對比如表1所示。統一使用N代表環成員個數，TH代表方案中的各種哈希運算的單步平均耗時（除了本文方案的HA），使用TTG、TSP、TSD、TLHL、TMUL、Tbin、TTAcc、TTWitness分別表示陷門生成算法［23］、原像抽樣算法［23］、高斯抽樣算法［23］、剩余哈希引理［11］、矩陣向量乘法、bin（ ）算法、TAccA（）算法、TWitnessA（）算法的單步平均耗時，這些運算耗時相對較多，主要以這些運算衡量方案的時間開銷，忽略矩陣加減等耗時相對較少的運算。從系統創建（setup）、用戶密鑰生成（key generate）、簽名生成（sign）、簽名驗證（verify）所消耗的時間進行分析，其中log的底數為2。

在系統創建階段，文獻［10］方案是基于身份的可鏈接環簽名，需要運用陷門生成算法生成系統主密鑰，故該階段的時間開銷主要為TTG，L2RS［11］及本文方案是非基于身份的簽名，沒有這部分的時間開銷。在用戶密鑰生成階段，因需要生成N對公私鑰，LSLRS需執行N次矩陣向量乘法和N次bin（ ）算法， Tbin=O（max log vi），TMUL=O（nm），顯然Tbinlt;TMUL；文獻［10］方案需要N次的哈希運算和N次的原像抽樣算法，L2RS［11］需要N次的矩陣向量乘法和N次的剩余哈希引理算法。在簽名生成階段，LSLRS需要執行三次哈希運算、一次TAccA（）算法、一次TWitnessA（）算法、一次高斯抽樣算法、一次矩陣向量乘法及一次bin（ ）算法，其中HA的時間復雜度為THA=2TMUL+Tbin=O（nm）+O（max log vi）=O（nm），TTAcc=（N－1）THA=（N－1）×O（nm）=（N－1）TMUL，TTWitness=O（l2）=O（log2 N），顯然TTWitnesslt;TMUL，該階段LSLRS的時間開銷為3TH+N×TMUL+TTWitness+Tbin+TSD；文獻［10］需要執行N+1次的哈希運算、2N+1次的矩陣向量乘法及N次高斯抽樣算法，L2RS需要執行N次哈希運算、3N+2次矩陣向量乘法及N次高斯抽樣算法；顯然，在該階段LSLRS效率最優。在簽名驗證階段，LSLRS需要執行一次TAccA（）算法、一次哈希運算及兩次矩陣乘法運算，該階段的總時間開銷為TH+（N+1）TMUL；L2RS需要執行N次哈希運算和4N+1次的矩陣向量乘法，文獻［10］方案需要執行2N次哈希運算和2N次的矩陣向量乘法；在該階段LSLRS效率最優。這里用T（L2RS）表示L2RS的時間復雜度，用T（TANG）表示文獻［10］的時間復雜度，用T（LSLRS）表示本文方案的時間復雜度，則

T（L2RS）=N×TMUL+N×TLHL+N×TH+

（3N+2）TMUL+N×TSD+N×TH+（4N+1）TMUL=

（8N+3）TMUL+N×TSD+2N×TH+N×TLHL

T（TANG）=TTG+N×TH+N×TSP+（N+1）TH+

（2N+1）TMUL+N×TSD+2N×TH+2N×TMUL=

（4N+1）TMUL+N×TSD+（4N+1）TH+N×TSP+TTG

T（LSLRS）=N×Tbin+N×TMUL+3TH+TTAcc+

TTWitness+TSD+TMUL+Tbin+TTAcc+TH+2TMUL=

（N+3）TMUL+2TTAcc+TSD+4TH+（N+1）Tbin+TTWitness=

（N+3）TMUL+2（N－1）TMUL+TSD+4TH+（N+1）Tbin+TTWitness=

（3N+1）TMUL+（N+1）Tbin+TTWitness+TSD+4TH

顯然T（LSLRS）最小，故本文方案的效率最高。

三種方案的存儲開銷對比如表2所示，仍然統一使用N表示環成員個數，主要從單個用戶的公鑰長度、私鑰長度及簽名長度進行對比。log的底數為2，log qgt;1。在單個用戶公鑰長度方面，LSLRS的公鑰di∈{0，1}nk為nk（即n「log q）維的列向量，每個向量元素為0或1，故單個公鑰占n「log q位；文獻［10］的方案公鑰屬于Euclid Math TwoZApnq，為n維列向量，故長度為n log q；L2RS［11］的公鑰屬于卷積多項式環Euclid Math OneRAp1×m2q，通常將其表示為矩陣形式（即系數矩陣），其系數矩陣屬于Euclid Math TwoZApn×m2q，故公鑰長度為nm+nm log q。LSLRS的公鑰長度與文獻［10］的幾乎一樣，較L2RS有明顯的減小。在單個用戶私鑰長度方面，LSLRS的公鑰xi∈{0，1}m為m維的列向量，每個向量元素為0或1，故單個公鑰占m位；文獻［10］的私鑰屬于Euclid Math TwoZApmq，為m維列向量，故長度為m log q；L2RS［11］的私鑰屬于卷積多項式環Euclid Math OneRApm×12q，通常將其表示為矩陣形式（即系數矩陣），其系數矩陣屬于Euclid Math TwoZApm×n2q，故私鑰長度為nm+nm log q。LSLRS的私鑰長度較L2RS和文獻［10］有明顯的減小。在單個簽名長度方面，LSLRS生成的簽名（u，I，W，c，z，k）∈{0，1}nk×Euclid Math TwoZApq×Euclid Math TwoZApq×{0，1}nk×Euclid Math TwoZApq×Euclid Math TwoZApmq，文獻［10］生成的簽名（C1，t1，…，tN，I，b）∈Euclid Math TwoZApq×（Euclid Math TwoZApm+1q）N×Euclid Math TwoZApq×Euclid Math TwoZApnq，L2RS［11］的簽名（c1，t1，…，tN，H）∈Euclid Math OneRAp2q×（Euclid Math TwoZApm2q）N×Euclid Math OneRAp1×m2q，對比表明LSLRS的簽名長度較L2RS和文獻［10］有明顯的減小，而且隨著環成員數量N的增大，L2RS和文獻［10］的簽名長度會隨之增大，而LSLRS的簽名長度固定不變。綜上可知，LSLRS的整體存儲開銷明顯小于L2RS和文獻［10］的。

5.2 實驗評估

本文實驗在配置為Windows 10系統、英特爾酷睿i7-10750H@2.60 GHz處理器、512 GB固態硬盤、8 GB內存的計算機上運行，將參數設置為n=8，m=512，q=232。

表3為三個方案（L2RS［11］、文獻［10］、LSLRS）的時間開銷統計，環成員個數為16；圖1為依據表3中的數據畫出的時間開銷對比圖。從表3和圖1中可以看出，LSLRS在系統創建、簽名、驗證階段的時間開銷最小，且總時間開銷也是最小的，效率最高，具體原因已在上文進行了分析，此處不再贅述。

表4為三個方案（L2RS［11］、文獻［10］、LSLRS）的存儲開銷統計；圖2為依據表4中的單個公私鑰長度數據畫出的密鑰長度對比圖；圖3為依據表4中的簽名長度數據畫出的簽名長度對比圖。從表4和圖2可以看出，LSLRS的單個公鑰長度較小，單個私鑰長度最小；從表4和圖3可以看出，LSLRS的簽名長度最小，隨著環成員個數的增大，L2RS［11］與文獻［10］的簽名長度均在增大，而LSLRS的簽名長度保持不變，具體原因見上文的分析。

6 結束語

可鏈接環簽名能有效解決區塊鏈電子貨幣系統的雙花攻擊與區塊鏈電子選舉系統的重復投票問題，但已有基于格的可鏈接環簽名長度隨環成員的增多而增大，本文提出了基于格的簡短可鏈接環簽名。隨著環成員的增多，本文LSLRS的簽名長度保持不變，同時節省了時間和存儲開銷，因此本文方案具有更強的實用性。基于SIVP問題證明了簽名的不可偽造性，另外還證明了簽名的匿名性和可鏈接性。下一步工作將致力于提出具體的基于格的區塊鏈安全應用方案，進一步提高方案效率，確保區塊鏈技術能更好地為社會大眾服務。

參考文獻：

[1]Yang Di， Long Chengnian， Xu Han， et al. A review on scalability of blockchain［C］//Proc of the 2nd International Conference on Blockchain Technology.New York：ACM Press，2020：1-6.

［2]蔡曉晴，鄧堯，張亮，等.區塊鏈原理及其核心技術［J］計算機學報，2021，44（1）：84-131.（Cai Xiaoqing， Deng Yao， Zhang Liang， et al. The principle and core technology of blockchain［J］.Chinese Journal of Computers，2021，44（1）：84-131.）

［3]Rivest R L， Shamir A， Tauman Y. How to leak a secret［C］//Proc of the 7th International Conference on the Theory and Application of Cryptology and Information Security：Advances in Cryptology.Berlin：Springer，2001：552-565.

［4]范青，何德彪，羅敏，等.基于SM2數字簽名算法的環簽名方案［J］.密碼學報，2021，8（4）：710-723.（Fan Qing， He Debiao， Luo Min， et al. Ring signature schemes based on SM2 digital signature algorithm［J］.Journal of Cryptologic Research，2021，8（4）：710-723.）

［5]Liu J K， Wei V K， Wong D S. Linkable spontaneous anonymous group signature for Ad hoc groups［C］//Proc of the 9th Australasian Conference on Information Security and Privacy.Berlin：Springer，2004：325-335.

［6]Lyu Jiazhuo， Jiang Z L， Wang Xuan， et al. A secure decentralized trustless e-voting system based on smart contract［C］//Proc of the 18th IEEE International Conference on Trust， Security and Privacy in Computing and Communications.Washington DC：IEEE Computer Society，2019：570-577.

［7]Tsang P P， Wei V K. Short linkable ring signatures for e-voting， e-cash and attestation［C］//Proc of the 1st Information Security Practice and Experience Conference.Berlin：Springer，2005：48-60.

［8]Au M H， Chow S S M， Susilo W， et al. Short linkable ring signatures revisited［C］//Proc of the 3rd European Public Key Infrastructure Workshop.Berlin：Springer，2006：101-115.

［9]Yu Bin， Liu J K， Sakzad A， et al. Platform-independent secure blockchain-based voting system［C］//Proc of the 21st International Information Security Conference.Berlin：Springer，2018：369-386.

［10]湯永利，夏菲菲，葉青，等.格上基于身份的可鏈接環簽名［J］.密碼學報，2021，8（2）：232-247.（Tang Yongli， Xia Feifei， Ye Qing， et al. Identity-based linkable ring signature on lattice［J］.Journal of Cryptologic Research，2021，8（2）：232-247.）

［11]Torres W A， Kuchta V， Steinfeld R， et al. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain （Lattice RingCT v1. 0）［C］//Proc of the 23rd Australasian Conference on Information Security and Privacy.Berlin：Springer，2018：558-576.

［12]Torres W A， Kuchta V， Steinfeld R， et al. Lattice RingCT v2. 0 with multiple input and multiple output wallets［C］//Proc of the 24th Australasian Conference on Information Security and Privacy.Berlin：Springer，2019：156-175.

［13]Baum C， Huang Lin， Oechsner S. Towards practical lattice-based one-time linkable ring signature［C］//Proc of International Confe-rence on Information and Communications Security.Cham：Springer，2018：303-322.

［14]Liu Zhen， Nguyen K， Yang Guomin， et al. A lattice-based linkable ring signature supporting stealth addresses［C］//Proc of the 24th European Symposium on Research in Computer Security.Cham：Sprin-ger，2019：726-746.

［15]Saberhagen N V. CroptoNote v2.0［EB/OL］.（2013-10-17）［2022-02-08］.https：//static.coinpaprika.com/storage/cdn/whitepapers/1611.pdf.

［16]葉青，王文博，李瑩瑩，等.利用環上容錯學習問題構造可鏈接環簽名方案［J］.計算機科學與探索，2020，14（7）：1164-1172.（Ye Qing， Wang Wenbo， Li Yingying， et al. Using ring learning with errors problem to construct linkable ring signature scheme［J］.Journal of Frontiers of Computer Science and Technology，2020，14（7）：1164-1172.）

［17]莊立爽，陳杰，王啟宇.電子投票協議下的基于格的可鏈接門限環簽名［J］.密碼學報，2021，8（3）：402-416.（Zhuang Lishuang， Chen Jie， Wang Qiyu. Lattice-based linkable threshold ring signature in evoting［J］.Journal of Cryptologic Research，2021，8（3）：402-416.）

［18]嚴蔚敏，李冬梅，吳偉民.數據結構：C語言版［M］.2版.北京：人民郵電出版社，2015：55.（Yan Weimin， Li Dongmei， Wu Weimin. Data structure［M］.2nd ed.Beijing：Posts amp; Telecom Press，2015：55.）

［19]Camenisch J， Stadler M. Efficient group signature schemes for large groups （extended abstract）［C］//Proc of the 17th Annual International Cryptology Conference.Berlin：Springer，1997：410-424.

［20]Libert B， Ling S， Nguyen K， et al. Zero-knowledge arguments for lattice-based accumulators： logarithmic-size ring signatures and group signatures without trapdoors［C］//Proc of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin：Springer，2016：1-31.

［21]Lyubashevsky V. Lattice signatures without trapdoors［C］//Proc of the 31st Annual IACR Eurocrypt International Conference on the Theo-ry and Applications of Cryptographic Techniques.Berlin：Springer，2012：738-755.

［22]楊波.現代密碼學［M］.4版.北京：清華大學出版社，2017：273-274.（Yang Bo. Modern cryptography［M］.4th ed. Beijing： Tsinghua University Press，2017：273-274.）

［23]Gentry C， Peikert C， Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions［C］//Proc of the 14th Annual ACM International Symposium on Theory of Computing.New York：ACM Press，2008：197-206.