涂彬彬, 陳 宇

1.成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司摩石實(shí)驗(yàn)室, 北京100070

2.山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院, 青島266237

3.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100878

4.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100093

1 引言

對(duì)于密碼系統(tǒng)而言, 密鑰是實(shí)現(xiàn)密碼功能操作的關(guān)鍵, 密鑰的安全保存是密碼系統(tǒng)的安全核心.但是傳統(tǒng)公鑰密碼的密鑰唯一, 密鑰的安全性完全依靠用戶的秘密保存, 一旦用戶的密鑰丟失, 不僅難以恢復(fù),容易形成單點(diǎn)故障導(dǎo)致密碼系統(tǒng)無法正常操作, 甚至惡意敵手在獲得密鑰后, 可任意竊取用戶隱私信息或者偽造用戶身份.從 1979 年, Shamir 和 Blakley 分別獨(dú)立地提出了門限方案, 又稱秘密分享, 門限的思想便深入人心.特別是, Desmedt 和Frankel 等人[1,2]后來引入了門限密碼的概念, 徹底地打開了門限密碼研究的大門.門限密碼通過將密鑰信息分享給多個(gè)用戶分散保存, 密碼功能操作可由至少門限值個(gè)用戶協(xié)作完成, 而且任意少于門限數(shù)量的用戶無法進(jìn)行合謀.一方面提高了系統(tǒng)的健壯性, 即使少量用戶丟失密鑰, 不會(huì)導(dǎo)致密碼系統(tǒng)喪失功能性.另一方面, 提高了系統(tǒng)的安全性, 惡意敵手即使竊取了部分(少于門限值) 用戶的密鑰, 也難以打破密碼系統(tǒng)的安全性.

近些年, 云計(jì)算、分布式計(jì)算以及區(qū)塊鏈等技術(shù)持續(xù)發(fā)展并且廣泛應(yīng)用于互聯(lián)網(wǎng)領(lǐng)域.為了降低或者避免因單個(gè)用戶完全掌握權(quán)限, 導(dǎo)致密鑰丟失、權(quán)限濫用或該用戶被攻擊者控制等安全風(fēng)險(xiǎn), 提升分布式計(jì)算系統(tǒng)的健壯性和安全性, 可將密鑰分配給多個(gè)用戶分散保存, 并要求密碼操作由多個(gè)用戶協(xié)同完成.在傳統(tǒng)公鑰密碼系統(tǒng)中, 由于只有私鑰擁有者具有絕對(duì)權(quán)限, 難以滿足多用戶在分布式環(huán)境下的安全需求.門限密碼系統(tǒng)可看作關(guān)于密碼功能操作(解密/簽名) 的特殊的多方安全計(jì)算, 多個(gè)用戶秘密地分享了密鑰信息, 在進(jìn)行解密/簽名操作時(shí), 用戶可使用自己的私鑰, 通過多方安全計(jì)算的模式多方協(xié)作解密密文/簽名消息, 對(duì)于解決單點(diǎn)故障問題, 以及分布式環(huán)境下多用戶的數(shù)據(jù)安全、隱私保護(hù)和身份認(rèn)證有著重要的應(yīng)用意義.

門限密碼系統(tǒng)主要包括門限加密和門限簽名, 具體形式類似公鑰系統(tǒng)中的加密和簽名.門限加密包括密鑰生成、加密和解密過程, 以及一個(gè)消息組合器(combiner).在解密過程中, 用戶使用自己的私鑰解密密文, 并將解密分享發(fā)送給消息組合器, 消息組合器在接收到門限值個(gè)解密分享時(shí)可組合出原消息.同樣,門限簽名包括密鑰生成、簽名和驗(yàn)簽過程, 以及一個(gè)簽名組合器.在簽名過程中, 用戶使用自己的私鑰簽名消息, 并將簽名分享發(fā)送給簽名組合器, 簽名組合器在接收到門限值個(gè)簽名分享時(shí)可組合出該消息的簽名.如果門限密碼的密鑰生成階段不需要密鑰生成中心, 系統(tǒng)的公鑰和各用戶的私鑰是由用戶自己交互完成, 則可稱該門限密碼是全分布式的(full distributed)[3,4].如果門限密碼的解密/簽名階段, 不需要各用戶之間或者與組合器進(jìn)行交互, 則稱該門限加密/簽名是非交互的(non-interactive)[5,6].

與傳統(tǒng)公鑰密碼相比, 門限密碼有著豐富的功能性、更強(qiáng)的安全模型和特殊性質(zhì).在密碼功能方面, 門限密碼將傳統(tǒng)公鑰密碼操作從以往的單一模式擴(kuò)展到多用戶合作模式.在安全性模型上, 門限密碼除了考慮類似公鑰密碼方案的安全性外, 還要考慮敵手對(duì)于用戶的攻擊, 比如: (1) 弱的攻擊模型——靜態(tài)攻擊模型 (static corruption model).敵手在系統(tǒng)參數(shù)發(fā)布前先選定攻擊的目標(biāo)用戶, 可獲得目標(biāo)用戶的私鑰信息; (2) 強(qiáng)的攻擊模型——自適應(yīng)攻擊模型(adaptive corruption model).敵手可在系統(tǒng)運(yùn)行的任何時(shí)刻,根據(jù)具體的攻擊情況自適應(yīng)地選擇攻擊的目標(biāo)用戶, 獲得目標(biāo)用戶的私鑰信息.除了豐富的功能性和更強(qiáng)的安全性, 門限密碼還具有一些其它特性: (1) 緊致性 (compactness).公鑰尺寸和密文/簽名尺寸與參與用戶的數(shù)量無關(guān).(2) 魯棒性 (robustness).各用戶的解密/簽名分享的正確性可被公開驗(yàn)證.(3) 全分布式.系統(tǒng)的公鑰和用戶的私鑰可由用戶自己通過交互生成, 避免了密鑰生成中心的權(quán)限過大或者被攻擊者控制等帶來的安全風(fēng)險(xiǎn).(4) 抗合謀.門限密碼系統(tǒng)要求參與的用戶數(shù)量達(dá)到門限值, 才能正確完成密碼操作, 防止了單個(gè)用戶失敗導(dǎo)致整個(gè)系統(tǒng)癱瘓, 同時(shí)防止任意少于門限值個(gè)用戶合謀.基于上述良好的性質(zhì), 門限密碼自從誕生以來, 就成為密碼學(xué)領(lǐng)域非常熱門的研究方向, 得到快速的發(fā)展, 并在分布式環(huán)境下的密鑰恢復(fù)[7]、證書認(rèn)證 (certification authorities)、電子投票[8]、密碼貨幣[9]以及多方安全計(jì)算[10]等各方面都有著非常廣泛的應(yīng)用.

本文主要概述了目前門限密碼系統(tǒng)的研究現(xiàn)狀, 分別介紹了門限加密的選擇明文安全和選擇密文安全, 門限簽名的選擇消息不可偽造安全, 以及相關(guān)構(gòu)造方案和主要的構(gòu)造技術(shù).探討了目前門限密碼系統(tǒng)分別在靜態(tài)模型和自適應(yīng)模型下的通用構(gòu)造方法、抗量子安全等方向的發(fā)展趨勢(shì)和依舊存在的問題.

2 門限密碼系統(tǒng)的基本概念

本節(jié)將重點(diǎn)介紹門限加密和門限簽名的基本概念和安全性定義.

2.1 門限加密

門限加密方案(threshold encryption, TE)[11]包括以下4 個(gè)算法:

? KeyGen(λ,n,t): 密鑰生成算法輸入安全參數(shù) λ, 用戶數(shù)量 n 和門限值 t, 輸出公鑰 pk 和用戶私鑰分享 sk=(skid1,··· ,skidn).

? Enc(pk,m): 加密算法輸入公鑰pk 和消息m, 輸出密文c.

? Dec(skid,c): 解密算法輸入任意用戶的私鑰分享skid和密文c, 輸出解密分享cid.

? Combine(cidi1,··· ,cidit): 消息組合算法輸入任意 t 個(gè)解密分享 cidi1,··· ,cidit, 輸出消息 m.

正確性:對(duì)于 (pk,sk) ← KeyGen(λ,n,t), 加密任意消息 m 生成密文 c ←Enc(pk,m), 任意門限值t 個(gè)用戶計(jì)算解密分享 cidij← Dec(skidij,c),j ∈ [t], 則有 m ← Combine(cidi1,··· ,cidit).

安全性:定義靜態(tài)模型下選擇明文攻擊的敵手優(yōu)勢(shì)函數(shù)如下:

其中 Dec(·,Enc(pk)) 是一個(gè)特殊的解密預(yù)言機(jī), 該預(yù)言機(jī)輸入任意用戶的身份 id, 輸出一個(gè)新的密文c ←Enc(pk) 以及該用戶關(guān)于密文c 的解密分享cid←Dec(skid,c).對(duì)于任意概率多項(xiàng)式時(shí)間的敵手A,如果優(yōu)勢(shì)函數(shù)則門限加密是靜態(tài)模型下選擇明文安全的[11].

上述安全性定義都只是針對(duì)靜態(tài)模型下的敵手,這類敵手在系統(tǒng)參數(shù)建立(pk,sk)←KeyGen(λ,n,t)之前, 需要預(yù)先指定最多 t ? 1 個(gè)目標(biāo)用戶攻擊獲得其私鑰信息自適應(yīng)模型下的敵手可以在系統(tǒng)運(yùn)行的任何時(shí)刻自適應(yīng)地選擇最多 t ? 1 個(gè)目標(biāo)用戶攻擊, 并獲得其私鑰信息.

2.2 門限簽名

門限簽名方案(threshold signature, TS)[11]包括以下4 個(gè)算法:

? KeyGen(λ,n,t): 密鑰生成算法輸入安全參數(shù) λ, 用戶數(shù)量 n 和門限值 t, 輸出驗(yàn)證公鑰 vk 和用戶私鑰 sk=(skid1,··· ,skidn).

? Sign(skid,m): 簽名算法輸入任意用戶私鑰skid和消息m, 輸出簽名分享σid.

? Combine(σidi1,··· ,σidit): 簽名組合算法輸入任意 t 個(gè)簽名分享 σidi1,··· ,σidit, 輸出簽名 σ.

? Verify(vk,m,σ): 驗(yàn)證算法輸入驗(yàn)證公鑰 vk, 消息 m 和簽名σ, 當(dāng)簽名驗(yàn)證成功時(shí)輸出1, 否則輸出0.

正確性:對(duì)于 (vk,sk) ←KeyGen(λ,n,t), 任意門限值 t 個(gè)用戶簽名消息 m, 計(jì)算簽名分享 σidij←Sign(skidij,m),j ∈ [t], 獲得簽名 σ ← Combine(σidi1,··· ,σidit), 則有 1 ← Verify(vk,m,σ).

安全性:定義靜態(tài)模型下選擇消息攻擊的敵手優(yōu)勢(shì)函數(shù)如下:

其中敵手可以訪問用戶的簽名預(yù)言機(jī) Sign(·,·), 該預(yù)言機(jī)可輸入任意用戶的身份 id 和消息 m, 輸出該用戶關(guān)于消息的簽名分享 σid← Sign(skid,m).對(duì)于任意概率多項(xiàng)式時(shí)間的敵手 A, 如果敵手優(yōu)勢(shì)函數(shù)則門限簽名是靜態(tài)模型下選擇消息安全的[11].上述安全性定義只針對(duì)靜態(tài)模型下的敵手, 而自適應(yīng)模型下的敵手可以在系統(tǒng)運(yùn)行的任何時(shí)刻自適應(yīng)地選擇最多t ?1 個(gè)目標(biāo)用戶攻擊.

3 門限密碼的發(fā)展及研究現(xiàn)狀

Desmedt 和 Frankel[1,2]等人在研究面向群組的密碼 (group oriented cryptography) 時(shí), 引入了門限密碼的概念.門限密碼具有多用戶的協(xié)作解密/簽名的功能, 在保障群組環(huán)境下的數(shù)據(jù)安全、隱私保護(hù)和身份認(rèn)證等方面, 與傳統(tǒng)公鑰密碼相比, 有著天然的優(yōu)勢(shì).

3.1 門限加密

門限加密通過將私鑰信息分布式地保存在多個(gè)用戶中, 要求少于門限值個(gè)用戶無法成功合謀解密, 只有不少于門限值個(gè)用戶共同解密才能恢復(fù)消息.因此, 構(gòu)造門限加密方案除了需要考慮選擇明文/密文安全外, 還要考慮敵手對(duì)于用戶的攻擊.

3.1.1 選擇明文安全的門限加密

與選擇明文安全的公鑰加密相比, 門限加密的選擇明文安全定義[11]中, 敵手能力更強(qiáng), 可以任意選擇少于門限值個(gè)目標(biāo)用戶進(jìn)行攻擊, 獲得目標(biāo)用戶的解密私鑰.此外, 敵手還能訪問一個(gè)特殊的解密預(yù)言機(jī), 該預(yù)言機(jī)輸入任意用戶的身份, 輸出一個(gè)新的密文和該用戶的解密分享.因此, 構(gòu)造選擇明文安全的門限加密方案, 不僅要考慮泄漏目標(biāo)用戶的解密私鑰, 還要考慮特殊解密預(yù)言機(jī)泄漏用戶解密分享對(duì)于明文不可區(qū)分性的影響.

在 Crypto 1989 上, Desmedt 和 Frankel[2]使用 Shamir 的門限秘密分享技術(shù)[12]分割私鑰, 對(duì)ElGamal 加密方案[13]進(jìn)行門限化, 構(gòu)造了高效的選擇明文安全的門限加密方案.但在安全性證明中, 由于歸約算法(reduction algorithm) 沒有私鑰信息, 無法回答自適應(yīng)敵手關(guān)于目標(biāo)用戶的私鑰詢問.只能在靜態(tài)敵手固定攻擊的目標(biāo)用戶后, 對(duì)系統(tǒng)參數(shù)和目標(biāo)用戶的解密私鑰進(jìn)行模擬, 在靜態(tài)模型下可證明安全.此外, 由于Shamir 的門限秘密分享方案對(duì)于模數(shù)的限制, 該方案只能選擇素?cái)?shù)階群.同時(shí), 因?yàn)樵赗SA加密中參數(shù)?(N) 是偶數(shù), Z?(N)不是一個(gè)域.該問題也導(dǎo)致了無法通過分割RSA 加密方案的私鑰, 構(gòu)造基于RSA 假設(shè)的門限加密方案.

隨后, De Santis 等人[14]在 STOC 1994 上提出函數(shù)分享 (function sharing) 的概念.該密碼組件將單向陷門函數(shù) (one-way trapdoor function) 的陷門進(jìn)行分割, 每個(gè)陷門分享可用于計(jì)算任意函數(shù)像的求逆分享, 并且門限數(shù)量個(gè)求逆分享可以恢復(fù)出原像.函數(shù)分享滿足門限單向性: 任意概率多項(xiàng)式時(shí)間的敵手可以獲得少于門限個(gè)陷門分享, 以及一條包含多項(xiàng)式個(gè)隨機(jī)像的求逆分享的歷史帶(history tape), 卻無法以非可忽略的概率求逆該函數(shù).根據(jù)單向陷門函數(shù)構(gòu)造公鑰加密方案的思想, 基于函數(shù)分享設(shè)計(jì)了選擇明文安全的門限密碼的通用構(gòu)造方法.該方法中, 各參與方分別使用分享密鑰進(jìn)行解密, 并公布自己的解密分享, 門限值個(gè)解密分享可組合出明文.在實(shí)例化方面, 通過擴(kuò)展 Desmedt 和 Frankel[15]的技術(shù), 給出了Shamir 的門限秘密分享的擴(kuò)展版本.該版本可以在任意有限阿貝爾群上進(jìn)行秘密分享, 突破了基于RSA 假設(shè)難以構(gòu)造門限加密方案的障礙, 解決了Desmedt 和 Frankel[2]給出的困難問題, 基于 RSA 假設(shè)實(shí)例化了函數(shù)分享, 并構(gòu)造了選擇明文安全的門限加密方案.

3.1.2 選擇密文安全的門限加密

早期對(duì)于門限加密的研究主要關(guān)注于選擇明文安全, 但是隨著公鑰加密選擇密文安全概念的提出與推廣, 選擇密文安全的門限加密也受到了密碼學(xué)家的廣泛關(guān)注.直觀上, 門限加密的解密過程是多個(gè)用戶以一種安全多方計(jì)算的模式進(jìn)行解密運(yùn)算.因此, 構(gòu)造選擇密文安全的門限加密, 可以直接使用多方安全計(jì)算方法, 將選擇密文安全的公鑰密碼方案門限化.但是該技術(shù)需要各個(gè)解密用戶之間進(jìn)行大量的交互運(yùn)算,效率不高[7,16,17].后來, 選擇密文安全的門限密碼方案構(gòu)造主要在于實(shí)現(xiàn)密文的可驗(yàn)證性[7]或者保證各用戶解密分享的隨機(jī)化[17].隨著選擇密文安全的公鑰加密的設(shè)計(jì)技術(shù)的深入研究, 許多技術(shù)比如基于身份加密轉(zhuǎn)化技術(shù)[6,18,19]、基于可提取哈希證明系統(tǒng)的通用構(gòu)造技術(shù)[11,20,21]對(duì)構(gòu)造選擇密文安全的門限加密有著深遠(yuǎn)影響.

對(duì)于構(gòu)造選擇密文安全的門限加密方案的探索, Lim 和Lee[16]在Crypto 1993 上首先觀察到設(shè)計(jì)選擇密文安全的門限加密, 需要密文可公開驗(yàn)證.在解密階段, 各個(gè)用戶需要先驗(yàn)證密文的合法性, 然后對(duì)密文進(jìn)行解密, 輸出解密分享.如此可保證各用戶解密的密文合法性, 用戶的解密分享不會(huì)影響明文的不可區(qū)分性.該思想對(duì)于后續(xù)構(gòu)造選擇密文安全的門限加密有著非常大的影響.

在Eurocrypt 1998 上, Shoup 和Gennaro[7]給出了非交互的選擇密文安全的門限加密的形式化定義.與門限加密的選擇明文安全相比, 在選擇密文安全中, 敵手擁有更強(qiáng)的攻擊能力, 可獲得任意用戶的解密預(yù)言機(jī).該預(yù)言機(jī)輸入密文和任意用戶的身份, 輸出該用戶的解密分享.基于Lim 和Lee[16]的密文可公開驗(yàn)證思想, 他們使用Chaum-Pedersen 的∑- 協(xié)議[22], 應(yīng)用Fiat-Shamir 啟發(fā)式設(shè)計(jì)的非交互的零知識(shí)證明來保證密文的可公開驗(yàn)證性, 并在隨機(jī)預(yù)言機(jī)(random oracle) 模型下設(shè)計(jì)了首個(gè)可實(shí)踐的選擇密文安全的門限加密方案.

隨后在 Eurocrypt 1999 上, Canetti 和 Goldwasser[17]基于 Cramer 和 Shoup[5]的選擇密文安全的公鑰加密方案, 并在標(biāo)準(zhǔn)模型下將其門限化, 構(gòu)造了選擇密文安全的門限加密方案.方案[5]的密文具有特殊的代數(shù)結(jié)構(gòu), 在解密階段, 當(dāng)密文是有效時(shí), 各用戶的解密分享可正確組合出原消息, 而當(dāng)密文無效時(shí),各用戶的解密分享與隨機(jī)垃圾(random garbage) 不可區(qū)分.因此, 該方案依靠特殊的解密結(jié)構(gòu), 保證了用戶解密錯(cuò)誤的密文,輸出的解密分享具有隨機(jī)性,不會(huì)影響明文的不可區(qū)分性,精巧地避免了使用非交互零知識(shí)證明來保證密文的可公開驗(yàn)證性.但是在解密階段, 該方案需要各用戶之間進(jìn)行交互運(yùn)算并且需要儲(chǔ)存較多的預(yù)共享的秘密(pre-shared secret) 與方案[7]相比, 效率略低.此外, Canetti 和Goldwasser[17]還提出了基于多重加密思想構(gòu)造門限加密方案, 該思想后續(xù)也影響了Zhang 等人[23], Dodis 和Katz[24],以及Xie 等人[25]構(gòu)造門限加密的方法.

公鑰密碼的選擇密文安全的設(shè)計(jì)新思想影響著門限加密的構(gòu)造.Canetti 等人[18]在Eurocrypt 2004上提出了Canetti-Halevi-Katz(CHK)范式, 證明了選擇明文安全的基于身份加密蘊(yùn)含選擇密文安全的公鑰加密.基于該思想, Boneh 等人[6]構(gòu)造了標(biāo)準(zhǔn)模型下非交互的選擇密文安全的門限加密方案.他們首先將Boneh 和Boyen[26]的基于身份加密方案的密鑰生成算法門限化, 設(shè)計(jì)了門限的基于身份加密方案.然后, 將 CHK 范式[18]擴(kuò)展至門限版本, 構(gòu)造了基于雙線性 (Bilinear) Diffie-Hellman 假設(shè)的選擇密文安全的門限加密方案.同樣基于這種轉(zhuǎn)化思想, Bendlin 等人[19]將格上兩類重要的算法 (陷門生成算法和高斯抽樣算法) 門限化, 并對(duì)Gentry 等人[27]的基于身份加密方案門限化, 構(gòu)造了基于格的選擇密文安全的門限加密方案.

對(duì)于選擇密文安全公鑰加密的探索, Wee[20]在 Crypto 2010 上通過高度抽象傳統(tǒng)公鑰密碼的選擇密文安全的設(shè)計(jì)方法, 提煉出非交互零知識(shí)知識(shí)的證明 (Non-Interactive Zero-Knowledge Proof of Knowledge) 的思想, 首次提出了可提取哈希證明系統(tǒng)(extractable hash proof system) 的概念, 并基于可提取哈希證明系統(tǒng)給出了選擇密文安全的公鑰加密的通用構(gòu)造.隨后在Eurocrypt 2011 上, Wee[11]對(duì)該思想擴(kuò)展, 將可提取哈希證明系統(tǒng)門限化, 引入新的密碼組件——門限的可提取哈希證明系統(tǒng)(threshold extractable hash proof systems, TEHPS), 并基于門限的可提取哈希證明系統(tǒng)設(shè)計(jì)了門限加密的通用構(gòu)造方法, 然后分別基于整數(shù)分解假設(shè) (Factoring) 和 DDH 假設(shè)給出具體的實(shí)例化方案.此后, 在 TCC 2012 上, Libert 和 Yung[21]對(duì) Wee 提出的門限可提取哈希證明的思想進(jìn)一步推廣, 引入了 all-but-one perfectly sound threshold hash proof systems (ABO-PS-THPS) 的概念, 給出了自適應(yīng)模型下選擇密文安全的門限加密方案的構(gòu)造, 并分別基于素?cái)?shù)階的雙線性群上的 DLIN 假設(shè)[28]和 symmetric external Diffie-Hellman (SXDH) 假設(shè)[29]實(shí)例化了門限加密方案.

3.2 門限簽名

與傳統(tǒng)數(shù)字簽名相比較, 門限簽名將簽名私鑰分散給多個(gè)用戶, 只有當(dāng)不少于門限值個(gè)用戶協(xié)同簽名,才能完成正確的簽名, 而少于門限個(gè)用戶無法通過合謀簽名.因此, 在構(gòu)造門限簽名時(shí), 不僅要考慮簽名的不可偽造性, 還需要考慮敵手對(duì)于目標(biāo)用戶的攻擊.Desmedt 和 Frankel[15]在 Crypto 1991 上, 設(shè)計(jì)了可在阿貝爾群上運(yùn)算的門限秘密分享方案, 首次基于 RSA 假設(shè)設(shè)計(jì)了門限簽名方案.隨后, 基于不同的密碼假設(shè)的門限簽名方案也相繼被設(shè)計(jì)[11,19,30–34].在 Eurocrypt 2000 上, Shoup[30]采用了消除分母的技術(shù) (clearing out the denominator), 在靜態(tài)模型下基于 RSA 假設(shè)構(gòu)造了非交互的門限簽名方案.徐秋亮[31]首先設(shè)計(jì)了一個(gè)特殊形式的 RSA 簽名體制, 并通過證明所使用的hash 函數(shù)具有強(qiáng)無碰撞性及單向性, 建立了一個(gè)改進(jìn)的門限 RSA 簽名方案, 可完全避免在任何代數(shù)結(jié)構(gòu)中計(jì)算逆元素, 無須作任何代數(shù)擴(kuò)張, 在應(yīng)用中較為高效.在 Asiacrypt 2002 上, Katz 和 Yung[32]對(duì)修改版本的 Rabin 簽名方案[35]進(jìn)行了門限化, 獲得靜態(tài)模型下基于整數(shù)分解假設(shè)的非交互的門限簽名方案.在 Eurocrypt 2011上, Wee[11]基于門限可提取哈希證明系統(tǒng)設(shè)計(jì)了靜態(tài)模型下門限簽名的通用構(gòu)造, 并給出豐富的實(shí)例化.在 ACNS 2013 上, Bendlin 等人[19]將 Gentry 等人[27]的基于格的簽名方案門限化, 設(shè)計(jì)了基于格的門限簽名方案.Boneh 等人[34]提出了門限通用轉(zhuǎn)化器 (universal thresholdizer) 的概念, 并基于該組件可將格上的簽名方案轉(zhuǎn)化成門限版本, 獲得基于格的門限簽名方案.

上世紀(jì)九十年代, 隨著數(shù)字簽名標(biāo)準(zhǔn) (digital signature algorithm, DSA) 的提出和廣泛應(yīng)用.特別是, 近些年密碼貨幣的爆發(fā)式發(fā)展, 基于橢圓曲線的數(shù)字簽名標(biāo)準(zhǔn)(ECDSA) 在比特幣等密碼貨幣中承擔(dān)重要應(yīng)用.而在其中簽名密鑰的丟失也意味著具體經(jīng)濟(jì)的損失.由于比特幣系統(tǒng)中使用了多重簽名的解決方案, 并非門限簽名, 限制了系統(tǒng)的靈活性, 難以支持復(fù)雜的過程結(jié)構(gòu)[36].因此, 對(duì)DSA 進(jìn)行門限化具有重要的應(yīng)用意義.

在門限D(zhuǎn)SA 的研究探索中, 由于簽名算法是概率算法, 對(duì)其門限化需要所有簽名參與方通過交互運(yùn)算共同協(xié)商隨機(jī)數(shù), 導(dǎo)致門限化非常困難.在Eurocrypt 1996 上, Gennaro 等人[3]給出了交互式門限簽名的形式化定義, 并基于聯(lián)合隨機(jī)秘密分享方案(joint random secret sharing, JRSS) 和聯(lián)合零秘密分享方案(joint zero secret sharing, JZSS), 并設(shè)計(jì)了計(jì)算乘積和求逆的多方安全計(jì)算方法, 對(duì)DSA 進(jìn)行門限化, 構(gòu)造了全分布式的門限數(shù)字簽名標(biāo)準(zhǔn).具體而言, 根據(jù) JRSS 技術(shù)協(xié)商出DSA 的簽名驗(yàn)證公鑰和簽名私鑰, 并分別保留私鑰分享.簽名階段, 各參與方使用 JRSS 協(xié)商隨機(jī)數(shù) k 并各自保留隨機(jī)數(shù)分享, 使用多方安全求逆運(yùn)算計(jì)算k?1, 使用多方安全乘積運(yùn)算計(jì)算簽名私鑰與隨機(jī)數(shù)k 的組合, 各參與方可獲得簽名值的分享.最后各參與方公布簽名分享, 達(dá)到門限值即可組合出最終簽名.但是該方案在組合簽名階段, 各用戶需要計(jì)算私鑰與隨機(jī)數(shù)的乘積與隨機(jī)數(shù)的求逆, 導(dǎo)致了多項(xiàng)式的次數(shù)擴(kuò)張.具體而言, 當(dāng)門限值是t 時(shí), 至少需要 2t+1 個(gè)用戶才能組合出簽名.因此, 該方案并非門限最優(yōu)化的, 而且通信消耗非常大,難以應(yīng)用.

在 ACNS 2016 上, Gennaro 等人[9]針對(duì)門限數(shù)字簽名標(biāo)準(zhǔn)的多項(xiàng)式擴(kuò)張問題, 基于 Paillier 的同態(tài)加密方案[37]的門限版本配合陷門承諾技術(shù)(trapdoor commitment)[38], 構(gòu)造了最優(yōu)化的門限數(shù)字簽名標(biāo)準(zhǔn).具體而言, 該方案采用了門限同態(tài)加密技術(shù), 各參與方可以使用同態(tài)加密的性質(zhì)對(duì)于明文進(jìn)行密態(tài)操作, 保證了各方隱私信息的安全性, 并可完成復(fù)雜的簽名運(yùn)算.但是該方案依舊要求各用戶之間進(jìn)行大量的交互運(yùn)算通信消耗較高, 而且簽名算法需要復(fù)雜的零知識(shí)證明.隨后在CCS 2018 上, Gennaro 和Goldfeder[39]對(duì)上述方案進(jìn)行優(yōu)化, 使用了特殊的多方安全計(jì)算技術(shù) (Smart,Pastro,Damg?rd,Zakarias協(xié)議, SPDZ 協(xié)議), 避免了使用復(fù)雜的零知識(shí)證明方法, 設(shè)計(jì)了簡(jiǎn)單的門限 ECDSA 方案.但是該方法依舊使用了 Paillier 的同態(tài)加密方案, 而目前并沒有針對(duì)Paillier 加密方案的高效分布式密鑰生成算法.針對(duì)該問題, 在 CCS 2018 上, Lindell 等人[36]使用指數(shù) (in-the-exponent) ElGamal 的加法同態(tài)算法代替Paillier 的加法同態(tài)加密算法設(shè)計(jì)了首個(gè)高效的門限ECDSA 分布式密鑰生成算法和簽名算法.

在 2010 年底, 我國(guó)國(guó)家密碼管理局發(fā)布了 SM2 橢圓曲線公鑰密碼算法[40], 對(duì)我國(guó)商用密碼產(chǎn)品和信息安全體系建設(shè)具有重大意義.尚銘等人[41]填補(bǔ)了SM2 算法在多方合作應(yīng)用環(huán)境下的空缺, 基于秘密分享的思想, 對(duì)SM2 簽名算法進(jìn)行門限化, 分別針對(duì)存在可信中心和不存在可信中心的情況下, 設(shè)計(jì)門限的 SM2 簽名算法.在門限值為t, 總用戶數(shù)量為 n > 2t 時(shí), 任何2t+1 個(gè)參與者集合可以生成一個(gè)有效的簽名, 安全性分析表明, 該方案可抵抗n/2 竊聽攻擊和n/3 中止攻擊.

3.3 關(guān)鍵應(yīng)用技術(shù)研究進(jìn)展

門限密碼具有比傳統(tǒng)公鑰密碼更加復(fù)雜的安全模型和更加豐富應(yīng)用特性, 僅考慮加密的選擇明文/密文安全或者簽名的選擇消息不可偽造安全難以滿足門限密碼的現(xiàn)實(shí)應(yīng)用需求.在密碼研究領(lǐng)域, 一方面,主要探索基于較弱的密碼組件設(shè)計(jì)密碼方案, 可保證該密碼方案可基于多數(shù)密碼假設(shè)實(shí)例化, 豐富密碼方案的構(gòu)造.另一方面, 在更強(qiáng)的安全性模型下的探索密碼方案的設(shè)計(jì)技術(shù), 可構(gòu)造安全性更強(qiáng)的密碼方案,保證密碼方案具有更強(qiáng)的應(yīng)用適用性.此外, 積極關(guān)注密碼研究新動(dòng)向, 針對(duì)新型密碼分析技術(shù), 構(gòu)造具有針對(duì)性的安全密碼方案, 可保證密碼應(yīng)用的安全性.因此, 針對(duì)門限密碼的關(guān)鍵應(yīng)用技術(shù)研究, 一方面, 需要探索門限密碼的通用構(gòu)造技術(shù), 可根據(jù)不同的底層困難假設(shè)構(gòu)造具體的密碼方案, 提高密碼方案的適用性, 同時(shí)可進(jìn)行模塊化的代碼實(shí)現(xiàn), 提高代碼實(shí)現(xiàn)效率.另一方面, 門限密碼主要應(yīng)用于分布式環(huán)境下多用戶的合作場(chǎng)景.該場(chǎng)景中自適應(yīng)攻擊模型與靜態(tài)攻擊模型相比, 敵手對(duì)于現(xiàn)實(shí)用戶攻擊的更加真實(shí).因此,設(shè)計(jì)自適應(yīng)模型下安全的門限密碼是密碼安全應(yīng)用的關(guān)鍵.此外, 基于傳統(tǒng)數(shù)論假設(shè)的密碼方案難以在量子攻擊下保證安全性, 探索可抵抗量子攻擊的門限密碼方案引起了密碼學(xué)家們的廣泛關(guān)注.不同于傳統(tǒng)數(shù)論假設(shè), 格上的困難假設(shè)被認(rèn)為是可抗量子攻擊的.因此, 基于格構(gòu)造抗量子安全的門限密碼方案也是目前關(guān)鍵的研究方向.

3.3.1 門限密碼的通用構(gòu)造

探索密碼方案的通用構(gòu)造技術(shù)是密碼研究的重要方向.基于較弱的密碼組件設(shè)計(jì)密碼方案的通用構(gòu)造, 可保證該方案能由多數(shù)的底層密碼假設(shè)實(shí)例化.如果當(dāng)構(gòu)造該組件的某個(gè)密碼假設(shè)的安全性受到威脅,或者發(fā)現(xiàn)能更高效地實(shí)例化該組件的密碼假設(shè), 可以及時(shí)替換密碼假設(shè)來保證密碼方案的安全和高效執(zhí)行.此外, 基于密碼組件設(shè)計(jì)密碼方案的通用構(gòu)造技術(shù), 是一種模塊化的構(gòu)造思想, 在密碼方案的代碼實(shí)現(xiàn)方面具有較大的優(yōu)勢(shì).對(duì)于門限密碼系統(tǒng)的通用構(gòu)造技術(shù)的探索, 特別是選擇密文安全的門限加密和選擇消息不可偽造的簽名的通用構(gòu)造技術(shù)的研究一直深受關(guān)注, 其中選擇密文安全的門限加密的通用構(gòu)造方法如圖1 所示, 選擇消息不可偽造的簽名的通用構(gòu)造方法如圖2 所示.

圖1 選擇密文安全門限加密的通用構(gòu)造Figure 1 Generic constructions of CCA-secure threshold encryption

圖2 門限簽名的通用構(gòu)造Figure 2 Generic constructions of threshold signature

對(duì)于探索選擇密文安全的門限加密的通用構(gòu)造技術(shù), Canetti 和 Goldwasser[17]在 Eurocrypt 1999上, 首次基于多重加密 (multiple encryption) 的思想給出了門限加密的通用構(gòu)造方法.在密鑰生成階段,對(duì)每個(gè)用戶生成一組公鑰加密方案的公私鑰對(duì).在消息加密階段, 通過使用Shamir 的門限秘密分享對(duì)加密消息進(jìn)行分割, 使用每個(gè)用戶的公鑰對(duì)每個(gè)消息分享進(jìn)行加密, 密文包含了所有消息分享加密后的結(jié)果.在解密階段, 每個(gè)用戶使用自己的私鑰解密相對(duì)應(yīng)的密文, 獲得對(duì)應(yīng)的消息分享.在組合階段, 組合器接收到門限值個(gè)消息分享, 使用拉格朗日插值公式可恢復(fù)出原消息.隨后, Zhang 等人[23]在 PKC 2004 上,以及Dodis 和Katz[24]在TCC 2005 上基于多重加密的思想, 分別設(shè)計(jì)了靜態(tài)模型下選擇密文安全的門限加密的通用構(gòu)造方法.對(duì)上述方案的進(jìn)一步弱化, Xie 等人[25]發(fā)現(xiàn)文獻(xiàn)[23,24]的構(gòu)造中, 使用的加密組件需要滿足自適應(yīng)選擇標(biāo)簽安全(adaptively chosen-tag secure).他們觀察到該條件并非是必要的, 并對(duì)底層密碼組件進(jìn)行弱化, 使用選擇標(biāo)簽安全(selectively chosen-tag secure) 的基于標(biāo)簽加密(tag-based encryption) 作為加密組件, 結(jié)合強(qiáng)不可偽造安全的一次簽名設(shè)計(jì)了門限加密的通用構(gòu)造, 然后基于有損陷門函數(shù) (lossy trapdoor function)[42]設(shè)計(jì)了基于標(biāo)簽加密的通用構(gòu)造, 最終獲得了靜態(tài)模型下選擇密文安全的門限加密的通用構(gòu)造.但是使用多重加密技術(shù)設(shè)計(jì)的門限加密方案具有天然的缺陷——缺少緊致性, 導(dǎo)致該方案的公鑰尺寸和密文尺寸較大, 與用戶數(shù)量線性相關(guān).

通過擴(kuò)展 CHK 范式[18]構(gòu)造選擇密文安全的公鑰加密的思想, Boneh 等人[6]在 CT-RSA 2006 上給出了門限的基于身份加密可設(shè)計(jì)靜態(tài)模型下選擇密文安全的門限加密的通用構(gòu)造方法, 并基于Boneh和Boyen[26]的身份加密方案給出具體的實(shí)例化.具體而言, 該技術(shù)通過對(duì)基于身份加密的主私鑰進(jìn)行分割, 將基于身份加密的私鑰提取算法門限化, 要求達(dá)到門限值個(gè)參與方合作才能提取用戶的身份私鑰, 形成了門限的基于身份加密方案.然后使用強(qiáng)不可偽造的一次簽名技術(shù), 設(shè)計(jì)了門限加密方案, 并證明了任意選擇身份安全的門限的基于身份加密和強(qiáng)不可偽造一次簽名可構(gòu)造選擇密文安全的門限加密.該方法影響了后續(xù)較多的門限密碼設(shè)計(jì)方法, 包括 Libert 和 Yung[43], 以及 Bendlin 等人[19]構(gòu)造門限密碼方案.

在Eurocrypt 2011 上, Wee[11]通過擴(kuò)展可提取哈希證明系統(tǒng)構(gòu)造選擇密文安全的公鑰加密思想, 提出了門限的可提取哈希證明系統(tǒng), 并基于該組件設(shè)計(jì)靜態(tài)模型下可證明安全的門限加密和門限簽名的通用構(gòu)造方法.具體而言, 門限的可提取哈希證明系統(tǒng)包括兩種模式: 正常模式和t-模擬模式, 并且這兩種模式是統(tǒng)計(jì)不可區(qū)分的.此外, 該系統(tǒng)還包括兩種計(jì)算模式: 公開計(jì)算模式和秘密計(jì)算模式, 并且兩種計(jì)算模式計(jì)算結(jié)果相同.在正常模式下, 加密方可使用系統(tǒng)公鑰, 選擇隨機(jī)數(shù)進(jìn)行加密運(yùn)算, 生成密文.解密時(shí)要求各解密方運(yùn)行秘密計(jì)算模式, 輸入各自的私鑰分享和密文, 計(jì)算解密分享.當(dāng)解密分享達(dá)到門限值時(shí), 可使用抽取算法計(jì)算明文.t-模擬模式可用于輔助安全性證明.Wee 分別基于DDH 假設(shè)和大整數(shù)分解假設(shè)給出該方案豐富的實(shí)例化.該方法為構(gòu)造門限密碼提供了較好的思路, 而且基于單一密碼組件可同時(shí)構(gòu)造多個(gè)密碼方案, 在應(yīng)用實(shí)現(xiàn)上, 可通過模塊化設(shè)計(jì)高效實(shí)現(xiàn).但是 Wee 在設(shè)計(jì)門限可提取哈希證明系統(tǒng)時(shí),只給出了靜態(tài)模型下的形式化定義, 導(dǎo)致只能構(gòu)造靜態(tài)模型下的門限密碼方案, 難以達(dá)到抵抗自適應(yīng)模型下敵手的攻擊.針對(duì)該問題, Libert 和Yung[21]在門限可提取哈希證明技術(shù)的啟發(fā)下, 引入更強(qiáng)的密碼組件ABO-PS-THPS, 并基于該組件給出自適應(yīng)模型下選擇密文安全的門限加密的通用構(gòu)造.

哈希簽名范式(the hash-and-sign paradigm) 是一種經(jīng)典的簽名通用構(gòu)造技術(shù)[44]: 簽名驗(yàn)證公鑰為陷門函數(shù) f, 簽名私鑰為 f?1.在簽名消息 m 時(shí), 首先運(yùn)算哈希算法計(jì)算 y =H(m), 其中 y 是函數(shù) f 的某個(gè)像, 然后計(jì)算簽名值為 σ = f?1(y).驗(yàn)證簽名 (m,σ) 只需要簡(jiǎn)單驗(yàn)證 f(σ) = H(m).隨后, Bellare和Rogaway[45]形式化上述簽名通用構(gòu)造思想, 叫做滿域哈希技術(shù)(full-domain hash), 并證明當(dāng)f 是一個(gè)陷門置換(trapdoor permutation), 哈希函數(shù)H 可模型為隨機(jī)預(yù)言機(jī)(random oracle) 時(shí), 上述簽名方案是選擇消息攻擊不可偽造的.基于滿域哈希技術(shù)設(shè)計(jì)簽名的通用構(gòu)造思想, 衍生出較多的門限簽名算法.

De Santis 等人[14]將陷門函數(shù)門限化, 提出了函數(shù)分享的概念.該組件將陷門函數(shù)的陷門進(jìn)行分割,保證了門限數(shù)量個(gè)陷門分享才可進(jìn)行函數(shù)求逆運(yùn)算, 可完美地將滿域哈希技術(shù)推廣至門限版本, 用于門限簽名的通用構(gòu)造.具體的門限簽名構(gòu)造思想如下: 簽名驗(yàn)證公鑰是函數(shù)描述, 各簽名參與方掌握函數(shù)的陷門分享.在簽名消息 m 時(shí), 首先將 m 哈希運(yùn)算到函數(shù)的某個(gè)隨機(jī)像, 各參與方使用自己的簽名私鑰 (陷門分享) 分別計(jì)算該像的原像分享, 最后通過組合算法可計(jì)算出簽名值(原像).驗(yàn)證簽名類似傳統(tǒng)的滿域哈希技術(shù).最后, 他們基于RSA 假設(shè)實(shí)例化了函數(shù)分享, 獲得了基于RSA 假設(shè)的門限簽名方案.

Wee[11]將滿域哈希技術(shù)進(jìn)一步擴(kuò)展, 在文獻(xiàn)[14]的擴(kuò)展基礎(chǔ)上, 將底層的函數(shù)分享變換為門限可提取哈希函數(shù), 設(shè)計(jì)了門限簽名的通用構(gòu)造.在具體設(shè)計(jì)中, 他同樣使用哈希函數(shù)將消息映射到一個(gè)具體(實(shí)例) 空間, 簽名參與方使用各自的簽名私鑰計(jì)算該消息的簽名分享(實(shí)例的證據(jù)分享), 最后使用提取算法可抽取簽名值(證據(jù)).簽名驗(yàn)證算法可利用證據(jù)驗(yàn)證實(shí)例來證明簽名的正確性.該方案巧妙地將單向關(guān)系(one-way relation) 的可驗(yàn)證性用于門限簽名的驗(yàn)證, 將簽名的選擇消息不可偽造安全性規(guī)約到單向關(guān)系的單向安全性上.

3.3.2 自適應(yīng)模型下的門限密碼

目前多數(shù)的門限密碼方案主要考慮較弱的敵手模型——靜態(tài)攻擊模型.在這種攻擊模式下, 敵手必須在系統(tǒng)參數(shù)公開前就選定攻擊的目標(biāo)用戶, 獲得用戶的私鑰信息.當(dāng)系統(tǒng)參數(shù)公開后, 敵手不再具有攻擊其他用戶的能力, 這種攻擊模型并沒有充分考慮敵手的攻擊能力.在實(shí)際攻擊中, 敵手甚至可以在系統(tǒng)運(yùn)行的任意時(shí)刻選擇攻擊的目標(biāo)用戶, 并根據(jù)獲得的用戶信息來決定下個(gè)目標(biāo)用戶, 這種攻擊模型被稱為自適應(yīng)攻擊模型.自適應(yīng)攻擊模型嚴(yán)格地強(qiáng)于靜態(tài)攻擊模型[46], 更加貼近于現(xiàn)實(shí)中敵手的攻擊形式.因此,構(gòu)造自適應(yīng)模型下的門限密碼方案比靜態(tài)攻擊下更加困難.自適應(yīng)模型下門限密碼構(gòu)造方法如圖3 所示.

圖3 自適應(yīng)模型下的門限密碼Figure 3 Threshold cryptosystem under adaptive corruption model

在Crypto 1999 上, Canetti 等人[4]首先對(duì)構(gòu)造自適應(yīng)模型下安全的門限密碼進(jìn)行探索, 觀察到主要困難點(diǎn)在于模擬器無法提前預(yù)測(cè)敵手準(zhǔn)備攻擊的目標(biāo)用戶.而在可證明安全的角度, 模擬器需要模擬敵手的視角, 才能利用敵手的能力打破具體的底層困難假設(shè).當(dāng)自適應(yīng)的敵手詢問任意用戶私鑰分享時(shí), 模擬器需要掌握所有用戶的隱私信息才能完成模擬, 但是困難問題需要嵌入到用戶的隱私信息中, 模擬器無法獲得全部用戶的隱私信息, 也就無法完成模擬過程.為了突破該困難, Canetti 等人[4]給出了具體的嘗試,他們采用隱私信息擦除技術(shù)(erasures) 配合single inconsistent player 技術(shù), 確保各個(gè)用戶在系統(tǒng)參數(shù)公開前, 擦除自己的隱私信息.因此, 敵手即使攻擊了部分用戶也無法獲得用戶的隱私信息, 保證了模擬器不需要向敵手提供用戶的隱私信息, 并且可高效的模擬敵手的視角.但是隱私信息擦除技術(shù)存在很大的弊端,用戶擦除的隱私信息在系統(tǒng)的后續(xù)過程中無法使用, 而且實(shí)現(xiàn)該技術(shù)本身就存在很多困難[47].為了避免隱私信息擦除技術(shù)難實(shí)現(xiàn)的問題, Jarecki 和Lysyanskaya[48]在Eurocrypt 2000 上采用了承諾證明技術(shù)(committed proof) 配合 persistently inconsistent player 技術(shù), 避免了使用隱私信息擦除技術(shù), 且在并發(fā)復(fù)合(concurrent composition) 下構(gòu)造了自適應(yīng)模型下安全的門限密碼, 但是該方案要求用戶之間進(jìn)行大量的交互運(yùn)算.

Waters 在Crypto 2009 上為構(gòu)造基于身份加密方案, 首次提出了雙系統(tǒng)證明技術(shù)(dual system technique)[49,50], 也為設(shè)計(jì)自適應(yīng)模型下安全的門限密碼提供了新的思路.雙系統(tǒng)證明技術(shù)引入半功能密鑰(semi-functional secret key) 和半功能密文 (semi-functional ciphertext), 用于輔助安全性證明, 但不用于方案構(gòu)造.其中半功能密鑰可以正常解密真實(shí)密文, 半功能密文可以被正常密鑰解密, 但是半功能密鑰不能解密半功能密文.因此, 在敵手的詢問用戶私鑰和構(gòu)造挑戰(zhàn)密文時(shí), 模擬器可以生成半功能密鑰和半功能密文, 并使用半功能密鑰和半功能密文回應(yīng)敵手詢問, 模擬敵手視角.由于半功能密鑰不能解密半功能密文, 敵手拿到了半功能密鑰, 對(duì)解密半功能密文沒有任何幫助.隨后, 基于雙系統(tǒng)證明技術(shù), Libert 和Yung[43]將 Boneh 等[6]的門限基于身份加密轉(zhuǎn)化為門限加密的思想, 根據(jù) Boneh 和 Franklin[51]的身份加密方案, 設(shè)計(jì)了非交互的選擇密文安全的門限加密方案, 并給出了該方案在自適應(yīng)模型下的安全性證明.

在 TCC 2012 上, Libert 和 Yung[21]對(duì) Wee[11]的門限可提取哈希證明的思想進(jìn)行推廣, 引入了密碼組件 ABO-PS-THPS.該組件可看做具有公開可驗(yàn)證 (publicly verifiable) 的可合理模擬證明的(simulation-sound proofs) 門限哈希證明系統(tǒng) (threshold hash proof systems).該組件的每個(gè)證明都與一個(gè)標(biāo)記相關(guān)聯(lián), 具體包含了正常模式和 all-but-one 模式, 且正常選擇的公共參數(shù)和 all-but-one 模式下選擇的參數(shù)不可區(qū)分, 其中正常模式用于方案構(gòu)造, all-but-one 模式用于輔助安全性證明.具體而言,在 all-but-one 模式下非交互證明對(duì)于所有標(biāo)簽都是正確的, 除了在一個(gè)特定標(biāo)記處設(shè)置陷門, 可對(duì)于不正確的實(shí)例進(jìn)行模擬證明.他們基于該組件構(gòu)造了自適應(yīng)模型下選擇密文安全的門限加密方案.在實(shí)例化方面, 利用 Groth-Sahai 證明系統(tǒng)[52]分別基于素?cái)?shù)階的雙線性群上的 DLIN 假設(shè)[28]和 symmetric external Diffie-Hellman (SXDH) 假設(shè)[29]實(shí)例化了門限加密方案.

3.3.3 基于格的門限密碼

隨著量子計(jì)算的快速發(fā)展, 基于傳統(tǒng)數(shù)論假設(shè)的密碼方案的安全性受到量子攻擊的嚴(yán)重威脅, 構(gòu)造抗量子安全的門限密碼方案具有重要的意義.因?yàn)槟壳安淮嬖谟行У牧孔铀惴ù蚱聘裆系睦щy問題, 所以格密碼被認(rèn)為是能夠抵抗量子攻擊的.同時(shí), 格上的運(yùn)算簡(jiǎn)單, 計(jì)算量小, 格密碼與基于傳統(tǒng)數(shù)論假設(shè)構(gòu)造的密碼方案相比, 實(shí)現(xiàn)效率較高.

在 TCC 2010 上, Bendlin 和 Damg?rd[53]首次構(gòu)造了基于 LWE 假設(shè)的選擇明文安全的門限加密方案.具體構(gòu)造思想是基于Regev 的加密方案[54]的變種版本, 采用偽隨機(jī)的秘密分享技術(shù)(pseudorandom secret sharing)[55]切分私鑰, 并根據(jù) Peikert[56]給出的格上歸約方法, 在通用復(fù)合模式 (universal composability)[57]下給出安全性證明.但是該方案使用了特殊的切分消息技術(shù)導(dǎo)致在靜態(tài)模型下, 限制了總用戶的數(shù)量.在自適應(yīng)模型下, 要求各用戶之間存在私密信道, 需要各用戶之間進(jìn)行交互運(yùn)算, 并且該方案要求更大的模數(shù), 密文尺寸較大.

基于多重加密構(gòu)造門限加密的思想, Xie 等人[25]對(duì) Dodis 和 Katz[24]構(gòu)造門限加密的密碼組件進(jìn)行弱化, 基于有損陷門函數(shù)設(shè)計(jì)了靜態(tài)模型下選擇密文安全的門限加密的通用構(gòu)造, 并根據(jù)基于LWE 假設(shè)實(shí)例化的有損陷門函數(shù)[42], 構(gòu)造了選擇密文安全的門限加密方案.但是該方案使用門限秘密共享方案切分消息和多重加密技術(shù), 導(dǎo)致了公鑰和密文尺寸與用戶的數(shù)量線性相關(guān).

Zhang 等人通過對(duì)Brakerski[58]的全同態(tài)加密方案進(jìn)行修改, 摒棄了Gentry[59]的標(biāo)準(zhǔn)壓縮(standard squashing) 和自舉技術(shù) (bootstrapping), 使用重線性化技術(shù) (re-linearization) 大大減少了密文長(zhǎng)度, 使用模量減少 (modulus reduction) 技術(shù)管理了噪聲級(jí)別, 降低了解密復(fù)雜度, 并基于密鑰同態(tài)性(key-homomorphic property), 將該方案擴(kuò)展至門限版本, 可保證多方協(xié)同完成解密.

基于門限的基于身份加密轉(zhuǎn)化技術(shù), Bendlin 等人[19]將格上兩類重要的算法(陷門生成算法和高斯抽樣算法) 門限化, 將Gentry 等人[27]的基于身份加密方案和簽名方案轉(zhuǎn)化成門限版本, 并在通用復(fù)合模式[57]下給出安全性證明, 分別構(gòu)造了基于格的選擇密文安全的門限加密和不可偽造的門限簽名方案.但是該方案在進(jìn)行非交互的解密/簽名過程之前, 需要各用戶之間進(jìn)行大量的交互運(yùn)算.

Boneh 等人[34]根據(jù)全同態(tài)加密方案構(gòu)造低輪數(shù)多方安全計(jì)算的思想[60], 設(shè)計(jì)了 (n,n)-門限密碼,并使用 Shamir 的門限秘密分享將門限值由 n 可轉(zhuǎn)化成 t, 并配合消除分母的技術(shù) (clearing out the denominator) 保證了LWE 的噪聲增長(zhǎng)可被界定.基于上述技術(shù)思想, 他們提出了門限通用轉(zhuǎn)化器(universal thresholdizer) 的概念, 并基于該組件可將格上的加密和簽名方案轉(zhuǎn)化成門限版本, 獲得基于格的門限加密方案和門限簽名方案.但是該方案使用了全同態(tài)加密、多方安全計(jì)算等技術(shù), 導(dǎo)致方案效率不高.

4 門限密碼的研究展望

4.1 自適應(yīng)模型下安全的門限密碼的通用構(gòu)造

目前設(shè)計(jì)選擇密文安全的門限密碼的通用構(gòu)造方法, 主要通過多重加密技術(shù)[4,24,25]、門限的基于身份加密轉(zhuǎn)換技術(shù)[6,19,43]以及門限可提取哈希證明系統(tǒng)技術(shù)[11,21].其中多重加密技術(shù)存在公鑰尺寸和密文尺寸與用戶數(shù)量線性相關(guān)的問題, 門限的身份加密方案本身就比較難以構(gòu)造, 門限可提取哈希證明系統(tǒng)技術(shù)目前只能構(gòu)造靜態(tài)模型下的門限密碼.但是門限可提取哈希證明系統(tǒng)設(shè)計(jì)相對(duì)簡(jiǎn)單, 且同時(shí)可構(gòu)造門限加密和門限簽名方案.因此, 探索基于門限可提取哈希證明系統(tǒng)設(shè)計(jì)自適應(yīng)模型下安全的門限密碼是未來較有意義的工作.此外, 目前門限可提取哈希證明系統(tǒng)可基于 DDH 假設(shè)和整數(shù)分解假設(shè)實(shí)例化, 探索基于其他密碼假設(shè), 尤其是基于格上困難假設(shè)構(gòu)造門限可提取哈希證明系統(tǒng)也具有重要意義.

Boneh 等人[34]基于全同態(tài)加密思想, 提出了門限通用轉(zhuǎn)化器的概念, 可將格上的加密和簽名方案直接門限化, 為構(gòu)造門限密碼提供了新的方向.但是目前方案構(gòu)造只能基于LWE 假設(shè), 而且效率不高.探索基于其他密碼假設(shè)構(gòu)造的高效門限通用轉(zhuǎn)化器, 可豐富自適應(yīng)模型下的門限密碼方案的構(gòu)造.

4.2 基于格的門限密碼的高效設(shè)計(jì)

目前基于格的門限密碼方案較少, 而且存在各種問題.比如: Bendlin 和Damg?rd[53], 以及 Bendlin等人[19]的門限密碼方案需要用戶之間進(jìn)行大量交互運(yùn)算, Xie 等人[25]的門限加密方案只能在靜態(tài)模型下可證明安全, 而且公鑰尺寸和密文尺寸與用戶數(shù)量線性相關(guān), Boneh 等人[34]的構(gòu)造方法需要使用全同態(tài)加密技術(shù), 實(shí)踐效率較低.因此, 基于格上困難假設(shè)在自適應(yīng)模型下構(gòu)造高效的非交互的門限密碼方案是未來需要解決的問題.

4.3 簽名標(biāo)準(zhǔn)算法門限化

由于數(shù)字簽名標(biāo)準(zhǔn)的廣泛應(yīng)用, 對(duì)其高效地門限化具有重要的應(yīng)用意義.但是目前對(duì)于數(shù)字簽名標(biāo)準(zhǔn)的門限化都需要參與簽名的用戶進(jìn)行大量的交互運(yùn)算, 通信消耗非常大, 難以用于實(shí)際應(yīng)用.盡管 Gennaro 等人[9]在ACNS 2016 上設(shè)計(jì)的門限數(shù)字簽名標(biāo)準(zhǔn), 與之前的方案相比, 優(yōu)化了參與簽名的人數(shù), 并減少了用戶之間交互輪數(shù), 但是對(duì)于 (n,n)-門限數(shù)字簽名標(biāo)準(zhǔn), 在簽名階段至少需要用戶進(jìn)行 7 輪交互.如果對(duì)于 (n,t)-門限數(shù)字簽名標(biāo)準(zhǔn), 在簽名階段用戶交互輪數(shù)與門限值線性相關(guān).因此, 構(gòu)造低輪數(shù)交互甚至非交互的門限數(shù)字簽名標(biāo)準(zhǔn)是非常有意義且具有挑戰(zhàn)性的研究工作.

對(duì)于我國(guó)SM2 標(biāo)準(zhǔn)簽名算法的門限化研究, 尚銘等人[41]給出了具體的門限構(gòu)造填補(bǔ)該方向的研究空缺, 但是該方案在簽名階段需要較多的交互輪數(shù), 而且需要2t+1 個(gè)參與方進(jìn)行簽名, 并非達(dá)到門限最優(yōu).因此, 設(shè)計(jì)低輪數(shù)交互, 可達(dá)到門限最優(yōu)化的門限 SM2 簽名算法, 對(duì)于 SM2 標(biāo)準(zhǔn)簽名算法的推廣和應(yīng)用具有重大意義.