后量子安全的群簽名和環(huán)簽名*

馮翰文, 劉建偉, 伍前紅

北京航空航天大學 網(wǎng)絡空間安全學院, 北京100191

1 引言

在確保業(yè)務功能正常運行的前提下盡可能保護用戶隱私是現(xiàn)代密碼學的主要目標之一. 但是作為實現(xiàn)身份認證等核心業(yè)務功能的密碼學原語, 數(shù)字簽名并沒有將隱私性作為安全目標. 簽名者的公鑰是驗證簽名合法性的必要信息, 因此數(shù)字簽名的簽名者身份總是對驗證者可見的. 這種顯式的合法性驗證方式并不符合某些場景下的用戶需求. 例如, 為了避免受到干擾, 電子投票系統(tǒng)[1]中投票人只希望他的選票能夠被驗證為由合法的選民生成, 但不希望泄露他的身份; 為了避免泄露財產(chǎn)信息, 數(shù)字貨幣系統(tǒng)[2]中的用戶只希望系統(tǒng)能驗證他所花費的貨幣是系統(tǒng)內的合法貨幣, 但不希望明確指出花費的是哪個貨幣. 這些現(xiàn)實場景需要既能實現(xiàn)身份認證又能保護用戶身份隱私的密碼學工具.

群簽名(group signature)[3]和環(huán)簽名(ring signature)[4]等密碼學原語關注了上述場景下的用戶隱私保護問題. 它們允許簽名者以群組的名義簽名, 驗證者只能確認簽名由群組內的某個用戶生成, 而無法獲知簽名者的具體身份. 其中, 群簽名系統(tǒng)存在群管理員角色, 負責管理群成員, 并可以追蹤簽名者身份;環(huán)簽名中的群組是完全自組織的, 不存在任何特殊機構, 簽名的匿名性也無法被撤銷, 提供了更高級別的隱私保護. 本文在不引起歧義的前提下將群簽名和環(huán)簽名統(tǒng)稱為類群簽名. 經(jīng)過幾十年的研究發(fā)展, 類群簽名在理論上形成嚴格的模型和定義[5,6], 在構造上具有多個滿足實際效率需求的方案[7–9], 在功能上具備了適用于不同場景的變種[10,11], 在電子現(xiàn)金[12]、數(shù)字貨幣[13]、電子投票[1]和可信計算[14]等領域發(fā)揮著關鍵作用.

量子計算機的出現(xiàn)對經(jīng)典密碼體系造成了體系沖擊. Shor 在1994 年提出了可以有效解決離散對數(shù)問題和大整數(shù)分解問題的量子算法[15], 從理論上攻破現(xiàn)在所有基于離散對數(shù)和大整數(shù)分解的密碼方案. 近年來量子計算機實用化的進程不斷推進, 使得在現(xiàn)實中攻破經(jīng)典密碼體系趨于可能. 如何應對量子計算機的威脅, 是最近十多年來密碼學界研究的熱點問題, 主流解決思路是基于量子算法不能有效解決的困難問題重新構建完善的后量子公鑰加密體系. 基于格上困難問題[16]、編碼理論[17]、對稱密碼學原語[18]、同源函數(shù)[19]和多變量多項式[20]等被廣泛認為抗量子安全的假設, 公鑰加密方案和數(shù)字簽名等基礎密碼原語已經(jīng)具備實用化的后量子安全解決方案. 其中, 基于格的密碼體系[16]由于具備代數(shù)操作簡單、漸進效率高、可歸約到最壞情況(worst-case) 困難問題以及支持全同態(tài)加密[21]等高級密碼學原語構造的優(yōu)點,受研究者廣泛關注.

與數(shù)字簽名和公鑰加密等基礎原語不同, 后量子安全的類群簽名研究起步較晚, 仍處在快速發(fā)展的階段. 在Asiacrypt 2010 上, Gordon、Katz 和Vaikuntanathan[22]設計了首個基于格上困難問題的群簽名方案, 拉開了近十年來后量子安全類群簽名研究的序幕. 以豐富功能、提高效率和增強安全性為目標, 大量的后量子安全的群簽名[23,24]和環(huán)簽名方案[25,26]被相繼提出. 一方面, 基于格上困難問題的構造最受關注. 功能方面, 以Libert 等人的工作[24]為代表的一系列工作[27–32], 在格密碼體系下實現(xiàn)了具有多種不同功能性質的類群簽名方案. 效率方面, Esign 等人[25]在2019 年的突破性工作使得基于格的環(huán)簽名方案滿足了實用化需求, Yang 等人的工作[33]和Pino 等人的工作[34]也極大地提高了基于格的群簽名方案的效率. 值得注意的是, 這些基于格的類群簽名方案設計也極大地推動了基于格的零知識證明系統(tǒng)的研究, 對格密碼學產(chǎn)生了更加廣泛的影響. 其中部分技術也被延伸到基于編碼理論的密碼體系, 用于設計相應的類群簽名方案[35]. 另一方面, 2016 年Giacomelli、Madsen 和Orlandi[36]基于對稱密碼學原語提出了高效的非交互式零知識(non-interactive zero-knowledge, NIZK) 證明系統(tǒng), 豐富了后量子密碼體系的工具庫, 啟發(fā)了基于對稱密碼學原語設計類群簽名的新思路[18,37], 為后量子安全的實用化類群簽名方案提供了新的可能.

本文結合當前領域的主要成果, 較為全面地介紹了基于格上困難問題和對稱密碼學原語兩類假設的類群簽名方案. 從技術角度對現(xiàn)有的后量子安全的類群簽名方案進行分類總結, 歸納了現(xiàn)有各類構造技術的特點和局限, 理清了該領域的技術發(fā)展脈絡, 總結了一些還有待解決的重要問題. 本文組織結構如下: 第2節(jié)介紹了類群簽名的基本定義和設計思想; 第3 節(jié)和第4 節(jié)分別具體綜述了基于格的和基于對稱密碼學原語的類群簽名方案研究; 第5 節(jié)介紹了量子隨機預言機模型, 并探討了如何構造量子隨機預言機模型下可證明安全的類群簽名方案; 第6 節(jié)展望了該領域目前還有待解決的若干問題.

2 類群簽名的基本概念及設計思想

2.1 群簽名

群簽名最早由Chaum 和van Heyst 在1991 年提出[3]. 該密碼學原語允許群成員以整個群組的名義簽名任意的消息, 從而使驗證者可以確認該簽名由群中某個成員生成, 但無法得知簽證者的具體身份.

根據(jù)群成員是否可以在系統(tǒng)啟動后動態(tài)加入或撤銷, 群簽名方案可以分為靜態(tài)群簽名[5]、動態(tài)群簽名[38](僅動態(tài)加入), 可撤銷群簽名[39]和全動態(tài)群簽名[40](動態(tài)加入和撤銷) 等. 本節(jié)沿用Bellare 等人的靜態(tài)群簽名形式化定義[5], 介紹靜態(tài)群簽名這一基本模型. 動態(tài)群簽名和全動態(tài)群簽名的定義和模型可參考Kiayias 和Yang 的工作[38]和Bootle 等人的工作[40].

靜態(tài)群簽名定義. 靜態(tài)群簽名[5]是指所有的群成員及其身份都在啟動階段確定且不能更改的群簽名方案. 靜態(tài)群簽名方案存在群管理員和用戶兩類實體, 其中群管理員負責追蹤簽名者的身份. 該類方案依賴一個可信機構來生成系統(tǒng)公開參數(shù)和群管理員的私鑰, 并為所有的群成員分別生成并分發(fā)簽名密鑰. 一個靜態(tài)群簽名方案由兩個多項式概率時間(polynomial probabilistic time, PPT) 的隨機化算法和兩個多項式時間的確定性算法定義, 分別是: 密鑰生成(GKg)、簽名(GSig)、簽名驗證(GVf)、開啟(Open), 具體描述如下.

(1) (gpk,gmsk,gsk) ←GKg(1λ,1N). 群密鑰生成算法是隨機化算法, 以安全參數(shù)λ ∈N 和群成員數(shù)N ∈N 作為輸入, 輸出群公鑰gpk, 群管理員私鑰gmsk, 以及每一個群成員i ∈[N] 的簽名密鑰gsk[i] (構成向量gsk).

(2) σ ←GSig(gsk[i],M). 群簽名算法是隨機化算法, 以簽名密鑰gsk[i] 和待簽名消息M 作為輸入,

輸出群簽名σ.

(3) b ←GVf(gpk,M,σ). 群簽名驗證算法是確定性算法, 以群公鑰gpk, 消息M 和群簽名σ 作為輸

入, 輸出b ∈{0,1}.

(4) i or ⊥←Open(gmsk,M,σ). 開啟算法是確定性算法, 以群管理員私鑰gmsk, 消息M 和簽名σ

作為輸入, 輸出簽名者身份i ∈[N], 或者開啟失敗, 返回終止符⊥.

如果消息簽名對(M,σ) 滿足GVf(gpk,M,σ) = 1, σ 被稱為關于群公鑰gpk 的對消息M 的合法簽名.

靜態(tài)群簽名正確性. 該性質要求誠實生成的簽名永遠都是合法的, 以及誠實生成的簽名始終都能被Open 算法開啟為簽名者的身份.

靜態(tài)群簽名安全性. 靜態(tài)群簽名的經(jīng)典安全模型描述了兩個獨立的安全性質, 即完全匿名性(fullanonymity) 和完全可追蹤性(full-traceability):

? 完全匿名性: 敵手可以獲得所有群成員的私鑰, 可以任意地訪問開啟預言機(open oracle) 來獲得任一簽名的簽名者身份. 敵手可以指定兩個私鑰(gsk[i0],gsk[i1]) 和消息M 進行挑戰(zhàn), 但對于返回的挑戰(zhàn)簽名σ ←GSig(gsk[ib],M) (該簽名禁止問詢開啟預言機), 敵手仍然無法以不可忽略的優(yōu)勢判斷出b 的值.

? 完全可追蹤性: 敵手可以獲得系統(tǒng)主私鑰, 任意地獲得群成員的私鑰, 任意訪問特定私鑰的簽名預言機, 但仍然不能生成一個新的簽名使其被開啟為某個未被敵手獲得的私鑰對應的群成員.

根據(jù)文獻[41] 的結論, 完全匿名的群簽名方案必須依賴公鑰加密. 不依賴公鑰加密可實現(xiàn)的最優(yōu)匿名性被稱為無私匿名性(selfless anonymity), 其中敵手不能獲得被挑戰(zhàn)的兩個私鑰. 此外, 部分群簽名方案[22]的匿名性定義中, 群簽名無法訪問開啟預言機, 這樣的匿名性被稱為抗選擇明文攻擊的匿名性(CPA-anonymity).

2.2 環(huán)簽名

環(huán)簽名這一概念最早由Rivest、Shamir 和Tauman[4]提出. 環(huán)簽名允許用戶以一個自組織的用戶群體(被稱為環(huán)) 的名義簽名, 而不泄露簽名者的確切身份. 環(huán)簽名的概念與群簽名接近, 都是將簽名者身份隱藏到某個群體當中, 但存在顯著差異. 群簽名方案中存在群管理員可以撤銷群簽名的匿名性, 而環(huán)簽名中并不存在任何中心化的機構, 用于隱藏簽名者身份的群組可以是簽名者自己即時選擇的, 用戶之間也不需要任何的協(xié)作. 因此, 環(huán)簽名提供了更高的匿名性, 也更適用于密碼貨幣等[13]去中心化的應用場景.本綜述沿用Bender、Katz 和Morselli 提出的環(huán)簽名形式化模型及安全定義[6].

環(huán)簽名定義. 一個環(huán)簽名方案由以下三個算法定義: 密鑰生成(KeyGen)、簽名(Sign)、驗證(Verify).令公鑰序列R=(pk1,··· ,pkN) 為一個環(huán), 令R[i]=pki, 環(huán)簽名的形式化定義如下:

(1) (pk,sk) ← KeyGen(1λ). 密鑰生成算法以安全參數(shù)λ ∈ N 為輸入, 輸出用戶的公鑰私鑰對

(pk,sk).

(2) σ ←Sign(sk,s,M,R). 簽名算法以用戶私鑰sk、位置s、消息M 和環(huán)R 為輸入, 其中(R[s],sk)是一對由密鑰生成算法輸出的密鑰, R 中包含兩個以上的公鑰且兩兩不同. 該算法輸出簽名σ.

(3) b ←Verify(R,M,σ). 驗證算法以環(huán)R、消息M 和簽名σ 為輸入, 驗證σ 是否為M 在環(huán)R 下的合法簽名.

環(huán)簽名的正確性. 該性質要求所有誠實生成的環(huán)簽名都是合法的.

環(huán)簽名安全性. 環(huán)簽名需要滿足兩個獨立的安全性質, 即匿名性(anonymity) 和不可偽造性(unforgeability) 兩個性質. 前者要求攻擊者無法獲悉簽名者身份, 后者要求攻擊者無法在不掌握環(huán)中任何一個私鑰的情況下生成合法的簽名. 根據(jù)攻擊者能力的不同, 匿名性和不可偽造性有多種定義方式. 本綜述介紹攻擊者能力最強的定義.

? 抗密鑰全泄露匿名性. 敵手可以用任意方式(非誠實運行密鑰生成算法) 生成公鑰, 并獲得誠實用戶在包含非誠實生成公鑰的環(huán)下的簽名; 敵手可以獲得誠實用戶的密鑰生成過程中使用的隨機數(shù)(這是比獲得私鑰更強的能力); 敵手可以指定任意兩個誠實生成的公鑰(pk0,pk1) 作為挑戰(zhàn)公鑰,并指定簽名消息M 和環(huán)R = R′∪{pk0,pk1}; 對于誠實生成的簽名σ ←Sign(skb,sb,M,R), 敵手仍然無法以不可忽略的優(yōu)勢判斷b 的值.

? 抗內部腐化攻擊的不可偽造性. 對于一個誠實生成的公鑰集合, 敵手可以任意訪問他們對應的簽名預言機, 可以任意獲得部分公鑰對應的私鑰; 但對于由沒有被獲得私鑰的公鑰構成的子環(huán), 敵手無法以不可忽略的概率偽造簽名.

環(huán)簽名的變種. 環(huán)簽名較常見的變種包括可鏈接環(huán)簽名[10](linkbale ring signature). 標準的可鏈接性引入標簽這一概念來刻畫當前使用環(huán)簽名的具體事項(比如一次投票), 要求由同一個私鑰產(chǎn)生的兩個同一標簽下的環(huán)簽名可以被公開鏈接. 如果移除標簽的概念, 要求只要兩個環(huán)簽名由同一個私鑰產(chǎn)生即可鏈接, 該性質被稱為一次可鏈接性. 此外, 如果同一私鑰產(chǎn)生的兩個簽名不僅可以被鏈接, 還會直接暴露簽名者的身份, 這樣的環(huán)簽名方案被稱為可追蹤環(huán)簽名[11](traceable ring signature).

2.3 后量子安全的類群簽名的設計方法概述

群簽名和環(huán)簽名為用戶提供了相似的功能: 允許用戶以自己所在群組的名義對消息簽名, 簽名驗證者可以確認簽名由群成員產(chǎn)生, 但無法獲知簽名者具體身份. 二者在組織結構上存在差異: 群簽名的群組由群管理員維護, 且存在特殊機構可以追蹤任一群簽名的簽名者身份; 環(huán)簽名系統(tǒng)并不存在中心化機構, 簽名時所用的群組由簽名者自行定義.

組織結構的不同不僅導致了二者應用場景的差異, 也使得它們的設計方法有所不同. 群簽名和環(huán)簽名都可保證非群組成員無法以該群組的名義簽名, 因此每一個群簽名或者環(huán)簽名都可以視作是對群成員關系的證明. 環(huán)簽名的群組要求具備自組織性, 通常由公鑰集合的形式來定義, 簽名者實質上需要證明持有其中某個公鑰的私鑰. 群簽名由于引入了群管理員這一特殊機構, 支持更加靈活多樣的群組定義方式. 首先, 使用公鑰集合定義群組的方法同樣適用于有管理員的群組, 其公鑰集合由管理員定義并公開; 群組也可以通過管理員持有的秘密信息定義, 例如管理員使用自己的私鑰對為所有群成員生成證書, 凡是持有合法證書的用戶都被視為群成員. 因此, 從群成員關系證明的角度來看, 群簽名可能比環(huán)簽名更容易構造. 但是, 群簽名需要額外支持特殊機構對簽名者身份的追蹤, 給方案設計增加了難度. 技術上, 幾乎所有的群簽名[5,38,42]構造都遵循Bellare、Micciancio 和Warinschi[5]提出的“加密后證明”(encrypt-then-prove)范式. 為了簽名一個消息, 群成員首先使用追蹤機構的公鑰加密自己持有的由群管理員提供的證書, 再證明該密文確實是合法生成的. 驗證簽名的過程即驗證證明的過程, 而追蹤機構可以用私鑰解密密文獲得簽名者身份. 因此, 群簽名的構造除了要證明群成員關系, 需要額外證明密文是正確生成的. 后者通常制約群簽名效率提高的原因.

類群簽名設計方法在經(jīng)典密碼體制下已有較充分的討論. 核心密碼組件概括如圖1所示.

圖1 類群簽名的構造組件Figure 1 Building blocks of group signatures and ring signatures

(自組織的) 群成員關系定義和證明. 群成員關系定義是任何類群設計的出發(fā)點. 群成員關系的定義方法決定了方案的用戶密鑰形式, 也關系到可以使用何種證明方法來證明此種群成員關系. 在經(jīng)典密碼體制下, 自組織的群成員關系有以下兩種常見定義:

? 由公鑰集合直接定義. 群組直接表示為用戶的公鑰集合: G = {pk1,··· ,pkn}. 集合G 對應的關系可以表示為: 存在sk 使得∨i∈[n]R(pki,sk)=1, 其中R(pk,sk)=1 代表sk 是pk 對應的私鑰.Cramer、Damg?rd 和Schoenmakers[43]提出的證明系統(tǒng)構造框架適用于此種群成員關系定義方法. 這種群組定義方法比較直觀, 其對應的證明方法通用性強, 可以通過單個公鑰對應的身份認證協(xié)議轉換得到. 其缺點是產(chǎn)生的證明大小與集合大小線性相關.

? 使用累加器(accumulator)[44]定義. 累加器可視為對集合的承諾承諾值u (稱為累加值) 與集合大小無關. 集合中每一個元素e 都對應一個短證據(jù)w, w 的大小與集合大小成次線性關系, 且任何掌握w,e 和u 的個體都可以高效驗證e 是被承諾集合中的元素. 令{pk1,··· ,pkn} 為構成群組的公鑰集合, 令u 是該集合對應的累加值. 此時群組可直接用u 表示, 對應的群成員關系為: 存在pk, sk 和w, 使得R(pk,sk)=1 且w 是pk 在u 中的證據(jù). Merkle 樹[45]是一種典型的累加器.

對于群簽名系統(tǒng)中有管理員管理的群組, 除了使用自組織的群定義方式外, 還可以基于標準模型下的數(shù)字簽名方案定義. 具體的, 令(vk,sk) 為群管理員持有的簽名公私鑰對, 群組由所有被管理員簽名的元素構成. 群成員關系證明即為證明持有vk 下合法的簽名消息對.

密文正確性證明. 公鑰加密和密文證明是群簽名構造的重要組件, 用于實現(xiàn)簽名者的身份追蹤功能.在群簽名的全匿名性定義中, 攻擊者可以任意開啟簽名者的身份. 為了實現(xiàn)這一安全性, 公鑰加密方案需要對應滿足選擇密文攻擊(IND-CCA) 的安全性. 密文證明是指證明密文是在追蹤機構的公鑰下合法生成的, 且明文滿足特定的關系(群簽名中常見的是滿足群成員關系). 需要指出的是, 基于對稱密碼原語的群簽名方案[18]并不使用公鑰加密作為構造組件, 而是采用了文獻[41] 提出的基于偽隨機函數(shù)的構造方法來實現(xiàn)可追蹤性, 相應的代價是該方案無法達到完全匿名性.

證明的隱私性要求. 類群簽名的主要安全目標是保護用戶的隱私, 因此構造中使用的群成員關系證明和密文正確性證明方法應當保證驗證者無法從證明中獲得簽名者的任何身份信息. 現(xiàn)有構造通常使用非交互式零知識(non-interactive zero-knowledge, NIZK) 證明系統(tǒng)[46]來實現(xiàn)隱私保護的目標. 具體的,一個適用于NP 語言L 的NIZK 證明系統(tǒng)由三個算法刻畫: 1) 啟動算法(Setup), 用于生成共享字符串(common reference string, CRS), 或者確定一個隨機預言機; 2) 證明算法(Prove), 以x 的證據(jù)w 為輸入, 生成證明π 來表明x ∈L; 3) 驗證算法(Verify), 用于公開驗證證明π 是否合法. NIZK 證明系統(tǒng)需要滿足三個獨立的安全性質: 完備性(completeness): 誠實生成的證明始終能通過驗證; 可靠性(soudness):對于錯誤的論斷x /∈L, 任何人不能產(chǎn)生合法的證明π 表明x ∈L; 零知識性(zero-knowledge): 任何人無法從證明中獲得除了x ∈L 以外的任何信息.

此外, 也有部分方案采用非交互式證據(jù)不可區(qū)分[47](non-interactive witness-indistinguishable) 的證明系統(tǒng). 對于一個待證明的論斷x, 令w0和w1是該論斷不同的證據(jù), 證據(jù)不可區(qū)分性保證驗證者無法區(qū)分由w0和w1產(chǎn)生的證據(jù). 非交互式證據(jù)不可區(qū)分證明系統(tǒng)所依賴的假設和模型往往弱于零知識證明系統(tǒng), 因此通常被用于實現(xiàn)弱假設下的理論構造.

后量子安全的類群簽名方案的研究本質上是在解決上述密碼組件的后量子安全構造問題. 由于數(shù)字簽名、公鑰加密以及構造Merkle 樹所需的Hash 函數(shù)都已具備后量子安全的構造, 因此后量子安全類群簽名方案要解決的核心問題是這些群成員關系定義對應的具有隱私保護性質的證明方法. 本文在第3 節(jié)和第4 節(jié)將圍繞后量子安全的群成員關系證明方法和密文證明方法, 綜述現(xiàn)有方案.

3 基于格的類群簽名方案

本節(jié)按照安全證明模型(標準模型和隨機預言機模型)分別綜述格基類群簽名的發(fā)展歷程及研究現(xiàn)狀.標準模型下的構造主要是回答標準模型下格基類群簽名方案是否存在這一理論問題. 隨機預言機模型下的構造主要是考慮方案的功能性和效率, 目前大部分格基類群簽名方案在隨機預言機模型下可證明安全.隨機預言機模型下的方案大多以基于格的NIZK 證明系統(tǒng)作為核心組件, 使用何種零知識證明系統(tǒng)在很大程度上影響了簽名方案的構造方法和具體效率.

現(xiàn)有的格基NIZK 證明系統(tǒng)可以分為具備標準可靠性的NIZK (NIZK with standard soundness, ss-NIZK) 證明系統(tǒng)和具備弱可靠性的NIZK (NIZK with weak soundness, ws-NIZK) 證明系統(tǒng), 它們適用范圍和具體效率方面存在較大的差異. 具體的, NIZK 證明系統(tǒng)的可靠性往往通過知識提取器(extractor)定義. 標準的可靠性是指,若證明者可以產(chǎn)生關于x ∈L 的合法證明π,知識提取器從證明者處獲得x ∈L的證據(jù)w. 弱可靠性是指, 知識提取器只能從證明者處獲得某個與x 相關的論斷x′的證據(jù)w′.

為了理清技術發(fā)展脈絡, 本節(jié)進一步將隨機預言機模型下的格基類群簽名方案分為基于ws-NIZK 證明系統(tǒng)的方案和基于ss-NIZK 證明系統(tǒng)的方案, 分類進行綜述. 此外本文也綜述了隨機預言機模型下唯一一個不基于NIZK 的格基環(huán)簽名方案. 本節(jié)的所涉及的格密碼背景知識可參考王和劉的綜述[48].

3.1 標準模型下的后量子安全類群簽名方案

類群簽名的構造通常依賴于NIZK 證明系統(tǒng)或兩輪證據(jù)不可區(qū)分證明系統(tǒng)(ZAP)[47]. 然而在標準模型, 包括共享字符串模型(common reference string model, CRS) 和樸素模型(plain model) 中, 高效NIZK 證明系統(tǒng)和ZAP 的已知構造方式非常有限, 主要為Groth 和Sahai 利用雙線性映射構造的證明系統(tǒng)[49]. Groth 和Sahai 的證明系統(tǒng)也是現(xiàn)有的在標準模型下可證安全的群簽名方案和環(huán)簽名方案的構造基礎. 如何基于抗量子的困難問題假設構造類似于Groth 和Sahai 的NIZK 證明系統(tǒng)目前是一個公開難題.

理論上, 可證明所有NP 語言的通用NIZK 證明系統(tǒng)或者ZAP 可以用于證明格密碼學和對稱密碼學相關的語言. CRS 模型下的通用NIZK 證明系統(tǒng)構造是一個非常經(jīng)典的問題, 早在FOCS 1990 上Feige,Lapidot 和Shamir 就已經(jīng)提出了基于單向陷門置換(one-way trapdoor permutation) 的通用NIZK 證明系統(tǒng)[46]. 然而, 盡管單向陷門置換是一個簡單且優(yōu)美的密碼學基本原語, 且可以基于大整數(shù)分解假設構造, 我們對它的其他構造方式尤其是基于抗量子假設的構造方式卻知之甚少, 這也使得后量子安全的通用NIZK 證明協(xié)議是長期以來的公開難題. 可喜的是, 近年來對Fiat-Shamir 轉換在標準模型下的構造方法研究取得了突破性進展. CRYPTO 2019 上, Piekert 和Shehian 基于LWE 假設構造了具有Correlation Intractability (CI) 性質的Hash 函數(shù), 該Hash 函數(shù)可以用于替換Fiat-Shamir 轉換中的隨機預言機, 從而得到CRS 模型下的通用NIZK 證明系統(tǒng)[50]; Eurocrypt 2020 上, Badrinarayanan 等人同樣利用具有CI 性質的Hash 函數(shù), 構造了基于LWE 假設的ZAP[51]. 根據(jù)群簽名的通用構造[5]和環(huán)簽名的通用構造[6], 上述抗量子的證明系統(tǒng)也從理論上解決了標準模型下后量子安全類群簽名構造問題. 在實際效率方面, 基于LWE 的具有CI 性質的Hash 函數(shù)構造復雜, 依賴于全同態(tài)加密[21]等高級密碼學原語, 目前距離實用化還存在非常巨大的差距.

本節(jié)所綜述的標準模型下的環(huán)簽名和群簽名方案均在上述通用證明系統(tǒng)之前提出, 在當時解決了標準模型下后量子安全的類群簽名的存在性問題.

3.1.1 標準模型下的環(huán)簽名

Brakerski 和Kalai[52]提出了一種高效的通用框架來構造標準模型下的環(huán)簽名方案. 具體的, 該文獻定義了環(huán)陷門(ring trapdoor) 函數(shù)這一概念, 并展示了如何利用環(huán)陷門來構造環(huán)簽名. 其中, 環(huán)陷門函數(shù)是對普通陷門函數(shù)的擴展, 它不僅要求給定f 和y 找到x 使得f(x) = y 是困難的, 也要求對于給定的f1,··· ,ft,y 來找到x1,··· ,xt使得fi(xi) = y 是困難的; 但如果具有任何一個fi對應的陷門, 則可以有效計算出所有滿足條件的x1,··· ,xt. 運用環(huán)陷門函數(shù)構造環(huán)簽名方案的思路也比較直觀, 函數(shù)本身作為簽名的公鑰, 函數(shù)對應的陷門作為簽名的私鑰, 求出的逆x1,··· ,xt作為環(huán)f1,··· ,ft下的簽名.

對于環(huán)陷門函數(shù)這一新定義, 該文獻基于格上的最小整數(shù)解(short integer solution, SIS) 問題[53]和雙線性對上的計算性Diffie-Hellman 問題分別構造了具體的環(huán)陷門函數(shù). 使用基于SIS 問題的環(huán)陷門函數(shù)實例化通用框架可以得到在標準模型下可證安全的格基環(huán)簽名方案. 由于該方案中, 簽名由所有的逆組成, 因此簽名的大小和環(huán)的規(guī)模線性相關. 同時, 基于格的環(huán)陷門函數(shù)依賴格的陷門函數(shù)[54], 該陷門函數(shù)需要較大的格維度, 這也導致簽名的實際大小過大[55], 不滿足實際應用需要.

3.1.2 標準模型下的群簽名

Katsumata 和Yamada[56]為了構造在標準模型下可證明安全的格基群簽名方案, 他們繞過了傳統(tǒng)的群簽名設計框架, 提出了不基于非交互零知識證明的構造方法. 他們構造的核心思想是利用屬性基簽名[57]來替代群簽名構造中非交互零知識證明的功能. 屬性基簽名有基于格的構造[58], 且在標準模型下可證明安全. 屬性基簽名方案中, 由密鑰中心向用戶分發(fā)某一屬性x 對應的私鑰skx, 而持有該私鑰的用戶可以生成滿足C(x) = 1 的屬性策略C 下合法的簽名. 與非交互零知識證明對應, 在屬性策略C 下的簽名可以視為對滿足C(x)=1 的x 的知識證明. 不同的是, 持有屬性x 的用戶必須事先從密鑰中心獲得私鑰skx才能完成進行簽名. 在群簽名中, 簽名者需要證明密文的正確性, 而加密所用的隨機數(shù)作為證據(jù)的一部分是在簽名過程中產(chǎn)生的, 無法被密鑰中心事先得知并生成對應的私鑰, 因此直接使用屬性基簽名無法得到安全的群簽名方案. Katsumata 和Yamada 借鑒了Kim 和Wu[59]構造預處理非交互零知識證明協(xié)議的思想, 使用對稱加密方案對憑據(jù)進行加密, 并將證明加密正確性轉換為證明解密的正確性, 通過解密的確定性移除加密的不確定性, 使得群管理員可以一次性生成用戶所需的簽名私鑰, 從而解決了該問題. 由于用戶同樣掌握解密密鑰, 可以確定某一簽名是否由自己的私鑰產(chǎn)生, 因此該方案的匿名性為無私匿名性而非完全匿名性. 該方案中, 密鑰中心需要掌握用戶所有的秘密信息, 并在啟動階段生成對應的私鑰, 因此該方案屬于靜態(tài)群簽名方案. 如何利用屬性基簽名來構造動態(tài)群簽名方案尚缺乏清晰的技術途徑.

3.2 基于ws-NIZK 證明系統(tǒng)的類群簽名方案

基于ws-NIZK 證明系統(tǒng)的格基類群簽名方案可以分為兩個階段. 早期方案使用的ws-NIZK 證明系統(tǒng)為MV03 證明系統(tǒng)[60]和Fiat-Shamir-with-Abort(FSwA) 證明系統(tǒng)[55]. 這兩個證明系統(tǒng)最早被用于證明GapCVP 或非齊次最小整數(shù)解問題(inhomogeneous small integer solution, ISIS) 等格上困難問題,應用到類群簽名的構造時需要配合額外的技術, 效率較低. 2018 年后的部分格基類群簽名方案發(fā)展了新的ws-NIZK 證明系統(tǒng), 包括one-out-of-many 的證明系統(tǒng)ESS+19[26]和ESL+19[25](適用于自組織的群成員關系證明), 以及證明自同構不變點的證明系統(tǒng)PLS18[34](適用于有管理員的群成員關系證明). 這些新型證明系統(tǒng)極大提升了格基類群簽名的實際效率, 達到或接近了實用化需求.

通用性方面, 基于格的ws-NIZK 證明系統(tǒng)僅適用于非常有限的語言. 弱可靠性在密文正確性證明和數(shù)字簽名持有證明等常見應用中缺乏明確的意義. 基于ws-NIZK 的群簽名方案中, 密文正確性證明需要額外的技術才能完成. 動態(tài)群簽名所需要的數(shù)字簽名持有證明難以通過ws-NIZK 證明系統(tǒng)實現(xiàn), 導致動態(tài)群簽名難以通過ws-NIZK 證明系統(tǒng)構造. 實際效率方面, 部分良好設計的ws-NIZK 證明系統(tǒng)非常高效, 可以滿足特定應用下的實用化需求.

3.2.1 基于MV03 和FSwA 的類群簽名方案

MV03 證明系統(tǒng)是由Micciancio 和Vadhan 于CRYPTO 2003 提出的零知識證明系統(tǒng)[60], 可以證明GapCVP 等格上最壞情況的困難問題. FSwA 證明系統(tǒng)由Lyubashevsky 于Asiacrypt 2009[61]和Eurocrypt 2012[55]提出并發(fā)展, 其設計思想與基于離散對數(shù)的Schnorr 協(xié)議[62]類似, 它允許證明者證明自己持有ISIS 問題的證據(jù), 即持有某個短向量x 滿足A·x = y(modq)∧//x//≤β, 其中A 和y 為公開的矩陣或向量, β 是公開的數(shù)值. MV03 證明系統(tǒng)的單次執(zhí)行允許惡意證明者以1/2 的概率欺騙驗證者(soundness error 等于1/2), 因此需要至少λ 次重復執(zhí)行協(xié)議才能保證惡意證明者成功欺騙的概率是可忽略的(λ 為安全參數(shù)), 效率較低. FSwA 證明系統(tǒng)單次執(zhí)行即可保證soundness error 為可忽略的, 效率明顯優(yōu)于MV03. 事實上, MV03 證明系統(tǒng)僅被使用于非常早期的群簽名方案.

據(jù)文獻[63] 分析, MV03 和FSwA 證明系統(tǒng)只能滿足弱可靠性, 即證明者對自己持有短向量x 滿足ISIS 的實例(A,y,β) 的證明, 實際上只能確保證明者知道//x′//≤β′滿足A·x′= cy, 其中β′> β,c > 1. FSwA 的這一缺點也進一步限制了它在證明密文正確性等需要精確的可靠性場景下的使用. 受限于MV03 和FSwA 可證明的語言類型, 相應的環(huán)簽名方案只能做到簽名大小與環(huán)的規(guī)模線性相關, 而群簽名需要借助格的特殊陷門函數(shù)才能完成密文正確性的證明.

基于FSwA 證明系統(tǒng)的環(huán)簽名方案. 早期的格基環(huán)簽名方案[64]可以視作是經(jīng)典的CDS 機制[43]在格密碼中的應用. CDS 機制是指Cramer、Damg?rd 和Schoenmakers 于CRYPTO 1994 上提出的一種按照OR 關系組合Sigma 協(xié)議機制. 具體的, 若對于某個NP 語言L, 存在滿足特定條件的協(xié)議Σ 可以證明x ∈L, 那么經(jīng)由CDS 機制可以得到一個新的協(xié)議ΣOR來證明x1∈L ∨···∨xN∈L. 如果Σ協(xié)議是身份認證協(xié)議, 則ΣOR可經(jīng)過Fiat-Shamir 轉換[65]得到環(huán)簽名方案. 使用CDS 機制, Melchor等人[64]將基于FSwA 的格基身份認證協(xié)議[55]為環(huán)簽名方案. 該環(huán)簽名方案和所有經(jīng)由CDS 機制構造的環(huán)簽名方案一樣, 簽名大小和環(huán)的規(guī)模線性相關.

類似的構造方法也被應用與設計格基可鏈接環(huán)簽名方案. Baum、Lin 和Oechsner 的方案[66]與Torres 等人的方案[67]非常類似. 他們的方案可以視作是基于離散對數(shù)的可鏈接環(huán)簽名方案[10]在格上的遷移. 他們首先設計FSwA 協(xié)議證明用于實現(xiàn)鏈接性的向量是用簽名者的私鑰誠實生成的, 再利用CDS機制隱藏簽名者的公鑰, 經(jīng)由Fiat-Shamir 轉換后形成可鏈接環(huán)簽名. 這兩個方案簽名大小和環(huán)的規(guī)模成線性關系, 主要應用考慮的是匿名數(shù)字貨幣等環(huán)規(guī)模較小的場景. 需要指出的是, 這兩個方案所實現(xiàn)的可鏈接性為一次可鏈接性, 即任意兩個由同一私鑰產(chǎn)生的簽名可以被公開鏈接. 一次可鏈接性與標準的基于標簽(Tag-based) 的可鏈接性[68]有嚴格的區(qū)別. 從應用角度, 一次可鏈接性足夠匿名數(shù)字貨幣的使用需求. 從技術角度, 實現(xiàn)基于標簽的可鏈接性需要引入偽隨機函數(shù)作為組件, 并用零知識證明系統(tǒng)來保證偽隨機函數(shù)的正確執(zhí)行[68]. 這樣的證明任務難以通過FSwA 完成.

基于FSwA 和MV03 證明系統(tǒng)的群簽名方案. 由于MV03 和FSwA 難以直接證明密文的正確性, 早期的格基群簽名構造不得不依賴特殊的代數(shù)結構來降低需要證明的關系的復雜度. 最早的基于格的群簽名方案由Gordon、Katz 和Vaikuntanathan[22]提出. 在該方案中, 他們提出了帶陷門的正交格(orthogonal lattice with its trapdoor) 這一概念及其采樣方法. 給定矩陣B, 可以生成矩陣(A,T) 使得A·B = 0(modq) 及T 是A 的陷門[64]. A1,··· ,AN作為N 個用戶的分別的公鑰. 如果編號為j 的用戶需要對消息M 簽名, 則可以利用對應的陷門Tj可以生成一個短向量ej滿足Aj·ej=H(M), 再求解線性方程組生成ei,i ?= j 滿足Ai·ei= H(M). 然后加密每個ei,i ∈[N] 得到ci= Bi·si+ei. 該加密方案的安全性可以歸約到格上的容錯學習問題(learning with errors, LWE)[69]. 由于Bi和Ai是正交矩陣, 因此驗證者可以很輕易的驗證Ai·ci=0+Ai·ei=H(M). 唯一需要證明的是至少有一ci對應的ei是一個短向量. 這樣的證明系統(tǒng)可以結合MV03 證明系統(tǒng), CDS 機制, 以及Fiat-Shamir 轉換[65]來實現(xiàn). 安全性上, Gordon 方案提供的匿名性為抗選擇明文攻擊的匿名性, 即攻擊者不具備獲得任意指定簽名的簽名者身份的能力. 效率上, Gordon 方案中簽名的大小和群成員個數(shù)線性相關, 并且由于使用了特殊的代數(shù)結構導致系統(tǒng)參數(shù)巨大, 實際效率也無法應用于真實場景. Camenisch、Neven 和Rückert 對此方案進行了改進[70], 實現(xiàn)了具備完全匿名性的格基群簽名方案, 且可以保護誠實的用戶不被管理員惡意指控,但是構造上仍然依賴于正交格陷門和MV02 協(xié)議, 效率沒有明顯提升.

第一個基于格的對數(shù)級的群簽名方案由Laguilaumie 等人[23]提出. 該方案將用戶的身份編碼為?比特的字符串id = id[1]···id[?] ∈{0,1}?, 并使用Boyen[71]提出的格基簽名方案來為用戶生成證書. 在Boyen[71]的簽名方案中, 簽名是一個陷門矩陣而非短向量, 獲得簽名的用戶可以利用這個簽名來生成自己的臨時憑證x. 對消息M 進行簽名時, 用戶需要對所有的j ∈[?] 逐項加密x·id[j], 再證明密文是對x 的加密(對應id[j] 為1) 或者0 (對應id[j] = 0) 的加密. 因為? 比特的身份編碼最多有2?個, 因此群成員最多有2?個. 簽名的大小與群成員個數(shù)成對數(shù)關系. 然而, 該方案在證明密文屬性的時候仍然依賴于Gordon 等人[22]提出的帶陷門的正交格, 因此產(chǎn)生的群簽名的實際大小仍然非常巨大. Laguilaumie 等人在隨后的工作中提出了支持了驗證者本地撤銷的格基群簽名方案[27], 但此方案的效率相比不支持本地撤銷的方案[23]沒有提升. Nguyen、Zhang 和Zhang[72]利用Agrawal 等人在基于格的身份基加密[73]方案中提出的身份編碼技術, 來編碼群簽名中的用戶身份, 并基于FSwA 證明系統(tǒng)來完成對方案中密文正確性的證明. 由于使用了更緊致的身份編碼, Nguyen 等人的方案較Laguilaumie 等人的方案[23]有所提升,但是仍然依賴Gordon 等人[22]提出的陷門函數(shù). 根據(jù)文獻[74] 的測試, 在群成員總數(shù)為210時, Nguyen等人的方案的簽名大小為500 MB, 私鑰大小為90 GB. 上述群簽名方案用戶的密鑰均是在系統(tǒng)啟動階段由群管理員生成, 用戶無法動態(tài)加入, 因此上述方案為靜態(tài)群簽名方案.

3.2.2 PLS18 的群簽名方案

在CCS 2018 上, Pino、Lyubashevsky 和Seiler[34]充分利用了環(huán)的代數(shù)結構來設計群簽名方案. 對于分圓環(huán)Rq= Z/(Xd+1), 存在多個元素可以在對應分圓數(shù)域的Galois 自同構映射下保持不變. Pino等人針對這種自同構不變性, 設計了一種高效格基NIZK 證明系統(tǒng), 證明某個承諾值屬于自同構下的不變點. 將所有的不變點視作群元素, 該零知識證明協(xié)議可以用于證明群成員關系. 技術上, 該證明系統(tǒng)與FSwA 證明系統(tǒng)類似, 單次執(zhí)行即可實現(xiàn)可忽略的soundness error, 但也僅滿足弱可靠性. 為了證明密文是正確生成的, Pino 等人使用了Lyubashevsky 和Neven 在Eurocrypt 2017 上提出的可驗證加密技術[75]. 結合可驗證加密與新的群成員關系證明系統(tǒng), Pino 等人提出了基于模SIS 和模LWE 問題[76]的群簽名方案. 該方案是目前最高效的格基群簽名方案, 簽名大小僅為580KB 左右, 所有操作都可以在0.5秒以內完成. 但由于環(huán)中的不變點是在系統(tǒng)啟動階段就已經(jīng)確定的, 如何利用該證明系統(tǒng)來設計動態(tài)群簽名方案和環(huán)簽名方案尚不清晰.

3.2.3 ESS+19 和ESL+19 的環(huán)簽名方案

經(jīng)典密碼體制下Groth 和Kohlweiss[8]設計基于離散對數(shù)困難問題設計了簽名大小與環(huán)的規(guī)模成對數(shù)關系的環(huán)簽名方案. 該環(huán)簽名方案的核心構造是一種新的one-out-of-many 的零知識證明協(xié)議: 證明N 個承諾{ci}i∈[N]的某個承諾值的消息為0. FSwA 證明系統(tǒng)與基于離散對數(shù)的Schnorr 協(xié)議的相似性揭示了將更多的基于離散對數(shù)的協(xié)議遷移到格基協(xié)議的可能, 也啟發(fā)研究人員思考如何利用Groth 和Kohlweiss 的設計方法來構造高效格基環(huán)簽名. 在ACNS 2019 上, Esgin 等人[26]等人解決了將Groth和Kohlweiss[8]設計思想遷移到格上的若干問題, 設計了基于模格上[76]的SIS 問題的one-out-of-many協(xié)議, 并構造了具有對數(shù)級簽名大小的環(huán)簽名方案ESS+19. 該one-out-of-many 協(xié)議的soundness error為1/poly, 需要多次重復執(zhí)行協(xié)議才能實現(xiàn)可忽略的soundness error. 在CRYPTO 2019 上, Esgin 等人[25]解決了該問題, 實現(xiàn)了單次執(zhí)行即可保證可忽略的soundness error. 他們將該證明技術提煉為適用于非線性多項式關系的零知識證明技術, 并發(fā)展了基于環(huán)中國剩余定理的批處理技術, 進一步降低此類零知識證明的通信復雜度, 提高效率. Esgin 等人[26]也利用這一新型技術對他們之前提出的環(huán)簽名方案[26]進行了重構, 得到了基于模格上困難問題的環(huán)簽名方案ESL+19. 對210規(guī)模的環(huán), 該方案的簽名大小僅為100KB 左右, 是目前適用于大規(guī)模環(huán)的效率最高的后量子安全環(huán)簽名方案.

3.3 基于ss-NIZK 證明系統(tǒng)的類群簽名方案

現(xiàn)有基于格的ss-NIZK 證明系統(tǒng)包括Stern 類協(xié)議[77]和YAZ+19 證明系統(tǒng)[33]. Stern 類協(xié)議和YAZ+19 證明系統(tǒng)的通用性強, 可以證明格密碼學中常見的一大類語言, 可以構造類群簽名的各種功能變種. 但Stern 類協(xié)議單次執(zhí)行的soundness error 為2/3, 需要多次重復執(zhí)行才能實現(xiàn)可忽略的soundness error, 根本上限制了基于Stern 類協(xié)議的類群簽名的效率. YAZ+19 可以視作Stern 類協(xié)議的改進版本,單次執(zhí)行的soundness erro 為多項式的逆, 需要重復執(zhí)行的次數(shù)顯著降低. 二者都無法通過單次執(zhí)行實現(xiàn)可忽略的soundness error, 在特定應用上效率明顯低于某些ws-NIZK 證明系統(tǒng).

3.3.1 基于Stern 類協(xié)議的類群簽名方案

Stern 類協(xié)議最早由Stern 提出并用于設計基于編碼理論的身份認證協(xié)議[77], 而后被Kawachi、Tanaka 和Xagawa 引入到格密碼學中用于構造基于格的身份認證協(xié)議[78]. Ling 等人[63]改進了Kawachi 等人的工作, 使得Stern 類協(xié)議可以“精確地” 證明ISIS 問題(與FSwA 不同). 此后, Stern 類協(xié)議被廣泛地用于設計基于格的類群簽名方案,Stern 類協(xié)議的設計技巧也在應用中不斷發(fā)展. 目前Stern類協(xié)議可以證明符合如下形式的NP 關系[74]: RS:= {(A ∈Zn×dq,v ∈Znq,V ?{?1,0,1}d);x : A·x =v mod q,x ∈V}. 使用Libert、Ling、Nguyen 和Wang 等人提出并發(fā)展的若干技巧[24,30,74], 格密碼學中常見的密文結構關系和簽名消息對關系等都可以轉換為上述形式, 從而可以使用Stern 來協(xié)議來證明此關系. Stern 類協(xié)議的發(fā)展豐富了格密碼學工具庫, 使得大量此前不知道如何基于格構造的密碼學原語第一次有了基于格的具體構造.

需要指出的是, 盡管Stern 類協(xié)議功能強大, 基于Stern 協(xié)議的類群簽名方案的效率距離實際應用仍然有較大距離. 這是由于Stern 類協(xié)議單次執(zhí)行的soundness error 為2/3, 為了使soudness error 下降到可忽略為一個可忽略的值如2?128, 需要重復執(zhí)行Stern 協(xié)議200 次以上. Stern 類協(xié)議的這一特性是基于此類協(xié)議的簽名方案無法進一步提高效率的主要原因.

基于Stern 類協(xié)議的環(huán)簽名方案. 在Eurocrypt 2016 上, Libert 等人基于Stern 類協(xié)議設計了簽名大小與環(huán)規(guī)模成對數(shù)關系的環(huán)簽名方案[74], 解決了格基緊致環(huán)簽名構造這一公開難題. 在經(jīng)典密碼體制下, 緊致的環(huán)簽名方案通常需要依賴累加器這種特殊結構. 累加器可以視作是對集合的承諾方案, 且具備緊致的成員關系證明方式. 已知的累加器分為三類, 包括基于Strong RSA 假設的累加器[79], 基于雙線性對的累加器[80], 以及基于Merkle 樹的累加器[45]. Libert 等人[74]使用基于SIS 困難問題的[53]雜湊函數(shù)構建了墨克樹(Merkle tree)[45]作為基于格的的累加器方案, 再針對該累加器設計了Stern 類型[77]的零知識證明協(xié)議. 對于墨克樹中的葉子節(jié)點, 它到根節(jié)點的路徑可以作為該葉子節(jié)點屬于該墨克樹的證據(jù),而該證據(jù)的大小和葉子節(jié)點的總數(shù)成對數(shù)關系. 這也是Libert 等人的方案可以實現(xiàn)對數(shù)級簽名大小的根本原因.

Stern 類協(xié)議作為核心組件被用于設計一些環(huán)簽名的變種方案. Yang 等人[29]在Libert 等人[74]提出的格基環(huán)簽名方案基礎上設計了基于格的可鏈接環(huán)簽名方案. 在CT-RSA 2020 上, 筆者[32]提出了可追蹤環(huán)簽名的通用設計框架, 并基于Stern 類協(xié)議構造了格基可追蹤環(huán)簽名方案.

基于Stern 類協(xié)議的群簽名方案. Ling、Nguyen 和Wang[81]發(fā)展了Stern 協(xié)議[63], 使得群簽名方案中的密文正確性可以通過Stern 協(xié)議證明, 從而擺脫了對Gordon 等人[22]提出正交格基陷門的依賴,而僅使用標準的格陷門函數(shù)[54]. 相比于之前基于正交格基陷門的群簽名方案, 該方案的安全假設更弱, 并且可以很容易地構造基于環(huán)SIS 和環(huán)LWE 的版本[82]. 基于環(huán)LWE 和環(huán)SIS 的方案通常比基于標準LWE 和標準SIS 的方案更加高效, 但此前的群簽名方案所使用的正交格陷門缺乏基于環(huán)的構造方法.

Libert 等人[74]采用拓展環(huán)簽名的方式來構造靜態(tài)群簽名方案. 他們所拓展的環(huán)簽名方案也即上文介紹的基于Merkle 樹累加器的環(huán)簽名方案. 他們的群簽名方案的群公鑰可以看做包含所有群成員公鑰的一個固定的環(huán). 在對消息進行簽名時, 簽名者需要加密自己的公鑰, 并證明密文是對環(huán)中某個公鑰的加密.該方案的構造方式移除了對格上陷門函數(shù)的需求, 可以更靈活的設置系統(tǒng)參數(shù). 在此之前的格基群簽名方案都是用了格上的陷門函數(shù)來為群中的用戶生成憑證, 受限于陷門所需的系統(tǒng)參數(shù)選擇, 簽名的實際尺寸都過于巨大[55]. 同時, 由于對應環(huán)簽名方案的簽名大小和環(huán)規(guī)模成對數(shù)關系, 該方案的簽名尺寸也是對數(shù)級的. 根據(jù)Libert 等人自己的測試結果, 該方案在群成員為210時, 簽名大小為60 MB 左右, 較之前GB級的簽名大小有顯著提升.

利用Stern 協(xié)議, Libert 等人[24]在Asiacrypt 2016 上構造了第一個基于格的動態(tài)群簽名方案. 該構造的關鍵是設計零知識證明協(xié)議證明密文對應的明文是合法的格基數(shù)字簽名[83]. 在ACNS 2017 上,Libert 等人[30]拓展了文獻[74] 提出的累加器方案, 使其支持加入和撤銷等動態(tài)操作, 從而得到了第一個基于格的全動態(tài)群簽名方案. 此工作后, 大量的具有不同安全特性或者功能特性的格基群簽名方案被提出, 包括具有前向安全性的群簽名方案[84]、支持對開啟機構行為審計的群簽名方案[85]、支持層次結構的群簽名方案[86]和多群簽名方案[87]. Ling 等人[31]為Ducas 和Micciancio[88]的數(shù)字簽名方案設計零知識證明協(xié)議, 支持證明持有該方案合法的消息簽名對, 從而構造出了第一個基于格的常數(shù)級群簽名方案.這也是目前漸進效率最優(yōu)的格基群簽名方案.

3.3.2 基于YAZ+19 證明系統(tǒng)的類群簽名方案

在CRYPTO 2019 上, Yang 等人[33]提出了一種新的格基零知識證明系統(tǒng)YAZ+19. 功能方面, 該證明系統(tǒng)與Stern 類協(xié)議接近, 可以證明格密碼學中常見的一大類NP 語言, 并具備標準的可靠性. 效率方面, 該證明系統(tǒng)單輪執(zhí)行的soundness error 僅為1/poly, poly 代表安全參數(shù)的多項式. 該數(shù)值小于Stern 類協(xié)議的soundness error 2/3, 將soundness error 降低到可忽略的大小所需要的重復次數(shù)也隨之少于同等安全參數(shù)下Stern 類協(xié)議所需重復次數(shù), 因此該證明系統(tǒng)效率較Stern 類協(xié)議有顯著提升.

YAZ+19 證明系統(tǒng)設計上結合了FSwA 和Stern 類協(xié)議的優(yōu)點. 對于需要證明的ISIS 問題(A,y;x),該證明系統(tǒng)首先采用類似于FSwA 的方式, “寬松地” 證明存在向量x′滿足A·x′= cy mod q, 再采用類似于Stern 類協(xié)議的方式“精確地” 證明存在向量x ∈{?1,0,1}n滿足x′= cx. 結合兩者的優(yōu)點,YAZ+19 實現(xiàn)了精確證明和更小的soundness error.

Yang 等人[33]使用該證明系統(tǒng)對基于Stern 類協(xié)議的類群簽名方案[74]進行了全面的升級, 得到的類群簽名方案是目前基于標準格效率最優(yōu)的方案. 值得一提的是, Bootle、Lyubashevsky 和Seiler[89]也在CRYPTO 2019 上發(fā)表了他們關于新型格基零知識證明系統(tǒng)的工作. 他們的證明系統(tǒng)設計方法和效率與YAZ+19 接近, 但他們并沒有將該證明系統(tǒng)應用到類群簽名的設計中, 在此不再展開介紹.

3.4 基于變色龍Hash 的環(huán)簽名方案

在ACNS 2019 上, Lu、Au 和Zhang 提出了適用于小規(guī)模環(huán)的實用格基環(huán)簽名方案Raptor[90].與第三代的其他工作不同, Raptor 取得的效率提升并非是來源于新型零知識證明協(xié)議, 而是來源于環(huán)簽名方案的新設計框架. Lu 等人深入分析了Rivest、Shamir 和Tauman 提出第一個環(huán)簽名通用構造框架RST01[4], 提煉出了RST01 框架實際上所需要的密碼組件, 即增強變色龍雜湊函數(shù)(chameleon hash plus, CH+). 他們基于標準格和NTRU 格分別構造了CH+, 并在此基礎上構造了格基環(huán)簽名方案. 與RST01 框架的其他環(huán)簽名一樣, Lu 等人的方案中簽名大小與環(huán)的規(guī)模線性相關, 因此更適用于小規(guī)模環(huán)的情況. 他們的實現(xiàn)測試結果說明該方案對于規(guī)模較小的環(huán)(例如由5 個公鑰構成的環(huán)) 效率可以滿足實用需求(對應簽名大小為6.3 KB).

Lu 等人也提出了一種新的一次可鏈接環(huán)簽名設計方法. 他們的方案區(qū)別于Franklin 和Zhang[68]提出的構造方法, 通過在環(huán)簽名中附加一次性簽名的方法來實現(xiàn)同一私鑰產(chǎn)生的不同簽名的可鏈接性.Wang、Chen 和Ma[91]總結并推廣了此種可鏈接環(huán)簽名設計技巧.

3.5 具體效率

本文結合安全假設、具體功能和應用場景等指標, 在表1 中總結了其中最高效的格基類群簽名方案.

表1 格基類群簽名方案具體效率Table 1 Performance of group signatures and ring signatures from lattices

4 基于對稱密碼原語的類群簽名方案

基于對稱密碼原語構造隨機預言機模型下的類群簽名并非理論上的難題. 在FOCS 1990 上, Feige等人基于單向函數(shù)構造了Sigma 協(xié)議可以證明哈密頓回路問題[46]. 由于哈密頓回路問題是NPC 問題,所有NP 語言的實例都可以轉換為該問題的一個實例, 因此該Sigma 協(xié)議可以證明任意的NP 語言. 將Fiat-Shamir 轉換應用于該Sigma 協(xié)議可以得到隨機預言機模型下的通用非交互零知識證明系統(tǒng), 其安全性僅依賴于單向函數(shù)的困難性. 基于對稱密碼學原語的環(huán)簽名方案可以通過結合基于單向函數(shù)的承諾方案和該通用NIZK 證明系統(tǒng)直接得到, 具體的構造方法可以視作是對文獻[92] 提出通用構造的實例化.基于對稱密碼學原語的群簽名方案略顯復雜, 不能通過實例化Bellare 等人的通用框架得到[5]. 根據(jù)文獻[41] 的結論, 完全匿名的群簽名方案必須依賴公鑰加密, 而基于對稱密碼學原語設計的群簽名方案所能實現(xiàn)的最佳匿名性為無私匿名性(selfless anonymity), 嚴格弱于標準的全匿名性定義. 二者的區(qū)別在于完全匿名性允許攻擊者獲取全體用戶的私鑰, 而無私匿名性要求誠實用戶的私鑰始終保密.

近年來, 基于對稱密碼學原語的高效零知識證明系統(tǒng)研究取得了突破性進展[36,93], 促進了實用化的基于對稱密碼原語的類群簽名研究. Ishai 等人在此研究方向做出了開創(chuàng)新貢獻[93]. 他們注意到多方計算協(xié)議(multi party computation, MPC) 的安全目標和零知識證明系統(tǒng)的安全目標存在高度相似性, 提出了基于承諾方案的通用轉換框架, 可以將符合一定性質的MPC 協(xié)議轉換為零知識證明系統(tǒng). 在他們提出的通用構造中, 證明者首先將需要證明的關系R(x,w) 作為MPC 協(xié)議要計算的函數(shù), 將證據(jù)w 進行秘密分享, 本地執(zhí)行MPC 協(xié)議各方的所有步驟, 再對每一方的執(zhí)行流程分別承諾并將承諾值發(fā)送給驗證者; 驗證者隨機選取部分承諾要求證明者開啟; 證明者將指定的承諾值對應的各方計算流程作為開啟值提供給驗證者, 驗證者檢驗開啟部分是否正確以及各方計算流程是否兼容. 由于MPC 協(xié)議所有參與方的所有計算均在證明者本地完成, 因此該轉換方法被稱為“MPC-in-the-Head”. Giacomelli、Madsen和Orlandi[36]進一步提煉了Ishai 等人[93]的構造方法, 發(fā)現(xiàn)MPC-in-the-Head 架構下MPC 協(xié)議可以無代價地使用不經(jīng)意傳輸信道(oblivious-transfer channels) 和任何的確定性兩方功能(deterministic two-party functionality), 評估了不同的MPC 協(xié)議轉化為零知識證明系統(tǒng)的實際效率, 將轉換后效率最優(yōu)的零知識證明系統(tǒng)與Fiat-Shamir 轉換相結合, 提出了ZKBoo 證明系統(tǒng). 隨后, Chase 等人[94]對ZKBoo 進行了優(yōu)化, 進一步減少了ZKBoo 系統(tǒng)所產(chǎn)生的證明大小, 提出了ZKB++ 證明系統(tǒng). ZKBoo和ZKB++ 所使用的MPC 協(xié)議是一個可執(zhí)行任意布爾電路的三方協(xié)議, 這兩個證明系統(tǒng)同樣可以用于證明任意布爾電路的可滿足性問題.

在PQC 2018 上, Derler、Ramacher 和Slamanig[37]基于ZKB++ 證明系統(tǒng), 對由雜湊函數(shù)形成的默克爾樹進行成員關系證明, 得到了基于對稱密碼學原語的環(huán)簽名方案. 他們的方案可以看做是Libert等人基于格的環(huán)簽名方案[74]的對稱密碼版本. 在CT-RSA 2019 上, Boneh、Eskandarian 和Fisch[18]同樣利用ZKB++ 證明系統(tǒng)設計了基于對稱密碼學原語的群簽名方案. 由于公鑰加密是實現(xiàn)群簽名完全匿名性的必要條件, Boneh 等人的群簽名方案滿足的匿名性為無私匿名性. 此外, Boneh 等人的群簽名方案將Intel SGX 芯片作為應用場景, 實現(xiàn)了該場景下所需的匿名撤銷等功能. 上述工作在使用ZKB++證明系統(tǒng)作為關鍵組件時, 由于ZKB++ 的計算和通信開銷與電路的乘法復雜度密切相關, 為了充分提升效率他們并沒有采用標準的對稱密碼設計(如SHA256, AES128 等), 而是使用乘法復雜度較低的分組密碼LowMC[95]作為基本組件來設計相應的對稱密碼原語. 根據(jù)具體的應用需求來設計乘法復雜度最低的對稱密碼原語是此類工作的重要組成部分.

由于使用三方協(xié)議作為底層協(xié)議, ZKBoo 和ZKB++ 的單次執(zhí)行都會允許惡意的證明者有2/3 的概率欺騙驗證者. 這一性質與基于格的Stern 證明系統(tǒng)相同. 為了確保惡意證明者欺騙成功的概率是可忽略的, ZKBoo 和ZKB++ 都需要多次執(zhí)行(在128 比特安全性下執(zhí)行次數(shù)為200 次以上), 使得ZKBoo和ZKB++ 產(chǎn)生的證明大小較大. ZKBoo 和ZKB++ 之所以選擇三分協(xié)議作為底層協(xié)議, 是因為Ishai等人提出的框架僅支持兩方功能, 在這一限制下選擇特定的三方協(xié)議實現(xiàn)的效率最高. 在CCS 2018 上,Katz、Kolesnikov 與Wang 將預處理模式引入了MPC-in-the-Head 框架[96], 實現(xiàn)了n 方功能和零知識證明系統(tǒng)安全目標的兼容, 從而允許選擇更高效的n 方協(xié)議, 進一步降低協(xié)議重復執(zhí)行的次數(shù). Katz 等也將他們提出的高效零知識證明系統(tǒng)應用到環(huán)簽名和群簽名的設計中. 相比直接基于ZKB++的群簽名[18]和環(huán)簽名方案[37], Katz 等人的方案效率提升顯著, 是目前基于對稱密碼學原語的最高效的類群簽名方案.具體效率對比見表2, 實驗數(shù)據(jù)來自文獻[96].

基于格上困難問題構造類群簽名和基于對稱密碼學原語構造類群簽名是目前最主流的構造方法. 這兩類構造的安全性根據(jù)不同的評價指標互有優(yōu)劣. 一方面, 基于格的方案的安全性依賴于具體的困難問題假設, 基于對稱密碼學原語的構造在理論上僅依賴單向函數(shù)等基本密碼原語的存在性, 似乎基于對稱密碼原語的方案更為可靠; 另一方面, 基于對稱密碼原語的具體方案出于效率考慮, 使用了尚未廣泛研究的新型分組密碼LowMC, 而基于格的方案可以歸約到格中最壞情況的困難問題, 這個角度來看基于格的類群簽名方案安全性更可靠. 當然, 兩種設計方法并非是對立的. 在PKC 2020 上, Baum 和Nof 改進了Katz等人的設計方法, 提出了新的基于對稱密碼學的NIZK 證明系統(tǒng), 用于證明格上的困難問題SIS[97]. 盡管在該工作中他們并沒有將這一證明系統(tǒng)用于構造群簽名或環(huán)簽名方案, 這一新的證明系統(tǒng)有望有效地結合對稱密碼和格密碼的優(yōu)勢.

表2 基于對稱密碼學原語的類群簽名方案效率Table 2 Performance of group signatures and ring signatures from symmetric-key cryptography primitives

5 從隨機預言機模型到量子隨機預言機模型

隨機預言機模型是形式化證明實用密碼方案安全性的重要證明模型, 最早由Bellare 和Rogway 正式提出[98]. 在隨機預言機模型中, 密碼方案所使用的雜湊函數(shù)被建模為隨機預言機, 敵手只能通過問詢該預言機才能獲得雜湊函數(shù)在特定輸入下的輸出, 且輸出值在像空間均勻隨機分布. 隨機預言機模型有非常廣泛的應用, NIZK 證明系統(tǒng)和數(shù)字簽名構造中使用的Fiat-Shamir 轉換是一種基于隨機預言機的通用轉換框架, 它將公開拋幣(public coin) 的交互式協(xié)議中驗證方發(fā)送的隨機消息替換為隨機預言機的輸出, 從而移除了對交互的依賴.

真實世界中雜湊函數(shù)顯然可以在本地執(zhí)行, 因此擁有量子計算能力的攻擊者具備在量子疊加態(tài)上運行雜湊函數(shù)的能力. 為了真實地反映量子攻擊者的能力, 隨機預言機也應當允許量子疊加態(tài)的問詢——這樣的隨機預言機模型被稱為量子隨機預言機模型. 然而, 允許量子疊加態(tài)問詢這一改動直接導致了經(jīng)典的隨機預言機模型下一些常見的證明技術不再有效. 例如, 隨機預言機模型的安全證明中, 仿真者采用建立詢問-返回表的方式來模擬隨機預言機. 對于已經(jīng)記錄在表中的問詢值, 直接返回對應的輸出值. 對于沒有記錄的新問詢值, 仿真者從輸出空間均勻隨機選取元素作為輸出, 并將它們記錄在表中. 對于量子疊加態(tài)的問詢值, 判斷問詢值是否記錄在表首先要求仿真者對量子疊加態(tài)進行測量, 從而導致仿真失敗. 值得注意的是, 量子隨機預言機模型不僅是讓經(jīng)典的證明技術不可用, 也可能使得原本在隨機預言機模型下證明安全的方案不再安全. 在FOCS 2014 上, Ambainis、Rosmanis 和Unruh[99]排除了Fiat-Shamir 轉換在量子隨機預言機模型下有黑盒安全證明的可能.

目前基于后量子困難假設構造的類群簽名方案大都依賴于Fiat-Shamir 轉換構造. 根據(jù)Ambainis 等人的結論, 這類方案在量子隨機預言機模型下的安全性并不清晰. 針對Ambainis 的結論, 目前有兩類補救措施. 一類是通過對底層的交互式協(xié)議加入特定的限制條件, 使得Fiat-Shamir 轉換在這些限制條件下是安全的, 包括文獻[100–102] 的工作. 另外一類是提出可替換Fiat-Shamir 的在量子隨機預言機模型下可證明安全的通用轉換方法, 包括Unruh 在Eurocrypt 2015 上提出的Unruh 轉換[103]. 現(xiàn)有的類群簽名方案是否滿足若干限制條件從而可以使Fiat-Shamir 在量子隨機語言機模型下安全還需要大量地針對具體構造的討論. 更加通用的方法是將這些方案使用的Fiat-Shamir 轉換替換為Unruh 轉換從而得到量子隨機預言機模型下可證明安全的方案. 需要注意的是, Unruh 轉換的原始安全證明[103]僅適用于滿足標準soundness (2-special soudness) 的Sigma 協(xié)議, 而大部分基于抗量子假設的類群簽名方案所使用的Sigma 協(xié)議滿足k-special soundness (k > 2). Chase 等人[94]證明Unruh 轉換適用于ZKB++ 協(xié)議(k = 3), 筆者在ISC 2019 上[104]提供了補充證明表明Unruh 轉換適用于所有具有k-special soudness的Sigma 協(xié)議(k = poly(λ)). 因此現(xiàn)有的基于Fiat-Shamir 的轉換的類群簽名方案都可以通過Unruh轉換遷移到量子隨機預言機模型下安全的方案.

6 展望與結束語

后量子安全的類群簽名是后量子密碼體系的重要組成部分, 相關研究旨為后量子時代提供實現(xiàn)用戶隱私保護的密碼學工具. 目前已有的研究成果主要基于格上困難問題和對稱密碼學原語兩類抗量子假設, 較好地解決了在標準模型、隨機預言機模型和量子隨機預言機模型下后量子安全的類群簽名及其主要變種的存在性問題. 該領域的研究正在從理論走向實際, 主要研究方向是為各種類群簽名方案提供實用化的后量子安全構造, 同時盡可能提高這些實用化方案的安全性. 該方向還存在若干關鍵問題有待解決, 包括:

(1) 實用化的格基動態(tài)群簽名方案. 動態(tài)群簽名方案允許用戶在系統(tǒng)啟動后動態(tài)加入, 適用于大規(guī)?？裳诱沟膽脠鼍? 經(jīng)典密碼體制下的動態(tài)群簽名方案的群成員關系往往由群管理員的數(shù)字簽名定義, 管理員可以通過為新成員產(chǎn)生簽名的方式使其加入群簽名系統(tǒng). 由于群成員需要后續(xù)證明其持有合法的管理員簽名, 該數(shù)字簽名方案需要在標準模型下可證明安全. 然而, 現(xiàn)有標準模型下格基簽名方案均依賴于格的陷門函數(shù), 參數(shù)過大, 效率低下, 導致相應的動態(tài)群簽名方案并不高效.

(2) 量子隨機預言機模型下高效的類群簽名方案. 在隨機預言機模型西可證明安全的類群簽名方案在量子隨機預言機模型下的安全性缺少嚴格的討論和分析. 盡管大部分現(xiàn)有方案均可以通過替換Fiat-Shamir 轉換為Unruh 轉換實現(xiàn)量子隨機預言機模型下的可證明安全性, 但使用Unruh 轉換會帶來顯著的效率下降. 分析現(xiàn)有基于Fiat-Shamir 轉換的方案在量子隨機預言機模型下的安全性, 以及應用和發(fā)展現(xiàn)有的Fiat-Shamir 的若干結論來設計量子隨機預言機模型下的類群簽名方案, 是解決該問題的可能途徑.