唐 飛, 凌國瑋, 單進勇

1. 重慶郵電大學計算機科學與技術學院, 重慶 400065

2. 重慶郵電大學網絡空間安全與信息法學院, 重慶 400065

3. 北京數牘科技有限公司, 北京 100083

1 引言

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

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

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

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

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

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

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

2 預備知識與定義

2.1 橢圓曲線與相關復雜性假設

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

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

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

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

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

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

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

2.2 雙線性映射與相關復雜性假設

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

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

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

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

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

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

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

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

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

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

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

(1)正確性. 對于所有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), 對于任意兩個密文c1←Enc(pk,m1),c2←Enc(pk,m2), 均有c1?c2=Enc(pk,m1+m2).

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

2.4 加法同態(tài)標識加密

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

一個加法同態(tài)標識加密方案通常由如下四個算法組成.

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

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

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

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

方案具有如下三個性質.

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

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

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

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

2.6 秘密共享

Shamir 秘密共享[28]是構造門限密碼方案的基礎組件. 在Shamir 秘密共享方案中, 假設一共有n個參與者, 只有當大于等于t位參與者共同參與計算時, 才能恢復秘密值s, 小于t位參與者無法獲得關于秘密的任何信息. 令GF(p) 是階為大素數p的有限域, 秘密信息s ∈Z?p.

2.6.1 Shamir 秘密共享方案

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

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

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

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

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

3.1 方案構造

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

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

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

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

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

(1) 驗證c1是否滿足橢圓曲線方程, 若不滿足則報錯并退出;

(2) 計算橢圓曲線點S=[h]c1, 其中h=1, 若S是無窮遠點, 則報錯并退出;

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

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

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

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

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

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

3.2 門限解密

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

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

密鑰生成. 當存在可信中心時, 由可信中心完成生成密鑰對(pk,sk)、公開公鑰pk、生成關于sk 的秘密份額、秘密份額的分發(fā). 可信中心需進行如下運算:

3.3 安全性分析

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

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

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

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

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

猜測.A輸出對α的猜測α′. 如果α=α′, 則說明A獲勝. 定義:

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

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

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

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

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

4.1 方案構造

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

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

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

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

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

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

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

4.2 門限解密

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

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

多中心情況下, 系統(tǒng)中存在n′個可信中心{KGC1,KGC2,··· ,KGCn′},n′≥2t ?1, 它們需要共同確定公開參數與相關符號定義. 由于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作為秘密實現(xiàn)門限解密. KGC 們?yōu)榱松擅孛芊蓊~, 并公開mpk, 需要進行如下運算:

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

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

4.3 安全性分析

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

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

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

5 效率分析

本文的主要工作是分別基于國密SM2 和SM9 構造了加法同態(tài)加密方案. 為保證本文所提出同態(tài)加密方案的高效性, 本節(jié)將對128 比特安全等級(256 位橢圓曲線、3072 位Paillier)、明文比特長度為32比特下(參照Chen 等人[7]的方案) 的SM2 同態(tài)加密方案、標準SM2 加密方案、SM9 同態(tài)加密方案、標準SM9 加密方案、Exp-ElGamal 方案、Twisted-ElGamal 方案、Paillier 方案進行對比實驗. 選取Exp-ElGamal 方案、Paillier 方案進行對比實驗的原因是因為它們是最常用的加法同態(tài)加密方案, 而選取Twisted-ElGamal 方案是因為它的密鑰與密文長度是相對較小的, 并且能很好的應用于Sigma 協(xié)議與范圍證明協(xié)議. 測試的硬件平臺采用Intel i7-1165G7 處理器、內存為16 GB、主頻為2.8 GHz. 操作系統(tǒng)為Ubuntu 18.04, 編程語言是Go 1.19. 標準SM2 和SM9 加密方案使用的代碼庫為cryptogm[38], 本文所提出的同態(tài)加密方案的具體實現(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 通信與存儲開銷

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

經過對比分析, 各方案的密鑰、密文長度如表1 所示.

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

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

5.2 計算開銷

經過實驗測試, 各加密方案的效率計算開銷結果如表2 所示.

標準SM2 方案與標準SM9 方案不具備同態(tài)性, 故表2 中沒有同態(tài)加與標量乘的實驗結果.

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

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

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

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

6 結束語

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