賴俊祚, 黃正安, 翁 健, 吳永東

1. 暨南大學, 廣州510632

2. 鵬城實驗室, 深圳518055

1 引言

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

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

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

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

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

2 預備知識

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

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

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

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

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

而且要求在這兩個實驗中,A都不能向Hv(·) 詢問gu.

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

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

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

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

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

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

接下來, 我們回顧公鑰加密中最常見的一個安全模型: IND-CCA 安全性[10].

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

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

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

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

3.1 方案構(gòu)造

記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為兩個哈希函數(shù). 在本方案的安全性證明中,H2將用隨機預言機[8]來替換.

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

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

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

3.2 安全性證明

本小節(jié)中, 我們給出定理2 和定理3 的完整證明.證明(定理2): 我們構(gòu)造一個針對關(guān)于(G,H1) 的ODH 問題的敵手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.

同時,B給A1提供隨機預言機(即H2) 和解密預言機的詢問服務.

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

通過這樣的方式,B可以回答A2的隨機預言機詢問和解密詢問.

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

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

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

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

4 基于SM2 的RR-MRPKE 實例化方案

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

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

表1 性能分析Table 1 Performance analysis

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

圖2 加密計算開銷比較Figure 2 Computation overhead comparison of encryption

在通信代價方面, 如表1 所示. 一般的構(gòu)造方案需要發(fā)送方返回n個密文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的長度為128 bit,c3,i的長度為64 bit. 因此, 當消息m的長度為64 bit, 即c2,i的長度為64 bit 時, 本方案可以節(jié)省大約1/2 的通信代價. 與原始方案相比, 本方案具有明顯的通信優(yōu)勢.

5 總結(jié)

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