基于國密SM2 和SM9 的加法同態(tài)加密方案*

唐 飛, 凌國瑋, 單進(jìn)勇

1. 重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 重慶 400065

2. 重慶郵電大學(xué)網(wǎng)絡(luò)空間安全與信息法學(xué)院, 重慶 400065

3. 北京數(shù)牘科技有限公司, 北京 100083

1 引言

近年來, 人們更加傾向于使用公有云或互聯(lián)網(wǎng)存儲(chǔ)數(shù)據(jù), 進(jìn)而降低存儲(chǔ)成本. 為了實(shí)現(xiàn)用戶數(shù)據(jù)的隱私保護(hù)機(jī)制, 常用的方法是將數(shù)據(jù)加密后再存入數(shù)據(jù)庫中. 然而, 當(dāng)用戶要對(duì)加密的數(shù)據(jù)進(jìn)行相關(guān)計(jì)算, 例如求和、內(nèi)積等, 如果是普通的加密方法, 則用戶需要自己下載數(shù)據(jù)再解密并計(jì)算, 或授權(quán)云服務(wù)提供商獲取原始數(shù)據(jù)從而實(shí)現(xiàn)云計(jì)算服務(wù). 針對(duì)這一問題, Rivest 等人[1]提出了同態(tài)加密的概念, 同態(tài)加密是一種可對(duì)密文進(jìn)行同態(tài)運(yùn)算的加密方案, 即對(duì)密文計(jì)算后再解密可以得到對(duì)原始數(shù)據(jù)直接計(jì)算的結(jié)果, 從而同時(shí)實(shí)現(xiàn)云存儲(chǔ)數(shù)據(jù)的機(jī)密性與用戶的隱私保護(hù)性.

同態(tài)加密方案一般分為全同態(tài)加密和部分同態(tài)加密兩類[2]. 其中, 全同態(tài)加密方案[3]可對(duì)密文進(jìn)行任意的同態(tài)計(jì)算, 部分同態(tài)加密方案只能單獨(dú)對(duì)密文做加法或乘法同態(tài)計(jì)算. 盡管部分同態(tài)加密方案只能支持單一的同態(tài)計(jì)算, 但這類方案的實(shí)現(xiàn)效率往往比全同態(tài)加密方案高很多, 因此具有更高的可用性. 部分同態(tài)加密方案中以加法同態(tài)加密方案最為典型, 已廣泛應(yīng)用于數(shù)據(jù)聚合[4]、多方計(jì)算[5]、聯(lián)邦學(xué)習(xí)[6]、區(qū)塊鏈支付系統(tǒng)[7]等現(xiàn)實(shí)應(yīng)用場(chǎng)景中. 例如, 無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合方案[4]利用加法同態(tài)加密保護(hù)了數(shù)據(jù)隱私, 同時(shí)降低了網(wǎng)絡(luò)帶寬; 智能電網(wǎng)[5]利用加法同態(tài)加密對(duì)用戶電量數(shù)據(jù)進(jìn)行加密, 從而實(shí)現(xiàn)電量的隱私保護(hù)與快速求和計(jì)算; 聯(lián)邦學(xué)習(xí)[6]利用加法同態(tài)加密使得在多方聯(lián)合訓(xùn)練模型的同時(shí)保持原始數(shù)據(jù)不泄露給服務(wù)方.

加法同態(tài)加密方案中若干密文運(yùn)算后的結(jié)果為對(duì)應(yīng)明文之和的密文, 即Enc(m1)?Enc(m2) =Enc(m1+m2). 現(xiàn)有的經(jīng)典加法同態(tài)加密方案均為國外研究人員設(shè)計(jì), 例如Paillier[8]、基于ElGamal[9]的同態(tài)加密方案Exponential ElGamal[10](簡(jiǎn)寫為Exp-ElGamal)、BGN[11]等, 缺乏支持國密標(biāo)準(zhǔn)的加法同態(tài)加密方案. 因此, 在需要同態(tài)加密的應(yīng)用場(chǎng)景中一般都使用上述方案, 尤其是Paillier 方案使用特別廣泛, 例如微眾銀行的FATE 聯(lián)邦學(xué)習(xí)平臺(tái)[12]等均使用Paillier 方案作為其基礎(chǔ)核心組件. 截至目前, Paillier 論文[8]已被引用7762 次(Google 學(xué)術(shù)被引數(shù)據(jù)).

商用密碼是我國自主研發(fā)的密碼標(biāo)準(zhǔn)方案, 常用的商密標(biāo)準(zhǔn)包括 SM2[13]、SM3[14]、SM4[15]、SM9[16]等. 其中, SM2 是普通的公鑰密碼方案, SM9 是基于身份的公鑰密碼(標(biāo)識(shí)密碼) 方案. SM2和SM9 均基于橢圓曲線, 在同等安全強(qiáng)度下相對(duì)RSA[17]、Paillier[8]等類型的公鑰密碼方案而言, 具有密鑰更短、系統(tǒng)參數(shù)更小等優(yōu)點(diǎn), 并且硬件實(shí)現(xiàn)橢圓曲線密碼算法所需邏輯電路門數(shù)要較RSA 類型少得多, 功耗也更低. 目前, 國密系列標(biāo)準(zhǔn)方案已得到廣泛應(yīng)用, 研究者們也基于國密方案構(gòu)造了多種類型的密碼方案, 例如區(qū)塊鏈隱私保護(hù)[18]、多接收方公鑰加密[19]、多方簽名[20,21]、環(huán)簽名[22,23]、門限解密[24]、廣播加密[25]、標(biāo)識(shí)簽密[26]、范圍證明[27]等.

如上所述, 目前缺乏基于國密標(biāo)準(zhǔn)的同態(tài)加密方案, 使得相關(guān)企業(yè)只能采用Paillier 等加法同態(tài)加密方案. 針對(duì)這一問題, 本文基于國密SM2 和SM9 設(shè)計(jì)具有加法同態(tài)性質(zhì)的公鑰加密方案, 本文的主要貢獻(xiàn)如下:

分別基于國密SM2 和SM9 構(gòu)造了加法同態(tài)加密方案和標(biāo)識(shí)加法同態(tài)加密方案. 兩個(gè)方案均兼容原標(biāo)準(zhǔn)方案中的推薦曲線參數(shù)和密鑰生成算法, 僅對(duì)原方案的加解密算法作出調(diào)整, 使新方案在盡可能保留原方案結(jié)構(gòu)的基礎(chǔ)上具備加法同態(tài)性質(zhì). 對(duì)所提方案做安全性與效率分析. 安全性方面, 首先通過與原標(biāo)準(zhǔn)方案的密文形式進(jìn)行對(duì)比, 所提方案與原標(biāo)準(zhǔn)方案具有類似的安全性, 再證明了所提方案具有INDCPA 安全性. 效率分析方面,編程實(shí)現(xiàn)所提方案,并與Paillier[8]、Exp-ElGamal[10]、Twisted-ElGamal[7]方案做對(duì)比分析, 實(shí)驗(yàn)結(jié)果表明所提方案的絕大多數(shù)指標(biāo)均優(yōu)于Paillier、Exp-ElGamal. 其中所提SM2加法同態(tài)加密方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的3/5, Paillier 方案的1/8; SM9 加法同態(tài)加密方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的3/4, Paillier 方案的1/6.

為了降低私鑰泄露導(dǎo)致密碼系統(tǒng)可用性和安全性受損的風(fēng)險(xiǎn), 進(jìn)一步構(gòu)造具有門限解密性質(zhì)的加法同態(tài)方案. 門限解密方案的安全性與一般的基于Shamir 秘密共享[28]的門限解密方案類似, 為基于國密SM2 和SM9 的同態(tài)加密方案的分布式應(yīng)用提供理論支撐.

2 預(yù)備知識(shí)與定義

2.1 橢圓曲線與相關(guān)復(fù)雜性假設(shè)

令p是大素?cái)?shù),E為定義在有限域Fp上的橢圓曲線,G為橢圓曲線的q階基點(diǎn)(xG,yG), 群G 代表以G為生成元生成的橢圓曲線點(diǎn)集. 若x ∈Z?q, [x]G代表橢圓曲線基點(diǎn)G的x倍點(diǎn). 橢圓曲線上的運(yùn)算規(guī)則此處不再贅述.

在SM2 方案[13]中, 推薦的曲線方程為y=x3+ax+b, 建議的參數(shù)a,b分別如下:

a: 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B 6831D7E0 EC65228B 3937E498;

b: 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391 5C45517D 722EDB8B 08F1DFC3.

假設(shè)1離散對(duì)數(shù)(discrete logarithm) 問題. 給定(E,G,p,q) 與群G, 隨機(jī)選擇P ∈G, 計(jì)算一個(gè)隨機(jī)數(shù), 滿足P=[x]G是困難的.

假設(shè)2CDH(computational Diffie-Hellman)問題. 給定(E,G,p,q)與群G, 隨機(jī)選擇[x]G,[y]G ∈G, 計(jì)算[xy]G是困難的.

假設(shè)3DDH(decisional Diffie-Hellman)問題. 給定(E,G,p,q)與群G,隨機(jī)選擇[x]G,[y]G,[z]G ∈G, 判斷z=xy是否成立是困難的.

2.2 雙線性映射與相關(guān)復(fù)雜性假設(shè)

令G1,G2為階為大素?cái)?shù)N的加法循環(huán)群, GT為階為大素?cái)?shù)N的乘法循環(huán)群,P1,P2是G1,G2的生成元, 若x ∈Z?N, [x]Pi代表生成元P1,P2的x倍, 其中i ∈{0,1}, 滿足:

(1)雙線性: 對(duì)任意的a,b ∈ZN,e([a]P1,[b]P2)=e([b]P1,[a]P2)=e(P1,P2)ab;

(2)非退化性:e(P1,P2)?=1;

(3)可計(jì)算性: 存在有效算法能高效計(jì)算雙線性對(duì)e, 如基于Weil 對(duì)[29]的改進(jìn)算法.

在SM9 方案[16]中, 群G1,G2中元素均為橢圓曲線上的點(diǎn), 曲線方程采用y2=x3+5.

2.3 加法同態(tài)公鑰加密

一個(gè)普通的加法同態(tài)加密方案包含如下四個(gè)算法.

(1)系統(tǒng)建立Setup(1?): 系統(tǒng)建立算法輸入安全參數(shù)?, 輸出公共參數(shù)pp, 包含明文空間M、密文空間C 等系統(tǒng)公開參數(shù)的描述.

(2)密鑰生成KeyGen(pp): 密鑰生成算法輸入系統(tǒng)參數(shù)pp, 輸出用戶公鑰pk 和私鑰sk.

(3)加密Enc(pk,m): 加密算法輸入公鑰pk 與明文m ∈M, 輸出密文c ∈C.

(4)解密Dec(sk,c): 解密算法輸入私鑰sk 與密文c ∈C, 輸出m ∈M; 否則輸出⊥, 代表解密失敗.方案具有如下三個(gè)性質(zhì).

(1)正確性. 對(duì)于所有pp←Setup(1?), (pk,sk)←KeyGen(pp),c ←Enc(pk,m), 均有m ←Dec(sk,c).

(2)同態(tài)性. 所有pp←Setup(1?), (pk,sk)←KeyGen(pp), 對(duì)于任意兩個(gè)密文c1←Enc(pk,m1),c2←Enc(pk,m2), 均有c1?c2=Enc(pk,m1+m2).

(3)安全性. 加法同態(tài)公鑰加密方案的安全性要求敵手無法從密文得到關(guān)于明文的任何信息.

2.4 加法同態(tài)標(biāo)識(shí)加密

標(biāo)識(shí)密碼即基于身份的密碼(identity-based cryptography, IBC), 是Shamir[31]于1984 年提出的概念, 在標(biāo)識(shí)密碼方案中, 用戶的私鑰由密鑰生成中心(key generation center, KGC) 根據(jù)主密鑰和用戶標(biāo)識(shí)計(jì)算得出, 用戶的公鑰由用戶標(biāo)識(shí)充當(dāng), 從而用戶不需要通過第三方保證其公鑰的真實(shí)性. 與基于公鑰基礎(chǔ)設(shè)施(public key infrastructure, PKI) 的密碼方案相比, 標(biāo)識(shí)密碼方案中的密鑰管理環(huán)節(jié)可以適當(dāng)?shù)玫胶?jiǎn)化. 在大數(shù)據(jù)隱私計(jì)算中, 一般的加法同態(tài)加密方案由于更新密鑰需要花費(fèi)太多的時(shí)間, 故越來越多人開始注意到基于身份的同態(tài)加密方案, 例如Gentry 等人[32]基于容錯(cuò)困難(learning with errors,LWE) 問題構(gòu)造的同態(tài)加密方案等.

一個(gè)加法同態(tài)標(biāo)識(shí)加密方案通常由如下四個(gè)算法組成.

系統(tǒng)建立Setup(1?): 算法輸入一個(gè)安全參數(shù)?, 輸出加密主公鑰mpk 和加密主私鑰msk, 以及系統(tǒng)參數(shù)pp, 其中包含明文空間M、密文空間C、加密主公鑰mpk 等公開參數(shù)的描述.

密鑰生成KeyGen(pp,msk,id): 密鑰生成算法輸入加密主私鑰msk 與用戶標(biāo)識(shí)id, 輸出用戶私鑰skid.

加密Enc(id,m): 加密算法輸入用戶標(biāo)識(shí)id 與明文m ∈M, 輸出密文c ∈C.

解密Dec(sk,c): 解密算法輸入用戶私鑰skid與密文c ∈C, 輸出m ∈M; 否則輸出⊥, 代表解密失敗.

方案具有如下三個(gè)性質(zhì).

正確性. 對(duì)于所有(mpk,msk,pp)←Setup(1?), skid←KeyGen(pp,msk,id),c ←Enc(id,m), 均有m ←Dec(skid,c).

同態(tài)性. 方案滿足對(duì)于所有(mpk,msk,pp)←Setup(1?), skid←KeyGen(pp,msk,id), 對(duì)于任意兩個(gè)密文c1←Enc(id,m1),c2←Enc(id,m2), 均有c1?c2=Enc(id,m1+m2).

安全性. 加法同態(tài)標(biāo)識(shí)加密方案的安全性要求敵手無法從密文得到關(guān)于明文的任何信息.

2.5 大步小步走(Baby Step Giant Step, BSGS) 算法

2.6 秘密共享

Shamir 秘密共享[28]是構(gòu)造門限密碼方案的基礎(chǔ)組件. 在Shamir 秘密共享方案中, 假設(shè)一共有n個(gè)參與者, 只有當(dāng)大于等于t位參與者共同參與計(jì)算時(shí), 才能恢復(fù)秘密值s, 小于t位參與者無法獲得關(guān)于秘密的任何信息. 令GF(p) 是階為大素?cái)?shù)p的有限域, 秘密信息s ∈Z?p.

2.6.1 Shamir 秘密共享方案

可信中心給n位參與者{U1,U2,··· ,Un}分發(fā)秘密份額, 使得其中任意t位及其以上誠實(shí)的參與者才可以重構(gòu)出秘密信息s, 而任意小于t位的參與者不能得到關(guān)于秘密s的任何信息.

2.6.2 Shamir 聯(lián)合隨機(jī)秘密共享方案

在無可信中心的情況下, 需要參與者{U1,U2,··· ,Un}聯(lián)合決定并生成隨機(jī)的共享秘密值.

3 基于SM2 算法的同態(tài)加密方案

SM2[13]是中國于2010 年12 月發(fā)布的基于橢圓曲線的公鑰密碼方案, 并于2012 年3 月成為商用密碼標(biāo)準(zhǔn). 本節(jié)基于SM2 構(gòu)造具有加法同態(tài)性質(zhì)的公鑰加密方案.

3.1 方案構(gòu)造

系統(tǒng)建立. 令A(yù)、B分別為加密用戶與解密用戶, 他們提前設(shè)定相同的公共參數(shù)pp, 其中p是大素?cái)?shù),E為定義在有限域Fp上的橢圓曲線,G是橢圓曲線的q階基點(diǎn), 明文空間M 的比特長(zhǎng)度mlen 設(shè)為32 比特[7]. 若k ∈, [k]G代表橢圓曲線基點(diǎn)G的k倍點(diǎn). 密碼雜湊函數(shù)H:{0,1} →Zq.x||y代表字節(jié)串或比特串x與y的拼接.⊕代表比特串之間的異或運(yùn)算.

密鑰生成.B用戶隨機(jī)選取私鑰sk∈, 公開公鑰pk=[sk]G.

加密. 設(shè)用戶A需要發(fā)送給用戶B的消息為m, 用戶A需要進(jìn)行以下計(jì)算:

標(biāo)準(zhǔn)SM2 方案[13]的c2部分是m ⊕t, 其中t= KDF(x2||y2,mlen), KDF :{0,1}?×mlen→{0,1}mlen. 但由于本方案的后續(xù)計(jì)算過程沒有用到t, 故在本方案中無需計(jì)算該值.

解密. 用戶B收到用戶A發(fā)送的密文c=(c1,c2,c3), 進(jìn)行如下運(yùn)算解密:

(1) 驗(yàn)證c1是否滿足橢圓曲線方程, 若不滿足則報(bào)錯(cuò)并退出;

(2) 計(jì)算橢圓曲線點(diǎn)S=[h]c1, 其中h=1, 若S是無窮遠(yuǎn)點(diǎn), 則報(bào)錯(cuò)并退出;

(3) 計(jì)算橢圓曲線點(diǎn)[sk]c1=(x2,y2),[m]G=c2?[sk]c1;

(4) 利用BSGS 算法從[m]G中恢復(fù)m;

(5) 若是同態(tài)運(yùn)算后的密文, 直接輸出明文m, 解密完成并退出;

(6) 否則計(jì)算u=H(x2||m||y2), 判斷u=c3是否成立. 若成立, 輸出明文m, 否則報(bào)錯(cuò)并退出.

標(biāo)準(zhǔn)SM2 方案[13]支持消息完整性校驗(yàn), 故本文提出的基于SM2 的同態(tài)加密方案相比一般的加法同態(tài)加密方案還具有密文校驗(yàn)的功能. 然而c3部分是密碼雜湊函數(shù)生成的摘要, 不具備加同態(tài)性, 所以無法支持同態(tài)計(jì)算后的密文校驗(yàn). 但從實(shí)際應(yīng)用來看, 這是可以接受的. 如聯(lián)邦學(xué)習(xí)中最典型的兩方縱向(無第三方存在的情況), 雙方通過加密自身訓(xùn)練過程中的中間值, 進(jìn)而共同完成模型訓(xùn)練. 然而, 進(jìn)行密文計(jì)算(同態(tài)加、標(biāo)量乘等操作) 的一方無法對(duì)密文進(jìn)行解密, 同時(shí)解密一方解密得到的明文一般為不可區(qū)分的隨機(jī)值, 失去了密文校驗(yàn)的價(jià)值, 如兩方縱向邏輯回歸[34]; 另一方面, Paillier[8]、Exp-ElGamal[10]、BGN[11]等使用廣泛的同態(tài)方案均不支持同態(tài)密文校驗(yàn), 但仍被廣泛使用, 這也能說明同態(tài)密文校驗(yàn)并不是必須的. BSGS 算法無法在有效的時(shí)間內(nèi)恢復(fù)比特長(zhǎng)度過長(zhǎng)的明文, 故限定了明文空間M 的比特長(zhǎng)度,此處以32 比特[7]為例.

正確性. 如果用戶A、B是誠實(shí)的, 那么有:

3.2 門限解密

門限密碼概念由Desmedt[35]提出, 假設(shè)系統(tǒng)中存在t位參與者{U1,U2,··· ,Un}, 他們共享解密私鑰sk, 當(dāng)對(duì)密文進(jìn)行解密時(shí), 至少需要t位參與者共同參與才能恢復(fù)密文所對(duì)應(yīng)的明文, 少于t位的參與者無法得到關(guān)于明文的任何信息. 門限解密能夠降低或避免因個(gè)體完全掌握解密密鑰而導(dǎo)致的濫用權(quán)限、密鑰丟失, 或某個(gè)參與者被攻擊者完全控制而造成系統(tǒng)癱瘓等安全風(fēng)險(xiǎn), 使系統(tǒng)的容錯(cuò)率和安全性得到較大提高. 一般的門限密碼方案可分為有可信中心和無可信中心兩類. 當(dāng)可信中心存在時(shí), 由可信中心進(jìn)行秘密分發(fā), 減少參與者之間的通信量和計(jì)算量; 但一個(gè)被所有參與者都信任的可信中心可能并不存在, 此時(shí)需要參與者聯(lián)合實(shí)現(xiàn)對(duì)秘密的分享, 即無可信中心方案. 本節(jié)基于Shamir 秘密共享[28]構(gòu)造3.1 節(jié)加法同態(tài)加密方案的門限解密方案.

系統(tǒng)建立. 系統(tǒng)建立階段的公開參數(shù)與符號(hào)定義在有可信中心時(shí)由可信中心產(chǎn)生, 無可信中心時(shí)由t位參與者共同決定, 它們應(yīng)與3.1 節(jié)系統(tǒng)建立的公開參數(shù)與符號(hào)定義保持一致.

密鑰生成. 當(dāng)存在可信中心時(shí), 由可信中心完成生成密鑰對(duì)(pk,sk)、公開公鑰pk、生成關(guān)于sk 的秘密份額、秘密份額的分發(fā). 可信中心需進(jìn)行如下運(yùn)算:

3.3 安全性分析

基于SM2 的加法同態(tài)加密方案是將標(biāo)準(zhǔn)SM2 方案的密文c2部分從m ⊕t變?yōu)閇m]G+[k]pk, 從而使方案具備加法同態(tài)性. 其中t是由[k]pk 通過密鑰派生函數(shù)KDF 生成的比特串, 即t近似于的[k]pk摘要. 也就是說標(biāo)準(zhǔn)SM2 方案的c2部分是將明文m與[k]pk 的摘要進(jìn)行異或得到的. 而本文所提出的基于SM2 的加法同態(tài)加密方案是將[m]G與[k]pk 直接相加. 兩種方案的密文c2部分生成本質(zhì)上是一致的, 均為明文與[k]pk 進(jìn)行運(yùn)算. 且在其余運(yùn)算過程與密文部分均不變的的前提下, 基于SM2 的加法同態(tài)加密方案與標(biāo)準(zhǔn)SM2 方案應(yīng)有類似的安全性. 從另一個(gè)方面來說, 基于SM2 的加法同態(tài)加密方案的c2密文形式與Exp-ElGamal 也是一致的, 也可說明該方案與Exp-ElGamal 也有類似的安全性.

定理1如果DDH 問題是難解的, 那么基于SM2 的加法同態(tài)加密方案是IND-CPA 安全的.

證明:如果存在一個(gè)概率多項(xiàng)式時(shí)間(probabilistic polynomial time, PPT) 敵手A能以不可忽略的優(yōu)勢(shì)ε打破基于SM2 的加法同態(tài)加密方案, 則可以構(gòu)造挑戰(zhàn)者C以不可忽略的優(yōu)勢(shì)解決DDH 問題.

系統(tǒng)建立.C得到DDH 問題的實(shí)例([x]G,[y]G,z[G]). 然后運(yùn)行系統(tǒng)建立算法, 得到系統(tǒng)參數(shù)pp,設(shè)置公鑰pk=[x]G. 將pp 與pk 發(fā)送給A.

挑戰(zhàn).A提交兩個(gè)任意的明文m0,m1∈M 給C.C隨機(jī)選擇一個(gè)比特α ∈{0,1}, 進(jìn)而計(jì)算c?=([y]G,[mα]G+[z]G), 然后將c?發(fā)送給A.

猜測(cè).A輸出對(duì)α的猜測(cè)α′. 如果α=α′, 則說明A獲勝. 定義:

定義A獲勝的優(yōu)勢(shì)為:

那么C解決DDH 問題的優(yōu)勢(shì)為:

本節(jié)提出的門限解密方案是基于Shamir 秘密共享構(gòu)造的, 采用了Desmedt[35]構(gòu)造的ElGamal 的門限解密方案的思路. 同時(shí)關(guān)于以基于Shamir 秘密共享方案構(gòu)造公鑰加密方案的門限解密的安全性已在多篇文獻(xiàn)中得到證明, 如文獻(xiàn)[24,35] 等, 故本文不再贅述.

4 基于SM9 算法的同態(tài)加密方案

2016 年國家密碼管理局正式發(fā)布SM9 標(biāo)準(zhǔn)[16], 它是一種基于雙線性對(duì)的標(biāo)識(shí)密碼方案, 同時(shí)也是我國商用密碼算法中的第一個(gè)標(biāo)識(shí)密碼算法. 本節(jié)基于SM9 構(gòu)造具有加法同態(tài)性質(zhì)的標(biāo)識(shí)加密方案.

4.1 方案構(gòu)造

系統(tǒng)建立. 令A(yù)、B分別為加密用戶與解密用戶. KGC 提前設(shè)定公開參數(shù)pp, 其中G1、G2為階為素?cái)?shù)N的加法循環(huán)群,P1、P2是它們的生成元, GT為階是素?cái)?shù)N的乘法循環(huán)群, hid 是加密私鑰生成函數(shù)識(shí)別符.e是從G1×G2到GT的雙線性對(duì), 明文空間m的比特長(zhǎng)度mlen 設(shè)為32 比特[7]. 若u是隨機(jī)數(shù), [u]P代表群G1、G2中元素P的u倍. 密碼雜湊函數(shù)H1:{0,1}?×N →Z?N, 消息驗(yàn)證碼函數(shù)MAC :{0,1}?×GT→Z?N, 密鑰派生函數(shù)KDF :{0,1}?×klen→{0,1}klen, 其中klen = mlen+256.隨機(jī)選擇msk∈Z?N作為加密主私鑰, 計(jì)算G1中的元素mpk=[msk]P1作為加密主公鑰, 則加密主密鑰對(duì)為(mpk,msk). KGC 保存msk, 公開mpk.

密鑰生成. 設(shè)用戶B的標(biāo)識(shí)為idb, KGC 在有限域FN上計(jì)算t1=H1(idb||hid,N)+msk, 若t1=0則需重新執(zhí)行系統(tǒng)建立算法, 否則計(jì)算t2=msk·t?11. 用戶B的解密私鑰skidb=[t2]P2.

加密. 設(shè)用戶A需要發(fā)送給用戶B的消息為m. 用戶A應(yīng)實(shí)現(xiàn)以下運(yùn)算步驟:

標(biāo)準(zhǔn)SM9 加密方案[16]的c2部分是m ⊕K1, 其中K1是KDF 生成的K的前mlen 比特. 由于本方案中后續(xù)無需用到K1, 故K1部分在本方案中被丟棄.

解密. 用戶B收到用戶A發(fā)送的密文c=(c1,c2,c3), 進(jìn)行如下計(jì)算解密:

與SM2 同態(tài)加密方案類似, 單個(gè)密文可以通過c3進(jìn)行解密校驗(yàn). 但是由于c3是消息驗(yàn)證碼函數(shù)生成的, 不具備加法同態(tài)性, 因此無法校驗(yàn)同態(tài)計(jì)算后的密文. 同時(shí)本方案需要利用BSGS 算法從gm中恢復(fù)出m, 此處同樣限定明文空間M 的比特長(zhǎng)度mlen 為32 比特.

正確性. 如果用戶A、B是誠實(shí)的且KGC 未被攻擊, 那么一定有:

4.2 門限解密

Boneh 等人[29]最早將門限思想引入到基于身份的加密方案中, 其目的主要是為了解決KGC 完全掌握系統(tǒng)主私鑰msk, 從而導(dǎo)致的權(quán)限過大問題. 主要采用的方法是將msk 分割為秘密份額分發(fā)給各個(gè)分KGC, 每個(gè)分KGC 為用戶生成部分用戶私鑰份額, 至少需要t個(gè)KGC 產(chǎn)生的用戶私鑰份額, 才能構(gòu)成完整的用戶私鑰, 完成對(duì)密文的解密, 因此也被稱作分布式密鑰生成. 但此方法存在兩個(gè)弊端: 首先要求KGC 必須實(shí)時(shí)在線, 其次是必須要足夠的t個(gè)KGC 才能完成解密. 所以Baek 等人[36]認(rèn)為, 在基于身份的門限解密方案中, 直接對(duì)用戶密鑰進(jìn)行分割也是有必要的, 此類門限解密和傳統(tǒng)的基于PKI 的門限解密類似, 單個(gè)KGC 作為可信中心存在. 于是我們可將基于身份的門限解密方案分成單中心(單個(gè)KGC) 與多中心(多個(gè)KGC) 兩種類型. 本節(jié)以假設(shè)系統(tǒng)中存在n位參與者{U1,U2,··· ,Un}, 然后再基于Shamir 秘密共享構(gòu)造4.1 節(jié)的門限解密方案.

系統(tǒng)建立. 單中心情況下, 僅有一個(gè)KGC 存在. KGC 首先參照4.1 節(jié)系統(tǒng)初始化部分得到公開參數(shù)pp 與相關(guān)符號(hào)定義, 然后選擇隨機(jī)數(shù)t2= msk·[H1(idb||hid,N)+msk]?1∈Z?N?1作為秘密, 通過計(jì)算H1(idb||hid,N) 與上式聯(lián)立可求得加密主私鑰msk, 進(jìn)而可以計(jì)算G1中的元素mpk = [msk]P1作為加密主公鑰. 最后保存msk, 公開mpk.

多中心情況下, 系統(tǒng)中存在n′個(gè)可信中心{KGC1,KGC2,··· ,KGCn′},n′≥2t ?1, 它們需要共同確定公開參數(shù)與相關(guān)符號(hào)定義. 由于SM9 方案的用戶密鑰形式為skidb= msk·[H1(idb||hid,N)+msk]?1P2, 為了防止msk 泄露, 此處不能直接以msk 作為秘密. 我們首先將用戶密鑰形式寫為skidb=[1?H1(idb||hid,N)·[H1(idb||hid,N)+msk]?1]P2, 然后以[H1(idb||hid,N)+msk]?1作為秘密實(shí)現(xiàn)門限解密. KGC 們?yōu)榱松擅孛芊蓊~, 并公開mpk, 需要進(jìn)行如下運(yùn)算:

多中心情況下, 此階段KGC 們不需要做出任何運(yùn)算.

加密. 加密算法中, 單中心情況與多中心情況是一致的, 加密用戶直接使用標(biāo)識(shí)idb加密發(fā)送的消息m得到密文c即可, 具體的計(jì)算過程見4.1節(jié)加密部分.

4.3 安全性分析

基于SM9 的加法同態(tài)加密方案與基于SM2 的加法同態(tài)加密方案采用了類似修改思路, 將標(biāo)準(zhǔn)SM9方案的密文c2部分從m ⊕t變?yōu)間m·w, 從而使方案具備加同態(tài)性.t是由w、密文c1部分、用戶標(biāo)識(shí)通過密鑰派生函數(shù)KDF 生成的比特串. 然而,w是由c1與p2通過雙線性對(duì)e求得的GT群元素, 用戶標(biāo)識(shí)也包含在c1中. 故KDF 的主要參數(shù)就是w, 所以t實(shí)質(zhì)上近似于w的摘要. 由此可知, 標(biāo)準(zhǔn)SM9方案的c2是由明文m與w的摘要t進(jìn)行異或運(yùn)算得到的, 而本文提出的基于SM9 的加法同態(tài)加密方案是將明文m以gm的形式放到乘法群GT中再直接與w相乘得到的. 兩種方案的密文c2部分本質(zhì)是一樣的, 均是明文m與w的運(yùn)算. 故在其他運(yùn)算過程以及密文部分不變的前提下, 兩種方案應(yīng)有類似的安全性.

定理2令密碼雜湊函數(shù)H1是隨機(jī)諭言機(jī), 如果DDH 問題是難解的, 那么基于SM9 的加法同態(tài)加密方案是IND-CPA 安全的.

本節(jié)所提的門限解密方案是以Shamir 秘密共享為基礎(chǔ)構(gòu)造的, 構(gòu)造思想與Baek 等人[36]構(gòu)造的基于身份的門限解密方案一致. 此類門限解密方案的安全性已在文獻(xiàn)[36] 中得到證明, 本文不再贅述.

5 效率分析

本文的主要工作是分別基于國密SM2 和SM9 構(gòu)造了加法同態(tài)加密方案. 為保證本文所提出同態(tài)加密方案的高效性, 本節(jié)將對(duì)128 比特安全等級(jí)(256 位橢圓曲線、3072 位Paillier)、明文比特長(zhǎng)度為32比特下(參照Chen 等人[7]的方案) 的SM2 同態(tài)加密方案、標(biāo)準(zhǔn)SM2 加密方案、SM9 同態(tài)加密方案、標(biāo)準(zhǔn)SM9 加密方案、Exp-ElGamal 方案、Twisted-ElGamal 方案、Paillier 方案進(jìn)行對(duì)比實(shí)驗(yàn). 選取Exp-ElGamal 方案、Paillier 方案進(jìn)行對(duì)比實(shí)驗(yàn)的原因是因?yàn)樗鼈兪亲畛Ｓ玫募臃ㄍ瑧B(tài)加密方案, 而選取Twisted-ElGamal 方案是因?yàn)樗拿荑€與密文長(zhǎng)度是相對(duì)較小的, 并且能很好的應(yīng)用于Sigma 協(xié)議與范圍證明協(xié)議. 測(cè)試的硬件平臺(tái)采用Intel i7-1165G7 處理器、內(nèi)存為16 GB、主頻為2.8 GHz. 操作系統(tǒng)為Ubuntu 18.04, 編程語言是Go 1.19. 標(biāo)準(zhǔn)SM2 和SM9 加密方案使用的代碼庫為cryptogm[38], 本文所提出的同態(tài)加密方案的具體實(shí)現(xiàn)[39]也是基于cryptogm 代碼庫; Exp-ElGamal 方案使用的將Go 語言版Bitcoin 的btcec[40]里的EC-ElGamal 方案改為Exp-ElGamal 方案[41]; Paillier 方案使用代碼庫Go-Paillier[42]; Twisted-ElGamal 方案使用Chen 在GitHub 上提供的開源代碼庫[43].

5.1 通信與存儲(chǔ)開銷

從解密算法中可以看出, 如果需要得到明文m, 那么必須求解一個(gè)離散對(duì)數(shù). 加快求解離散對(duì)數(shù)的算法例如kangaroo 算法[44]、Galbraith-Ruprai 算法[45]、BSGS 算法[33]、Bernstein-Lange 算法[46]等.Chen 等人[7]對(duì)它們進(jìn)行了算法復(fù)雜度的分析, 且比較了它們的特性. 例如, kangaroo 算法與Galbraith-Ruprai 算法的平均時(shí)間復(fù)雜度為O(2mlen/2) 且需要一個(gè)固定的內(nèi)存開銷; BSGS 算法平均時(shí)間/空間復(fù)雜度均為O(2mlen/2), 且它可通過調(diào)整參數(shù)的方式靈活調(diào)整時(shí)間以及空間開銷. Bernstein-Lange 算法的平均時(shí)間/空間復(fù)雜度為O(2mlen/3), 但它并不支持并行計(jì)算. 本文選擇BSGS 算法恢復(fù)明文, 因?yàn)樗臅r(shí)間與空間開銷是靈活的, 并且支持并行計(jì)算. 經(jīng)過實(shí)驗(yàn)分析, 該算法需要128 MB 左右的內(nèi)存空間.

經(jīng)過對(duì)比分析, 各方案的密鑰、密文長(zhǎng)度如表1 所示.

表1 各種方案的密鑰與密文長(zhǎng)度(明文長(zhǎng)度為32 比特, 單位bits)Table 1 Key and ciphertext length for various schemes (plaintext length is 32 bits, unit: bits)

需要注意的是, 表1 中密文長(zhǎng)度是在已知明文比特長(zhǎng)度為32 比特下進(jìn)行計(jì)算得到的. 并且標(biāo)識(shí)密碼方案(標(biāo)準(zhǔn)SM9 方案、基于SM9 的同態(tài)加密方案) 的用戶公鑰為用戶標(biāo)識(shí), 即公鑰長(zhǎng)度就是標(biāo)識(shí)長(zhǎng)度, 故在表中沒有給出它們的公鑰長(zhǎng)度.

5.2 計(jì)算開銷

經(jīng)過實(shí)驗(yàn)測(cè)試, 各加密方案的效率計(jì)算開銷結(jié)果如表2 所示.

標(biāo)準(zhǔn)SM2 方案與標(biāo)準(zhǔn)SM9 方案不具備同態(tài)性, 故表2 中沒有同態(tài)加與標(biāo)量乘的實(shí)驗(yàn)結(jié)果.

關(guān)于基于SM2 的同態(tài)加密方案, 如表2 所示, 本文所提出的基于SM2 的同態(tài)加密方案相較于經(jīng)典加法同態(tài)加密方案的Exp-ElGamal、Paillier 在各個(gè)指標(biāo)上均存在效率優(yōu)勢(shì). 解密運(yùn)算方面, 本方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的57%, Paillier 方案的12%. 與標(biāo)準(zhǔn)SM2 方案相比, 加密效率有所降低的原因是由于密文部分的生成從密鑰擴(kuò)展和異或運(yùn)算(即t= KDF(x2||y2,mlen) 與m ⊕t) 變成了橢圓曲線點(diǎn)乘與點(diǎn)加運(yùn)算(即[m]G與[m]G+[k]pk), 后者的效率是低于前者的; 解密效率降低的原因是需要進(jìn)行BSGS 算法恢復(fù)明文m.

表2 各種方案的效率測(cè)試(運(yùn)行1000 次的平均值, 單位: ms)Table 2 Efficiency tests of various schemes (average value of 1000 runs, unit: ms)

關(guān)于基于SM9 的同態(tài)加密方案, 如表2 所示, 本文所提出的基于SM9 的同態(tài)加密方案在各個(gè)指標(biāo)上與Paillier 方案相比均有一定優(yōu)勢(shì), 與Exp-ElGamal 方案相比也僅在加密運(yùn)算上不及. 解密運(yùn)算方面, 本方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的75%, Paillier 方案的16%. 所以該方案相較于其他加法同態(tài)加密方案仍是高效的. 同時(shí), 該方案的密文c2是一個(gè)GT群元素而非一個(gè)橢圓曲線的點(diǎn), 無需做橢圓曲線點(diǎn)加法時(shí)需要的模逆運(yùn)算, 而模逆運(yùn)算是相當(dāng)耗時(shí)的, 所以該方案的同態(tài)加運(yùn)算效率很高. 與標(biāo)準(zhǔn)SM9 方案相比, 加密效率有所降低的原因是由于密文c2部分的生成從異或運(yùn)算(m ⊕K2) 變成了群上的模冪與乘法運(yùn)算(gm與gm×w), 后者的耗時(shí)高于前者. 解密效率降低的原因同樣是需要進(jìn)行BSGS 算法恢復(fù)明文m.

綜上所述, 本文提出的基于國密SM2 和SM9 的同態(tài)加密方案與常用的加法同態(tài)加密方案(Exp-ElGamal、Paillier) 相比在各個(gè)運(yùn)算指標(biāo)上均是高效的. 解密運(yùn)算方面, 所提SM2 加法同態(tài)加密方案的解密耗時(shí)大約為Exp-ElGamal 方案的3/5, Paillier 方案的1/8; SM9 加法同態(tài)加密方案的解密耗時(shí)大約為Exp-ElGamal 方案的3/4, Paillier 方案的1/6. 盡管基于SM9 的同態(tài)加密方案的加密效率不及Exp-ElGamal, 但它的同態(tài)加運(yùn)算效率很高, 在大規(guī)模聯(lián)邦學(xué)習(xí)和隱私計(jì)算中仍應(yīng)具有較大優(yōu)勢(shì). 為了便于讀者參考, 我們將本文所提兩個(gè)加密同態(tài)加密方案的源代碼的上傳至Github 網(wǎng)站中(詳見https://github.com/ShallMate/-Homomorphic-SM2-9).

6 結(jié)束語

本文基于國密SM2 與SM9 設(shè)計(jì)了具有加法同態(tài)性質(zhì)的公鑰加密方案, 并構(gòu)造了相應(yīng)的門限解密方法, 解決了目前缺乏基于國密標(biāo)準(zhǔn)的同態(tài)加密方案這一問題, 使國密算法能夠用于同態(tài)加密場(chǎng)景. 對(duì)本文所提方案進(jìn)行了安全性證明, 然后編程實(shí)現(xiàn)了本文所提同態(tài)加密方案, 實(shí)驗(yàn)結(jié)果表明本文提出的兩個(gè)加法同態(tài)加密方案在大多數(shù)指標(biāo)上與經(jīng)典的Exp-ElGamal、Paillier 方案相比均占優(yōu)勢(shì), 其中SM2 加法同態(tài)加密方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的3/5, Paillier 方案的1/8; SM9 加法同態(tài)加密方案的解密耗時(shí)大約僅為Exp-ElGamal 方案的3/4, Paillier 方案的1/6.