BFV-MKFHE: 基于BFV 的多密鑰全同態加密方案設計*

楊亞濤, 趙東倉, 李兆夫, 劉亞奇

1.北京電子科技學院 電子與通信工程系, 北京100070

2.西安電子科技大學 通信工程學院, 西安710071

1 引言

在當前大數據與云計算背景下, 高效安全的數據處理顯得尤其重要.云計算技術解決了本地計算資源匱乏的問題, 使得外包任務和數據成為人們共享信息和處理數據的主要方式.云計算在成本和效率方面為我們提供便利的同時, 也帶來了很多機密性問題和隱私泄露隱患.當今社會, 人們對數據安全和隱私保護的要求越來越高, 因此, 如何在數據計算過程中保證用戶數據的隱私性和安全性, 成為云環境中迫切需要解決的實際問題.

全同態加密(fully homomorphic encryption, FHE) 技術因其密文可計算的突出優勢在眾多隱私保護手段中脫穎而出, 為隱私計算提供了一種有效的解決方案.常規的全同態加密方案主要包括公私鑰生成、加密、密文運算和解密四個過程, 具體過程示意如圖1 所示.

圖1 常規全同態加密(FHE) 運算示意圖Figure 1 Traditional full homomorphic encryption (FHE) operation

1978 年Rivset 等人[1]提出隱私同態的概念; 直到2009 年,Gentry 給出了全同態加密方案[2,3]的理論證明, 它的結構由三部分構成: 首先, 構造一個有限同態加密方案, 可以評估有限復雜度的函數; 其次, 盡可能簡化該方案的解密方案; 最后, 對簡化的解密函數進行同態計算, 得到最終密文.楊亞濤等人在SEAL(simple encrypted arithmetic library) 全同態加密庫的基礎上先后設計了同態加權電子投票系統[4]和同態密文指紋識別系統[5], 拓展了同態密碼的應用價值, 推動了全同態密碼從理論層面走向實際應用的進程.文獻[6] 通過分析研究近年來國內外在同態密碼領域的相關研究成果, 對當前同態密碼的發展情況、應用現狀以及未來可能的研究與發展方向做了詳細描述.

多密鑰全同態加密(multi-key fully homomorphic encryption, MKFHE) 技術允許對獨立密鑰加密的不同數據進行計算, 同態計算后的密文由所有參與者使用自己的私鑰分布式解密, 再將各部分解密結果聯合起來得到最終結果(如圖2–3 所示), 這是常規全同態加密技術無法實現的.

圖2 多密鑰全同態加密(MKFHE) 運算示意圖Figure 2 Multi-key fully homomorphic encryption (MKFHE) operation

隨著多方安全計算技術的發展, 在同態加密的實際應用中, 通常需要面對多用戶多密鑰的場景, 而傳統的全同態加密技術的同態計算只能對使用相同身份創建的密文(同一密鑰下的密文) 執行, 這一固有的缺陷使得FHE 的實際應用有著較大的局限性.為了在多用戶場景下解決隱私計算問題, 人們開始了MKFHE 方案的探索研究.

2012 年, López-Alt 等人[7]提出了第一個MKFHE 的構造LTV12, 基于NTRU (number theory research unit) 加密系統首次給出了MKFHE 的概念.后續較多構造方案均是在此基礎上得到的.多密鑰全同態加密技術的良好特性使得其在處理安全多方計算問題時具有顯著優勢, 未來將得到更廣泛的應用,因此在該方向的理論與應用研究具有很大的現實意義.

2 相關工作

在 TCC 2017 上, Chen 等人提出了一個新的安全性基于環 LWE 問題的多跳 MKFHE 方案CZW17[8].不同于以往關于標準假設的基于GSW 型的MKFHE 方案, 該方案的架構建立在BGV型的FHE 上, 該方案繼承了BGV 方案的優點, 可以加密一個環形元素作為明文, 并支持基于CRT (Chinese Remainder Theorem) 的密文封裝技術.此外, 該方案密文擴展程序的復雜性只取決于所涉及的密鑰數量, 而無關乎密文數量.2019 年, Chen 等人設計了BFV 與CKKS 方案的多密鑰變體, 創造性提出利用單一加密算法構造用戶私鑰的組合密文來生成重線性化密鑰(計算密鑰) 的新思路, 且無需對私鑰密文擴展, 與之前借助GSW 方案生成計算密鑰的技術相比, 該計算密鑰生成算法更簡潔快速.由此構造了高效的MKFHE 方案CDKS19[9], 并對該方案進行了應用研究.相比于CZW17 和LZY+19[10]方案, 該方案在空間和時間復雜度上都有所降低.

當前主流的MKFHE 方案按照基于的全同態加密系統不同, 主要分為以下四種類型:

第一種類型是NTRU 型的MKFHE 方案.該類型以López-Alt 等人[7]在2012 年首次提出的MKFHE 方案LTV12 為代表, 該方案首次給出了MKFHE 的密碼學定義.2020 年, Chen 等人構造了一種在同態運算后無需使用密鑰轉換技術進行密文維度約減的NTRU 型MKFHE 方案CZL+20[11],在一定程度上降低了密鑰尺度.2020 年, 李瑞琪等人[12]設計了一個基于NTRU 的支持批處理的層級MKFHE 方案, 該方案使用工具向量(gadget vector) 相關技術, 在構造方法上相比以往MKFHE 更為簡潔, 較大程度降低了計算復雜度和通信開銷.

第二種類型是GSW 型的MKFHE 方案.2013 年, Gentry 等人提出了第一個基于身份的完全同態(IBFHE) 加密方案GSW13[13], 然而他們的方案只在單一身份設置下有效.2015 年, Clear 和Mc-Goldrick 在GSW13[13]方案基礎上, 將結果推廣到多身份的情況下, 在標準模型下構造了基于LWE 安全的MKFHE 方案CM15[14].該方案是第一個基于標準LWE 成熟假設的MKFHE 方案, 此后人們在此基礎上提出了更多優化和擴展方案.在TCC2016 上, Peikert 和Shiehian 提出了基于GSW 的多跳(multi-hop) 多密鑰全同態加密方案PS16[15], 該方案比以前的基于LWE 的方案具有更小的密文尺度.緊接著, Brakerski 和Perlman 構造了一個基于LWE 安全的全動態(fully dynamic) MKFHE 方案BP16[16], 該方案支持無限次的同態操作, 適用于動態增加的多個參與方; 此外, 該方案的密文尺度和同態操作的空間復雜度只相對當前各參與方數量呈線性增長.

第三種類型是BGV 型的MKFHE 方案.2012 年, Brakerski 等人構造了BGV12 方案[17], 該方案在同態計算后使用密鑰交換(key-switching) 技術對膨脹的密文維度進行約減, 是另一種形式的重線性化技術.另外, BGV 型方案涉及到模數交換(modulus-switching) 技術, 這是與BFV 型方案最大的不同之處.該類型的代表性方案除了上文提到的CZW17[8]和CDKS19[9]之外, 在2019 年, Li 等人構造了BGV型MKFHE 方案LZY+19[10], 該方案給出GSW 的可分離密文擴展, 可以將擴展密文的大小縮小一半左右; 其次, 方案在計算密鑰生成過程中使用RBGV 密文和RGSW 密文的混合同態乘法, 可以顯著減少輸入/輸出密文的數量, 進而提高效率; 最后, 該方案構造了一個定向解密協議, 允許被評估的密文被任何目標用戶解密, 并消除了現有MKFHE 方案中被評估密文只能由參與同態計算的用戶解密的限制.

第四種類型是TFHE 型的MKFHE 方案.在ASIACRYPT 2016 上, Chillotti 等人構造了FHE方案CGGI16[18].緊接著, 在ASIACRYPT 2017 上, Chillotti 等人在CGGI16 方案的基礎上提出了CGGI17[19]方案, 該方案可以減少密文擴展.在ASIACRYPT 2019 上, Chen 等人基于Chillotti 等人在ASIACRYPT 2016 上設計的低延遲同態加密思路, 提出了一個MKHE 方案CCS19[20], 該方案構造的密文尺度和同態計算的計算成本分別以線性和四次方的方式增長, 與以前的工作相比, 在具體復雜度方面更有效率.

此外, 在量子同態領域也有相應的多密鑰方案.比如在方案DSS16[21]的基礎上發展而來的MKFHE方案Goy18[22].

2020 年, 李寧波等人[23]對當前MKFHE 領域的各類文獻成果進行了分析歸納, 詳細介紹了每個類型中典型的MKFHE 方案的構造方式, 并分別對其存在的問題進行了分析對比, 在此基礎上, 對未來一段時間多密鑰全同態加密的研究方向與趨勢做出了展望.

通過以上分析可以看到, 之前絕大多數高效的多密鑰全同態加密方案都是基于或利用GSW 方案來構造的, 且普遍存在以下兩個問題: 第一, 密鑰交換(重線性化) 過程通常較為繁瑣, 計算復雜度較大, 從而影響了整個方案的效率.這主要是由于計算密鑰的生成往往需要借助GSW 等方案, 所需的密鑰在數量和尺度上都難以降低.第二, 密文運算會產生較多的噪聲, 噪聲是影響全同態加密方案性能的重要因素, 在多密鑰的情況下, 對噪聲的控制顯得尤其重要, 現有的方案應對噪聲積累大多缺乏有效措施.

BGV 與BFV 同為第二代全同態加密的代表性算法, BGV 方案主要涉及到一個模數轉換技術, 在BGV 方案中, 模數的選取與每次需要減少的噪聲大小有關, 也與需要執行的算術電路有關, 因此BGV 的可用性受到一定限制.然而在BFV 中, 模數能夠選取到軟件/硬件能表達的最大位數, 并且由于BFV 將模數轉換的方案隱式包含在了乘法運算中, 所以BFV 方案不需要額外的技術手段來解決這個問題.相關實驗證明, 在明文空間模數較小的情況下, BFV 方案比BGV 方案的效率更高, 但是針對BFV 設計的多密鑰全同態加密方案較少, 因此本文采用BFV 算法的基本架構, 通過修改GZW17 方案的密鑰交換、模數轉換等過程, 優化加解密算法, 提出了一種基于BFV 的多密鑰全同態加密方案, 該方案繼承了第二代FHE 方案的優點, 可以加密環上的明文.在密文/明文比率、同態操作的復雜性和其他通信開銷方面, 比以前的工作更為有效.

本文提出的基于BFV 的多密鑰全同態加密方案, 主要貢獻為:

(1) 提出了一種高效的基于BFV 的MKFHE 方案, 稱為BFV-MKFHE 方案.我們將CZW17 方案的BGV 加密算法的結構修改為BFV 加密算法的結構, 減去了模數轉化過程, 使得加密算法更為簡潔,可以在一定程度上提高同態運算效率.此外, 本方案通過改變加密運算的取整方式來對加密算法進行優化,該方法減少了計算冗余, 在一定程度上減緩了噪聲積累.

(2) 修改了CZW17 方案中計算密鑰的生成過程, 使得多密鑰重線性化算法更簡潔高效.本方案通過單一加密算法來加密用戶私鑰, 用最終生成的組合密文來生成計算密鑰, 重線性化算法建立在效率更高的CDKS19 方案的基礎上, 并通過模數提高技術對算法進行優化, 降低了同態運算的計算復雜度.本方案完成一次同態乘法解密時產生的噪聲值減小為CDKS19 方案的1/p,生成計算密鑰的密文尺寸相比CZW17方案和LZY+19 方案約減小1/4, 運算效率更高.

3 預備知識

3.1 符號定義

文中斜體的大寫字母(例如A)表示矩陣,斜體的小寫字母(例如a)表示向量,a[i]表示向量a中的第i個元素.給定一個概率分布D, 用x ←D表示x是D中的采樣.對于集合S,x ←S表示從S中均勻采樣出X.本文的方案建立在環R==Z[x]/(xn+1)上,λ為安全系數,χ是R上的錯誤概率分布,K為參與方數量上限,L表示電路深度, 令l=L,···,0.選擇整數n=n(λ), 定義多項式環R=Z(x)/xn+1,多項式環R 上的噪聲分布為χ=χ(λ,K,L),q=ploy(n) 為密文模數.

3.2 RLWE 問題與比特分解函數

環上帶錯學習問題RLWE 最初由Lyubashevsky 等[24]提出, 定義如下:

對于安全參數λ, 設f(x) 是一個循環多項式Φm(x), 其deg(F) = Φ(M) 取決于λ, 并設置R=Z[x]/(f(x)).設q=q(λ)≥2 為整數.對于隨機元素s ∈Rq和在R上的分布χ=χ(λ), 用Aqs,χ表示通過選擇均勻隨機元素a ←Rq和噪聲項e ←χ得到的分布, 輸出(a,[as+e]q).RLWEd,q,χ問題是區分分布和均勻分布U(R2q) 的不同.

2012 年Micciancio[25]給出了工具向量(gadget vector)g和比特分解函數g?1(·) 的概念, 具體來說, 如果令g= (gi)∈zd為一個工具向量,q是一個整數, 比特分解函數g?1是一個將一個元素a ∈Rq轉化為一個向量u=(u0,u1,···,ud?1)∈Rd的函數, 且滿足

3.3 BFV 全同態加密算法

2012 年, Fan 等人[26]通過對Brakerski 所提方案[27]進行優化, 提出了BFV 同態方案.BFV 方案建立在環R=Z[x]/(xn+1) 上,λ為安全系數,t為約減明文多項式的系數,χ是R上的錯誤概率分布,ω是對數的底數.BFV 全同態加密方案共包括私鑰生成、公鑰生成、計算密鑰生成、加密、解密、同態加法和同態乘法7 個算法.該方案具體算法如下:

4 BFV-MKFHE 方案設計

4.1 多密鑰重線性化算法的設計與優化

在單密鑰情況下, 基于RLWE 的密文進行同態乘法包括兩個步驟: 向量乘法和重線性化.對于輸入的密文ct1和ct2, 首先計算它們的向量乘積, 得到一個滿足＜ct,sk?sk＞=＜ct1,sk＞·＜ct2,sk＞的擴展密文.由于sk·sk 包含非線性部分s2, 所以需要執行作為同態運算核心操作的重線性化程序, 將擴展的密文轉換為加密相同明文信息的典型密文.這個過程需要一個重線性化密鑰(計算密鑰), 它是通過在sk 下加密s2得到的, 因此, 重線性化的過程可以理解為一個密鑰切換過程.

本文的重線性化算法建立在CDKS19 方案的基礎上, 通過構造用戶私鑰的組合密文來生成計算密鑰,并通過應用模數提高技術對算法進行改進, 該算法無需對用戶私鑰的密文進行擴展, 同時盡可能來降低同態運算的計算復雜度, 具有較好的性能.

4.1.1 計算密鑰的生成算法設計

在多密鑰同態算法中, 計算密鑰的生成與使用是影響算法效率與性能的關鍵環節, 其中如何降低計算密鑰生成的復雜度是需要考慮的主要問題.本節中借助單一加密算法[9]來生成計算密鑰, 具體步驟如下:

Setup(1λ): 給定一個安全參數λ, 設置RLWE 的維度n、密文模數q、特殊模數p、密鑰分布χ、環上的錯誤分布Ψ.生成一個隨機向量a ←U(Rdq), 最后, 返回公共參數pp=(n,q,p,χ,Ψ,a).

KeyGen(pp): 選取私鑰s ←χ, 錯誤向量e ←Ψd, 輸出公鑰b=?s·a+e(modq)∈Rdq.公共參數pp 包含一個隨機生成的向量a ∈Rdq, 作為共同參考字符串模型, 同其他MKHE 方案一樣, 所有各方都應該采取相同的公共參數作為密鑰生成算法的輸入, 以支持多密鑰同態運算.

UniEnc(μ,s): 輸入一個明文m ∈R, 輸出一個密文D=[d0|d1|d2]∈Rd×3q, 具體步驟如算法1 所示.

4.1.2 模數提高技術的引入

算法3 模數提高的重線性化算法MR-Relin(ct,(Di,bi)1≤i≤k)Input: 一個擴展密文ct = (ci,j)0≤i,j≤k, k 對計算密鑰和公鑰組合{(Di,bi)}1≤i≤k Output: 一個密文ct′ = (c′i)0≤i≤k ∈R(k+1)q 1 令(c′i)0≤i≤k ←0;2 for 1 ≤i ≤k do i,j ←< g?1(ci,j),bj > (mod pq),4 c′3 c′′i,j ←?p?1 ·c′′i,j?,5 (c′′0,c′′i) ←(c′′0,c′′i)+g?1(c′i,j)[di,0|di,1](mod pq),j ←c′j+ < g?1(ci,j),di,2 > (mod pq);7 end 8 計算c′0 ←c0,0 +?p?1 ·c′′0 ?(mod q);9 對所有的1 ≤i ≤k, 計算c′1 ←c0,i +ci,0?p?1 ·c′′i ?(mod q).6 c′′

4.2 加密算法取整方式的優化

噪聲是影響全同態密碼算法性能的主要障礙.在密文域上進行同態計算將導致噪聲增長, 特別是同態乘法引起的噪聲增長更為顯著, 當噪聲增加到一定程度時, 解密算法將失敗.在BFV 的加密算法中, 明文m ∈Rt, 公鑰表示為pk=(p0,P1), 作抽樣e1,e2←χ, 密文可以表示為

4.3 BFV-MKFHE 方案構造

本節詳細給出BFV-MKFHE 方案的6 個算法,即MKFHE.Setup、MKFHE.KeyGen、MKFHE.Enc、MKFHE.CTExt、MKFHE.Eval、MKFHE.Dec.

(1) MKFHE.Setup(1λ,1k,1l)在給定安全參數λ的情況下, 定義K為參與方數量上限,L表示電路深度, 令l=L,···,0.選擇整數n=n(λ), 定義多項式環R=Z(x)/xn+1, 多項式環R上的噪聲分布為χ=χ(λ,K,L),

由于在部分解密過程中使用噪聲泛洪技術(noise flooding techniques) 引入噪聲項ei ←?(?為噪聲分布).該步驟的安全性是基于LWE 困難問題的, 公布的各部分解密結果為m?i= [cisi+ei]q,并不會泄露用戶私鑰si.該方案加密算法的安全性是基于RLWE 困難問題,滿足IND-CPA安全的, 修改后的聯合解密算法是具有已知系數的秘密的(近似) 線性組合.因此, 在以上分布式解密過程中公布部分解密結果不會泄露用戶信息(明文或密鑰).

算法4 多密鑰全同態密文擴展MKFHE.CTExt(ct1,ID1,ct2,ID2)Input: 兩個密文組{ct1 = (c10,c11,··· ,c1,k1),ID1 = (id11,id12,··· ,id1k1)},{ct2 = (c20,c21,··· ,c2,k2),ID2 = (id21,id22,··· ,id2k2)}Output: 兩個擴展密文組{ct1 = (c?10,c?11,··· ,c?1k),ID1 = (id1,id2,··· ,idk)},{ct2 = (c?20,c?21,··· ,c?2k),ID2 = (id1,id2,··· ,idk)}1 ID1 =ID2 = ID1 ∪ID2 = (id1,id2,··· ,idk), k ≥max{k1,k2}, 所有參與用戶合并為一個集合, 則可以共享同一組私鑰sk = (1,s1,··· ,sk).2 令c?10 = c10, 對所有的1 ≥i ≥k, 令c?1,i =■■ ■c1,j, idi = id1j(1 ≥j ≥ki)0, else , 即原有用戶的密文不變, 新用戶的密文位置補零.

5 方案證明與分析

5.1 正確性證明

由以上推導可以證明方案中所使用的重線性算法的正確性.

5.2 安全性分析

BFV-MKFHE 方案是在典型BFV 加密算法的基礎上設計的, 借鑒了LZY+19 方案和CDKS19 方案中的計算密鑰的生成算法, 并重構優化了加解密方式, 其安全性仍是基于RLWE 困難問題.

如前所述, 該MKFHE 方案包含了單一加密算法.密文是通過將編碼后的明文添加到隨機加密的零中產生的.因此, 只需證明零的隨機加密在計算上與隨機變量沒有區別即可, 證明如下:

定義一個隨機變量(a,b,c0,c1)∈R4q, 其中a ←U(Rq),b=?s·a+e(modq) 滿足s ←χ,e ←Ψ;(c0,c1) =v·(b,a)+(e0,e1)(modq) 滿足v ←χ,e0,e1←Ψ.首先, 將b的定義優化為b ←U(Rq), 由于參數(n,q,χ,Ψ) 下私鑰s的RLWE 問題是困難的, 所以它們在計算上是不可區分的.然后, (b,c0) 和(a,c1) 可以被看作是秘密v的兩個RLWE 密文, 在同樣的RLWE 假設下, 它們與均勻隨機變量U(R2q)在計算上是不可區分的.

只需要將密文模數設為pq, 就能得到模數提高技術下的單一加密算法和重線性化算法.因此, 我們也可以證明在參數為(n,q,χ,Ψ) 的RLWE 假設下, 該MKFHE 方案的模數提高技術是IND-CPA 安全的.

以上分析證明, 我們設計的BFV 型MKFHE 方案BFV-MKFHE 的安全性等同于LZY+19 方案和CDKS19 方案的安全性, 滿足IND-CPA 安全.

5.3 重線性化算法噪聲分析

BFV-MKFHE 方案主要通過在重線性化算法中使用模數提高技術來減少噪聲積累的, 因此本節主要對重線性化算法的噪聲進行分析.

本文算法中的噪聲呈現高斯分布, 所以本節通過計算噪聲的方差, 對噪聲進行評估和對比分析.

通過以上模數提高技術使用前后重線性化算法噪聲的方差對比, 可以得出結論: 使用模數提高技術可以使得重線性化算法噪聲降低.

5.4 性能分析

BFV-MKFHE 方案借鑒了CDKS19 方案中較為簡潔的重線性化思路, 并通過模數提高技術加以優化, 同時通過改變加密時的取整方式, 減少了加密算法的噪聲積累, 降低了計算冗余.與BGV 型的MKFHE 方案CZW17 和LZY+19 相比, 省去了每一層的模數轉換環節, 同時簡化了計算密鑰的生成過程, 較大程度降低了算法的計算復雜度, 同態運算的效率更高.

表1 提供了BFV-MKFHE 方案與幾種典型方案的主要特征比較.由表1 可知, BFV-MKFHE 方案的三個基本特征與CZW17 相同, 兩者的安全性都是基于RLWE 假設, 多個密鑰環且支持批處理.

表1 BFV-MKFHE 方案與其他方案的主要特征比較Table 1 Comparison of main features of BFV-MKFHE scheme with other schemes

表2 是本方案與目前經典的MKFHE 方案(CZW17 方案、LZY+19 方案、CDKS19 方案) 的部分性能對比.從表2 中可以看出, 本方案中計算密鑰密文的尺寸相對于CDKS19 方案沒有改變, 但較CZW17方案與LZY+19 方案約減小1/4, 且無需對用戶私鑰的密文進行擴展.CDKS19 方案一次同態乘法解密時產生的噪聲值相較于前兩個方案均降低了n倍, 由于本方案在重線性化之前使用了模數提高技術, 所以使得一次同態乘法解密時產生的噪聲值減小為CDKS19 方案的1/p.此外, 本方案優化了BFV 加密算法中的取整方式, 降低了計算冗余, 與以往方案的綜合比較可知, 本方案的運算效率更高.

表2 BFV-MKFHE 方案與其他方案的部分性能比較Table 2 Partial performance comparison of BFV-MKFHE solution with other solutions

6 小結

本文在CZW17 方案的基礎上構造了基于BFV 的多密鑰全同態加密方案BFV-MKFHE, 在保證運算效率和安全性的同時, 繼承了BFV 方案不需要模數轉換的優點.在計算密鑰的生成上, 借鑒了CDKS19 方案中較為簡潔的單一加密算法, 并利用模數提高技術進行優化, 使得在同態操作的復雜性和其他通信開銷方面, 比以前的研究工作更有效.相對于CDKS19 方案, 計算密鑰密文的尺寸相同, 且無需對用戶私鑰的密文進行擴展.相對于CZW17 方案與LZY+19 方案, 本方案在計算密鑰的密文尺寸、一次同態乘法產生的噪聲值以及是否需要擴展計算密鑰的密文方面均有所提升.下一步, 將研究如何進一步減小生成計算密鑰的密文尺寸, 提高全同態運算的效率.