基于SM2 的多接收方公鑰加密方案*

賴(lài)俊祚, 黃正安, 翁 健, 吳永東

1. 暨南大學(xué), 廣州510632

2. 鵬城實(shí)驗(yàn)室, 深圳518055

1 引言

自2008 年中本聰發(fā)表題為《比特幣: 一種點(diǎn)對(duì)點(diǎn)的電子現(xiàn)金系統(tǒng)》[1]的白皮書(shū)以來(lái), 作為比特幣核心技術(shù)的區(qū)塊鏈開(kāi)始快速發(fā)展. 從技術(shù)應(yīng)用的角度來(lái)看, 區(qū)塊鏈可視為一種分布式數(shù)據(jù)庫(kù), 它使用密碼學(xué)、時(shí)間戳和共識(shí)算法技術(shù)等實(shí)現(xiàn)了去中心化的分布式架構(gòu). 區(qū)塊鏈具有去中心化、可追溯、集體維護(hù)、透明開(kāi)放、無(wú)法篡改等特點(diǎn)[2], 這些特點(diǎn)為區(qū)塊鏈構(gòu)建了信任基礎(chǔ), 解決了信息不對(duì)稱(chēng)的問(wèn)題, 使其廣泛適用于多用戶(hù)、多接收方的應(yīng)用場(chǎng)景. 然而, 如何在一個(gè)不依賴(lài)任何信任機(jī)構(gòu)、透明開(kāi)放的區(qū)塊鏈系統(tǒng)上對(duì)用戶(hù)關(guān)鍵數(shù)據(jù)進(jìn)行隱私保護(hù), 這一問(wèn)題仍未能得到有效解決. 常規(guī)的公鑰加密雖然能保證機(jī)密性, 但在多接收方的場(chǎng)景下計(jì)算成本呈線(xiàn)性增長(zhǎng), 極大影響加密效率. 一種比較合適的解決方案是先采用隨機(jī)數(shù)重用的多接收方公鑰加密方案對(duì)數(shù)據(jù)進(jìn)行加密, 再將密文數(shù)據(jù)傳到鏈上. 與常規(guī)公鑰加密相比, 這種加密類(lèi)型效率更高, 更適合區(qū)塊鏈等去中心化、多接收方的應(yīng)用場(chǎng)景, 能起到更好的隱私保護(hù)效果.

多接收方公鑰加密最早是由Bellare 等[3]正式提出的. 文獻(xiàn)[3] 中指出, 公鑰加密的單接收方INDCPA/CCA 安全性可以推出多接收方IND-CPA/CCA 安全性. 隨后, Bellare 等[4]提出“可復(fù)現(xiàn)的公鑰加密(reproducible PKE)” 這一概念, 并指出如果一個(gè)可復(fù)現(xiàn)的公鑰加密方案滿(mǎn)足IND-CCA 安全性, 那么以該方案作為底層方案而得到的隨機(jī)數(shù)重用的多接收方公鑰加密方案仍滿(mǎn)足相應(yīng)的IND-CCA 安全性(按照文獻(xiàn)[4] 中的記號(hào), 稱(chēng)為RR-IND-CCA 安全性).

SM2[5]是我國(guó)國(guó)家密碼管理局推出的一種由我國(guó)擁有完全自主知識(shí)產(chǎn)權(quán)的非對(duì)稱(chēng)商用密碼算法. 該算法基于橢圓曲線(xiàn)密碼體制, 與國(guó)際通用的RSA 密碼體制[6,7]相比, 在同等安全強(qiáng)度下具有更高的效率.當(dāng)前我國(guó)在金融、政企等要求高安全等級(jí)的行業(yè)大多采用國(guó)際通用的加密算法, 而越來(lái)越多的國(guó)際通用密碼算法被攻擊或者被破譯, 使得我國(guó)的信息安全面臨嚴(yán)重威脅. 選擇更安全、更高效的國(guó)密算法, 或者基于國(guó)密算法構(gòu)造新的加密方案, 在信息安全已上升到國(guó)家安全的戰(zhàn)略地位的今天, 有著重要的意義.

本文從我國(guó)的區(qū)塊鏈數(shù)據(jù)隱私保護(hù)研究現(xiàn)狀和安全需求出發(fā), 首次基于國(guó)密算法SM2 提出了一個(gè)隨機(jī)數(shù)重用的多接收方公鑰加密方案, 并在隨機(jī)預(yù)言機(jī)模型[8]下證明該方案滿(mǎn)足RR-IND-CCA 安全性.

本文的其余部分結(jié)構(gòu)如下: 第2 節(jié)介紹了ODH 困難假設(shè)、IND-CCA 安全性、RR-IND-CCA 安全性、可復(fù)現(xiàn)的公鑰加密等相關(guān)知識(shí); 第3 節(jié)研究如何構(gòu)造隨機(jī)數(shù)重用的多接收方公鑰加密方案; 第4 節(jié)用橢圓曲線(xiàn)實(shí)例化該方案, 由此得到一個(gè)基于SM2 的隨機(jī)數(shù)重用多接收方公鑰加密方案.

2 預(yù)備知識(shí)

基本符號(hào). 本文中, 我們統(tǒng)一用κ表示安全參數(shù), 用N 表示自然數(shù)集. 對(duì)任意n ∈N, 符號(hào)[n] 表示集合{1,2,··· ,n}. 對(duì)任意有限集S,s ←S表示從S中均勻隨機(jī)地選取出一個(gè)元素s. 若D是定義在S上的一個(gè)概率分布,s ←D表示從S中按概率分布D選取元素s. 我們用{0,1}?表示所有長(zhǎng)度的字符串組成的集合, 用{0,1}?表示長(zhǎng)度為? ∈N 的字符串組成的集合.

對(duì)任意概率算法A, 記A所用的隨機(jī)數(shù)集合為RA.y ←A(x1,x2,··· ,xt) 表示“算法A以(x1,x2,··· ,xt) 為輸入, 同時(shí)選取內(nèi)部隨機(jī)數(shù)r ←RA, 最后輸出結(jié)果y”. 如果A的運(yùn)行時(shí)間是關(guān)于安全參數(shù)κ的多項(xiàng)式, 則稱(chēng)A為概率多項(xiàng)式時(shí)間(probabilistic polynomial time, PPT) 算法.

我們用粗斜體表示向量, 比如m(相應(yīng)地,m[i] 表示m的第i個(gè)分量,|m| 表示m的分量個(gè)數(shù),|m[i]| 表示m[i] 的比特長(zhǎng)度). 除非特別說(shuō)明, 否則, 對(duì)任意概率算法A,A(m) 均表示算法A對(duì)m的每個(gè)分量單獨(dú)作用(每次獨(dú)立選取內(nèi)部隨機(jī)數(shù)), 即A(m):=(A(m[1]),A(m[2]),··· ,A(m[|m|])).

Oracle Diffie-Hellman 困難假設(shè). 本文公鑰加密方案的安全性將依賴(lài)于oracle Diffie-Hellman 困難假設(shè)(簡(jiǎn)記為ODH 困難假設(shè)). 我們回顧文獻(xiàn)[9] 中的ODH 假設(shè)定義如下. 記G為群參數(shù)生成算法:該算法以安全參數(shù)1κ為輸入, 輸出一個(gè)q階循環(huán)群Gq的描述、q以及Gq的任意生成元g(其中, 要求q的二進(jìn)制表示是κ比特長(zhǎng)的字符串). 簡(jiǎn)記為(Gq,q,g)←G(1κ). 此外, 記?len∈N,H:Gq →{0,1}?len是一個(gè)函數(shù).

定義1 (ODH 困難問(wèn)題[9]) 如果對(duì)任意PPT 敵手A,A的優(yōu)勢(shì)

而且要求在這兩個(gè)實(shí)驗(yàn)中,A都不能向Hv(·) 詢(xún)問(wèn)gu.

公鑰加密. 根據(jù)文獻(xiàn)[3,4] 的符號(hào)標(biāo)記方式, 一個(gè)公鑰加密方案PKE 由以下4 個(gè)PPT 算法組成:

? PGen: 該算法以安全參數(shù)1κ作為輸入, 輸出一個(gè)公共參數(shù)par. 簡(jiǎn)記為par←PGen(1κ).

? KGen: 該算法以公共參數(shù)par 作為輸入,輸出一對(duì)公私鑰對(duì)(pk,sk). 簡(jiǎn)記為(pk,sk)←KGen(par).

? Enc: 該算法以公共參數(shù)par、公鑰pk 和明文m作為輸入, 輸出一個(gè)密文c. 簡(jiǎn)記為c ←Enc(par,pk,m).

? Dec: 該算法是確定性算法, 以公共參數(shù)par、私鑰sk 和密文c作為輸入, 輸出一個(gè)明文m或符號(hào)⊥(表示c不是合法密文). 簡(jiǎn)記為m/⊥←Dec (par,sk,c).

對(duì)任意合法生成的公共參數(shù)par, 我們將相應(yīng)的明文空間記為M(par), 相應(yīng)的Enc 內(nèi)部隨機(jī)數(shù)空間記為REnc(par). 公鑰加密方案的正確性要求如下: 對(duì)于任意par←PGen(1κ), (pk,sk)←KGen(par) 和任意明文m ∈M(par), 有Dec(par,sk,Enc(par,pk,m))=m.

接下來(lái), 我們回顧公鑰加密中最常見(jiàn)的一個(gè)安全模型: IND-CCA 安全性[10].

記A= (A1,A2) 為帶有狀態(tài)信息的概率多項(xiàng)式時(shí)間敵手. 對(duì)于一個(gè)公鑰加密方案 PKE =(PGen, KGen, Enc, Dec), 我們考慮以下實(shí)驗(yàn):是可忽略的, 則稱(chēng)PKE 是IND-CCA 安全的.

隨機(jī)數(shù)重用的多接收方公鑰加密. 通常來(lái)說(shuō), 在標(biāo)準(zhǔn)的公鑰加密應(yīng)用場(chǎng)景中, 每當(dāng)給一個(gè)用戶(hù)(即接收方) 發(fā)送消息, 就需要以該用戶(hù)的公鑰作為加密公鑰, 調(diào)用加密算法(需要均勻獨(dú)立隨機(jī)地選取一個(gè)內(nèi)部隨機(jī)數(shù)) 對(duì)消息進(jìn)行加密. 這就意味著, 每給一個(gè)接收方發(fā)送加密消息, 就需要一個(gè)均勻獨(dú)立隨機(jī)選取的內(nèi)部隨機(jī)數(shù). 當(dāng)需要同時(shí)給多個(gè)接收方發(fā)送加密消息的時(shí)候, 這種解決方案自然也要求發(fā)送方生成多個(gè)滿(mǎn)足均勻分布的內(nèi)部隨機(jī)數(shù)用于加密. 為了降低實(shí)際應(yīng)用中隨機(jī)數(shù)生成方面的計(jì)算成本并提高效率, Bellare 等人[4]針對(duì)多接收方的公鑰加密場(chǎng)景提出了隨機(jī)數(shù)重用的公鑰加密方案.

3 隨機(jī)數(shù)重用的多接收方公鑰加密方案

本節(jié)中, 我們提出一個(gè)高效的隨機(jī)數(shù)重用多接收方公鑰加密方案, 并在隨機(jī)預(yù)言機(jī)模型下證明其滿(mǎn)足RR-IND-CCA 安全性. 我們將在下一節(jié)給出該方案基于國(guó)密算法SM2[5]的一個(gè)實(shí)例化版本.

3.1 方案構(gòu)造

記G為一個(gè)群參數(shù)生成算法,?msg,?key,?ctx∈N. 記H1: Gq →{0,1}?msg×{0,1}?key和H2:Gq×{0,1}?key×{0,1}?msg→{0,1}?ctx為兩個(gè)哈希函數(shù). 在本方案的安全性證明中,H2將用隨機(jī)預(yù)言機(jī)[8]來(lái)替換.

我們的底層公鑰加密方案PKE1如圖1 所示.

圖1 公鑰加密方案PKE1Figure 1 PKE scheme PKE1

定理3 PKE1是可復(fù)現(xiàn)的.

3.2 安全性證明

本小節(jié)中, 我們給出定理2 和定理3 的完整證明.證明(定理2): 我們構(gòu)造一個(gè)針對(duì)關(guān)于(G,H1) 的ODH 問(wèn)題的敵手B如下所示.

B收到(1κ,Gq,q,g,U,V,W) 以后, 令par = (1κ,H1,Gq,q,g), pk =V,c?1=U, (k1,k2) =W, 并將(par,pk) 發(fā)給A1.

同時(shí),B給A1提供隨機(jī)預(yù)言機(jī)(即H2) 和解密預(yù)言機(jī)的詢(xún)問(wèn)服務(wù).

隨機(jī)預(yù)言機(jī)詢(xún)問(wèn)方面,B預(yù)先初始化一個(gè)空表List, 然后通過(guò)這個(gè)列表來(lái)回答A的詢(xún)問(wèn). 具體而言,對(duì)于A1的任意一個(gè)隨機(jī)預(yù)言機(jī)詢(xún)問(wèn)x ∈{0,1}?,B首先檢查L(zhǎng)ist 中是否存在元組(x,?). 如果A1是首次詢(xún)問(wèn)到x,B隨機(jī)選取y ←{0,1}?ctx, 將(x,y) 存入列表List 中, 并把y作為返回值發(fā)給A1; 如果A1不是首次詢(xún)問(wèn)到x, 則在List 中必然存有元組(x,?) (比如, (x,y′)), 這種情況下,B就將y′作為返回值發(fā)給A1.

通過(guò)這樣的方式,B可以回答A2的隨機(jī)預(yù)言機(jī)詢(xún)問(wèn)和解密詢(xún)問(wèn).

最后,B從A2處收到一個(gè)比特b′, 將b′′=(b′=b) 作為自己的最終輸出值.

以上就是關(guān)于敵手B的描述.

下面我們考慮B的優(yōu)勢(shì).

事件Evt2發(fā)生時(shí),A提出的所有解密詢(xún)問(wèn)中, 所有不屬于TypeI類(lèi)的詢(xún)問(wèn)c= (c1,c2,c3) 均滿(mǎn)足c1=且DEC(c) =⊥. 我們注意到, 只有當(dāng)A提出不屬于TypeI類(lèi)的解密詢(xún)問(wèn)時(shí), (k1,k2) 才會(huì)在對(duì)解密詢(xún)問(wèn)的回答中被調(diào)用到(換句話(huà)說(shuō), 在上面事件Evt1發(fā)生時(shí), (k1,k2) 只在挑戰(zhàn)密文的生成過(guò)程中用到, 其他任何時(shí)候都不再涉及到). 另一方面, 對(duì)任意固定的同時(shí)滿(mǎn)足c1=和DEC(c)=⊥的解密詢(xún)問(wèn)(c1,c2,c3),c1=確保在回答解密詢(xún)問(wèn)的過(guò)程中需要恢復(fù)出(k1,k2), 而DEC(c)=⊥確保最多只有k2被調(diào)用來(lái)回答該解密詢(xún)問(wèn). 由于(k1,k2) =W ←{0,1}?msg×{0,1}?key, 所以這種情況下從A的角度來(lái)看,k1依然是均勻獨(dú)立隨機(jī)分布的, 也就是說(shuō)無(wú)論b= 0 還是b= 1,A所看到的元素分布依然完全相同.由此可知,

4 基于SM2 的RR-MRPKE 實(shí)例化方案

令a,b為有限域Fq上的元素, 且a,b共同定義了Fq上的一條橢圓曲線(xiàn)E. 記E(Fq) 是E的所有有理點(diǎn)(包括無(wú)窮遠(yuǎn)點(diǎn)O) 組成的集合.G是E上的一個(gè)基點(diǎn), 其階為素?cái)?shù)p. 記h是p的余因子. 對(duì)任意k ∈N, 我們用kG表示橢圓曲線(xiàn)上G的k倍點(diǎn). 記KDF:{0,1}?×N→{0,1}?是文獻(xiàn)[5] 中指定的密鑰派生函數(shù). 對(duì)于任意? ∈N, KDF(·,?) 是一個(gè)長(zhǎng)度為klen 的比特串. 令H是一個(gè)哈希函數(shù), 在安全性證明中將用隨機(jī)預(yù)言機(jī)來(lái)代替.

性能分析. 本文首次基于國(guó)密算法SM2 構(gòu)造了一個(gè)隨機(jī)數(shù)可重用的多接收方公鑰加密方案, 為了更直觀地展現(xiàn)本方案的優(yōu)勢(shì), 我們與基于國(guó)密算法SM2 實(shí)現(xiàn)多接收方功能的一般的構(gòu)造方法進(jìn)行了性能比較. 我們主要從發(fā)送方的計(jì)算代價(jià)和發(fā)送方與接收方的通信代價(jià)兩方面進(jìn)行性能分析. 假設(shè)發(fā)送方要給n個(gè)接收方發(fā)送消息. 在計(jì)算代價(jià)方面, 如表1 所示, 其中GC、KDF、XOR、H 分別表示倍點(diǎn)運(yùn)算、KDF函數(shù)運(yùn)算、異或運(yùn)算和哈希函數(shù)運(yùn)算. 本方案要求發(fā)送方在生成n個(gè)不同公鑰加密的密文的過(guò)程中, 只需要選取一個(gè)隨機(jī)數(shù)r和做一次倍點(diǎn)運(yùn)算, 即計(jì)算一次橢圓曲線(xiàn)點(diǎn)c1=rG= (x1,y1)∈F2q. 而使用SM2算法構(gòu)造的一般的多接收方加密算法在生成n個(gè)密文給n個(gè)接收方時(shí), 需要重復(fù)選取n個(gè)隨機(jī)數(shù), 再針對(duì)每個(gè)隨機(jī)數(shù)做一次倍點(diǎn)運(yùn)算, 即需要做n次倍點(diǎn)運(yùn)算. 因此, 與原始方案相比, 本方案能夠有效減少發(fā)送方的計(jì)算量, 提高加密算法效率.

表1 性能分析Table 1 Performance analysis

同時(shí), 我們繪制了在不同接收方數(shù)目的情況下的加密算法的計(jì)算開(kāi)銷(xiāo), 如圖2 所示. 對(duì)比可見(jiàn), 本方案在加密算法的計(jì)算性能上明顯比原始方案有優(yōu)勢(shì).

圖2 加密計(jì)算開(kāi)銷(xiāo)比較Figure 2 Computation overhead comparison of encryption

在通信代價(jià)方面, 如表1 所示. 一般的構(gòu)造方案需要發(fā)送方返回n個(gè)密文c[i] = (c1,i,c2,i,c3,i),i ∈[n], 而本方案只需要發(fā)送方返回密文c=(c1,(c2,i,c3,i)i∈[n]), 與一般的構(gòu)造方法相比, 減少了|c1|(n ?1)bit 的通信量, 其中|c1|=|c1,i|. 在本方案中,c1的長(zhǎng)度為128 bit,c3,i的長(zhǎng)度為64 bit. 因此, 當(dāng)消息m的長(zhǎng)度為64 bit, 即c2,i的長(zhǎng)度為64 bit 時(shí), 本方案可以節(jié)省大約1/2 的通信代價(jià). 與原始方案相比, 本方案具有明顯的通信優(yōu)勢(shì).

5 總結(jié)

本文從區(qū)塊鏈去中心化的多用戶(hù)應(yīng)用場(chǎng)景出發(fā), 結(jié)合我國(guó)當(dāng)前的信息安全需求, 基于國(guó)密算法SM2提出了一個(gè)隨機(jī)數(shù)重用的多接收方公鑰加密方案. 該加密方案不僅能滿(mǎn)足區(qū)塊鏈多接收方場(chǎng)景下的數(shù)據(jù)隱私保護(hù)需求, 與常規(guī)公鑰加密方案相比, 還能顯著降低加密算法中隨機(jī)數(shù)生成過(guò)程的計(jì)算成本. 而且, 該加密方案是基于國(guó)密算法構(gòu)造而成, 能更好地滿(mǎn)足國(guó)內(nèi)現(xiàn)實(shí)應(yīng)用的安全需求和相關(guān)行業(yè)監(jiān)管要求.