一個基于NTRU 的多密鑰同態(tài)加密方案*

李瑞琪, 賈春福

1. 南開大學 網絡空間安全學院, 天津300350

2. 天津市網絡與數(shù)據(jù)安全技術重點實驗室, 天津300350

1 引言

全同態(tài)加密(Fully Homomorphic Encryption, FHE) 是一種新型密碼學工具, 其支持在加密信息上進行任意函數(shù)運算, 并且解密后得到的結果與在明文上執(zhí)行相應運算的結果一致. 全同態(tài)加密的特性使其能夠廣泛應用于云計算、物聯(lián)網等多種計算場景. 同態(tài)加密的思想最初由Rivest 等人[1]在1978 年提出(最初的概念被稱作“privacy homomorphism”), 但在此之后一直都沒有具體的構造方法, 直到2009 年Gentry 才構造出了第一個全同態(tài)加密方案[2,3]. 在Gentry 的開創(chuàng)性工作之后, 一系列關于全同態(tài)加密的研究成果相繼出現(xiàn)[4-8].

多密鑰全同態(tài)加密(Multi-Key Fully Homomorphic Encryption, MKFHE) 是FHE 在多用戶場景下的一種推廣, 其支持多方用戶以各自的密鑰對消息進行加密, 得到的密文可以一起參與運算, 運算結束后將各參與方的密鑰收集起來得到聯(lián)合密鑰, 再用聯(lián)合密鑰對結果密文進行解密. MKFHE 在安全多方計算中有著重要應用. 當前有關MKFHE 方案構造的研究主要可以分為以下三類:

· 基于NTRU 方案. López 等首次提出了MKFHE 的概念,并且構造了第一個MKFHE 方案[8](下稱LTV12 方案), 該方案是基于NTRU 加密體制[9,10]的. 作者利用重線性化(relinearization)和模交換(modulus switching) 技術獲得一個層級多密鑰全同態(tài)加密(leveled MKFHE) 方案.

· 基于Gentry-Sahai-Waters (GSW) 方案. 2015 年, Clear 等[11]構造了一個以GSW 方案[7,12]為基礎的MKFHE 方案, 隨后Mukherjee 等[13]對Clear 的方案進行了改進. 由于這兩個方案需要在進行密文運算前就確定所有參與的用戶, 因此這兩個方案被稱作單跳的(single-hop). 相對應地, Peikert 等[14]在2016 年提出了多跳的(multi-hop)MKFHE 方案(下稱PS16 方案), 其支持運算得到的結果密文繼續(xù)參與到接下來的計算中, 也支持新用戶中途加入運算. 同年, Brakerski等[15]提出了與多跳類似的概念——全動態(tài)(fully dynamic), 并構造了一個全動態(tài)的MKFHE 方案(下稱BP16 方案), 該方案支持任意用戶在任意時刻加入運算. 多跳與全動態(tài)的區(qū)別僅在于是否需要在同態(tài)計算前輸入參與運算的用戶數(shù)的上限.

· 基于Brakerski-Gentry-Vaikuntanathan (BGV) 方案. 2017 年, Chen 等[16]提出了一個基于BGV[5]方案的MKFHE 方案(下稱CZW17 方案). 該方案支持加密環(huán)中的元素而不只是1 比特, 并且該方案能夠加入批處理機制.

上述三種類型的方案推動了MKFHE 的研究, 但仍然存在著一定的問題. 這些方案存在的最主要問題是, 參與運算的用戶除了生成公私鑰以及對消息進行加解密外, 還需產生大量額外的參數(shù)以保證多密鑰的同態(tài)密文計算能夠進行, 例如LTV12 方案、BP16 方案和CZW17 方案中需要用戶生成運算密鑰(evaluation key), PS16 方案則需要用戶生成extension key 或冗余的密文, 這增加了用戶端的計算開銷.另外, 基于BGV 和基于GSW 的方案都需要進行密文擴張, 因為這兩類方案中解密密鑰的維數(shù)會隨著用戶數(shù)的增加而增加, 這使得密文的尺寸也要隨之增加才能正確解密.

為了解決上述問題, 我們提出了一種新的多密鑰同態(tài)加密方案, 利用工具向量和相應的分解函數(shù)將NTRU 方案轉化成leveled MKFHE 方案. 本文所提方案的主要優(yōu)勢在于:

· 用戶端只需要生成公鑰和私鑰以及對消息進行加解密, 并不需要生成evaluation key 或其他額外的參數(shù), 減輕了用戶端的計算負擔.

· 使用比特分解技術來構造HE 方案,這使得密文加法和乘法能夠簡單地實現(xiàn),不需要加入其它輔助技術(如relinearization);也使得NTRU 直接轉化為leveled MKFHE 方案,從而不需要modulus switching 技術. 整個方案更加簡潔、易于實現(xiàn).

· 不需要進行密文擴張, 即密文的(最大) 尺寸是不變的.

· 支持加密環(huán)中的元素而并不只是1 比特, 因而本方案可以擴展成支持批處理的MKFHE 方案.

另外,我們的方案是一個leveled MKFHE 方案,仍需要利用Gentry 的bootstrapping 定理將leveled MKFHE 方案轉化為一個完全的MKFHE 方案.

2 預備知識

本文中我們使用加粗大寫字母表示矩陣, 如M; 使用加粗小寫字母表示向量, 如v. 在矩陣中, M[i,j]表示位于第i 行第j 列的元素; 在向量中, v[i] 表示向量中的第i 個元素. 矩陣和向量中的元素標號從1開始. 本文中運算符“·” 表示矩陣乘法, 包括矩陣-矩陣乘法和標量-矩陣乘法(向量可以看作n×1 或者1×n 的矩陣).

其中δ 是一個只與環(huán)R 有關的常數(shù), 稱作環(huán)常數(shù).

2.1 離散高斯分布

我們將均值為0、標準差為r 的離散高斯分布記作DZn,r. 在本文中唯一需要用到的有關離散高斯分布的性質是, 從DZn,r中抽取的樣本的范數(shù)大概率在某一范圍內. 由此我們可以定義如下的概念:

定義1[8]如果一族分布{χn}n∈N滿足

則稱其為B 界分布.

而離散高斯分布有如下性質:推論1[8]令R=Z[x]/〈φm(x)〉. 令χ 為R 上的B 界分布, 設f1,f2,··· ,fk←χ, 有

2.2 RLWE 問題與DSPR 假設

環(huán)上帶錯學習問題(Ring Learning With Errors, RLWE) 最初是由Lyubashevsky 等[17]提出的, 判別版本的RLWE 問題定義如下:

定義2[17]設U(X) 為集合X 上的均勻分布. 給定一個秘密多項式s ∈Rq, 一個R 上的分布χ, 我們定義一個Rq× Rq上的分布As,χ: 隨機選取a ←U(Rq), 隨機抽取一個差錯e ←χ, 輸出(a,b = a·s+e). 判別版本的RLWE 問題(記作DRLWEq,χ) 定義為: 當s ←U(Rq) 時, 區(qū)分As,χ與U(Rq×Rq) 兩個分布.

下面的定理闡述了問題DRLWEq,χ的困難性, 即區(qū)分As,χ與U(Rq×Rq) 這兩個分布是困難的.

2.3 多密鑰同態(tài)加密

一個多密鑰同態(tài)加密方案包含四個算法(KeyGen, Enc, Dec, Eval), 具體描述如下:

· (pk, sk)←KeyGen(1λ): 給定安全參數(shù)λ, 輸出公鑰pk 和私鑰sk;

· c ←Enc(pk,m): 輸入消息明文m 和公鑰pk, 輸出密文c;

· m:=Dec(sk1,sk2,···,skN,c): 輸入密文c, 以及密文所對應的運算參與方的私鑰sk1,sk2,···,skN,輸出消息明文m;

· (c*,S) := Eval(C,(c1,S1),(c2,S2),··· ,(ct,St)): 算法的輸入包括一個電路C, 以及t 個元組(ci,Si),i ∈{1,··· ,t}. 每個元組中包括一個密文ci和其對應的用戶(密鑰) 集合Si. 算法的輸出為結果密文c*和其對應的用戶(密鑰) 集合S =∪Si(在用戶(密鑰) 集合中可以找到任意參與運算的用戶的公私鑰).

2.4 Bootstrapping

Gentry 在文獻[2,3] 中提出了“bootstrapping” 技術, 該技術利用重加密的思想更新密文, 從而控制噪聲膨脹以保證解密正確性, 進而實現(xiàn)任意次的密文同態(tài)運算. Gentry 的bootstrapping 定理也可以用于多密鑰的場景. 具體來說, 該技術要求HE 方案能夠對“增強解密電路(augmented decryption circuit)”進行處理, 同時也需要該HE 方案具有弱循環(huán)安全性(weakly circular secure). 有關bootstrapping 技術的更多細節(jié)參見文獻[2,3].

定義4 令E 為一個多密鑰同態(tài)加密方案. 該方案的增強解密電路fc1,c2定義為

定義5 如果一個公鑰加密方案在敵手獲得其私鑰的所有比特的密文時仍然是IND-CPA 安全的, 則稱該方案具有弱循環(huán)安全性.

結合定義4 和5, 可以得到多密鑰版本的bootstrapping 定理如下:

定理2 如果一個多密鑰同態(tài)加密方案能夠同態(tài)運行其增強解密電路, 并且具有弱循環(huán)安全性, 那么該方案就能轉化為一個完全的多密鑰全同態(tài)加密方案.

2.5 工具向量和比特分解函數(shù)

2.6 中國剩余定理與批處理

中國剩余定理(Chinese Remainder Theorem, CRT) 是一個重要的工具, 該定理內容如下:

定理3[23]設R 是一個環(huán), I1,I2,··· ,Ik是R 中兩兩互素的理想, 于是有

每一個Zp[x]/fi(x) 可以看作一個“明文槽”, 利用該同構可以將k 個Fpd中的明文用Rp中的一個元素來表示, 并且有如下性質: 設(a0,a1,··· ,ak-1),(b0,b1,··· ,bk-1) ∈(Fpd)k是兩組明文, 它們對應的Rp中的元素分別是a,b, 于是計算a+b 相當于計算(a0+b0,a1+b1,··· ,ak-1+bk-1), 計算ab 相當于計算(a0b0,a1b1,··· ,ak-1bk-1). 利用上述原理, 文獻[24] 提出了支持SIMD (Single Instruction Multiple Data) 操作的HE 方案.

在此基礎上, 文獻[25] 利用Rp上的自同構映射a(x)a(xj) 并結合Bene?/Waksman 置換網絡,可以使明文槽中的元素進行任意置換(permutation). 具體來說, 伽羅瓦群Gal(Q[x]/φm(x)) 中的元素為自同構映射xi,i ∈Z*m, 該伽羅瓦群包含了一個子群G ={xxpi|i=0,1,··· ,d-1}. 文獻[25] 證明了商群H =Gal(Q[x]/φm(x))/G 可以使明文槽中存儲的消息進行輪換(rotation). 因此, 以群H 所包含的自同構映射為基礎再結合Bene?/Waksman 置換網絡, 可以實現(xiàn)明文槽中元素的任意置換.

3 基于NTRU 的多密鑰同態(tài)加密方案

3.1 NTRU 方案

我們首先介紹NTRU 方案, 這是構造我們的MKFHE 方案的基礎.

給定安全參數(shù)λ, 設存在多項式時間的算法輸出以下參數(shù): 素數(shù)q =q(λ), 分圓多項式φm(x)(次數(shù)為n=n(λ)=φ(m)), B(λ) 界分布χ. 方案的明文空間為M=Rp, p 為小整數(shù)(例如2 或3), 方案所涉及到的所有運算均在環(huán)Rq=Zq[x]/〈φm(x)〉 中進行. NTRU 方案由以下三個算法組成:

· NTRU.KeyGen(1λ): 隨機抽取多項式f′,g ←χ, 令f :=pf′+1. 如果f 在Rq中不可逆, 那么重新抽取f′. 輸出公鑰和私鑰

· NTRU.Enc(pk,μ): 隨機抽取多項式s,e ←χ. 輸出密文

· NTRU.Dec(sk,c): 計算μ′=f ·c ∈Rq, 輸出

當‖fc‖∞≤q/2 時, 解密的結果是正確的, 這是由于此時fc mod q =fc.

3.2 基于NTRU 的多密鑰同態(tài)加密方案

這一小節(jié)介紹我們的基于NTRU 的多密鑰同態(tài)加密方案.

給定安全參數(shù)λ, 設存在多項式時間的算法, 輸出素數(shù)q = q(λ), 分圓多項式φm(x)(次數(shù)為n =φ(m) = n(λ)), B(λ) 界分布χ. 設基為ω, ?q=, 工具向量為g = (1,ω,ω2,··· ,ω?q-1), 明文空間為M = Rp, 令p 為小整數(shù)且滿足p ≤ω ＜q, 所有的運算均在Rq中進行. 我們的多密鑰同態(tài)加密方案包括以下四個算法:

· MKHE.KeyGen(1λ): 調用NTRU.KeyGen(1λ), 輸出公鑰和私鑰

· MKHE.Enc(pk,μ): 隨機抽取?q組si,ei←χ 用于計算NTRU.Enc(h,0) 來得到?q個“0 的密文”, 然后將得到的?q個0 的密文組成一個向量c0∈, 最后輸出密文

· MKHE.Dec(sk1,sk2,···,skN,c): 析取每個私鑰ski得到ski= fi, 令聯(lián)合私鑰為sk := f =f1f2···fN. 計算并輸出明文

· MKHE.Eval(C,(c1,S1),(c2,S2),···,(ct,St)): 設密文c1對應的用戶(密鑰) 集合為S1, 密文c2對應的用戶(密鑰) 集合為S2. 密文加法為

密文乘法為

同時, 也需要輸出cadd和cmult對應的用戶(密鑰) 集合S =S1∪S2.

4 方案分析

本節(jié)將對我們提出的MKFHE 方案的有關性質進行分析.

4.1 同態(tài)性分析

從而乘法正確.

在文獻[8] 的最初構造中, 密文c2+需要使用聯(lián)合私鑰f2·解密, 而密文c+～c2需要使用聯(lián)合私鑰f ·解密, 也就是說聯(lián)合私鑰會隨著運算電路的變化而變化. 但我們希望聯(lián)合私鑰僅與參與用戶有關, 而與運算電路無關. 在文獻[8] 中, 作者利用relinearization 技術解決了這個問題. 而在本文中, 我們的MKFHE 方案不需要額外添加任何技術就可以使得聯(lián)合私鑰只與參與用戶有關, 不受運算電路的影響.下面我們來說明這一點.

事實上只需證明在本方案中, 僅使用私鑰f 就能正確解密密文cmult=c·g-1(c) 即可.

與上文類似, 我們可將c·g-1(c) 表示為

以上的推導說明了無論有多少個用同一公鑰加密的密文相乘, 解密時只需使用原私鑰, 這就意味著本方案中的聯(lián)合私鑰與運算電路無關.

4.2 安全性分析

4.3 噪聲分析

在這一小節(jié)中, 我們將分析執(zhí)行同態(tài)運算的過程中, 密文噪聲的增長情況. 首先, 對密文的噪聲進行定義:

定義6 設c 為一個密文, f 為其對應的私鑰. 密文c 的噪聲定義為

對于所有NTRU 類型的方案, 解密正確需要滿足條件‖f ·c‖∞≤q/2. 因此在本方案中, 正確解密需要保證密文噪聲滿足noise(c)≤q/2.

下面的引理給出了執(zhí)行一次同態(tài)運算后密文噪聲的增長幅度.

引理3 令c,c′是兩個密文, 它們對應的明文分別是μ,μ′, 對應的用戶(密鑰) 集合分別為S1,S2. 令c 和c′之間執(zhí)行一次同態(tài)運算(加法或乘法) 后得到的密文所對應的用戶(密鑰) 集合為S =S1∪S2, 且S 中包含N 個用戶(密鑰). 解密cadd=c+c′和cmult=c·g-1(c′) 可以分別得到μ+μ′和μ·μ′. 如果noise(c)≤E,noise(c′)≤E, 那么進行一次同態(tài)運算后, 有noise(cadd),noise(cmult)＜(2pωnδB)2NE,參數(shù)p,ω,δ,n,B 的定義見3.2 節(jié).

證明: 已知每個用戶最初的私鑰fi的范數(shù)上界為pB+1, fS=fi. 根據(jù)推論1 可知‖fS‖∞≤δN-1(pB+1)N＜δN-1(2pB)N. 對于加法有

本方案是一個leveled MKFHE 方案.

證明: 引理3 給出了一次同態(tài)運算后密文噪聲的增長情況, 于是我們可以從初始密文中的噪聲E0＜4p2δB2開始計算L 層(乘法) 運算后密文噪聲的大小. 經過L 層運算后, 密文噪聲增長為為了能夠正確解密，我們需要保證(2pωnδB)2NL+2≤q/2. 已知p = O(1),ω = O(1),B = poly(n), 并且文獻[3] 指出大多數(shù)情況下環(huán)常數(shù)δ 滿足δ =poly(n)(這就要求我們選取滿足此項要求的分圓多項式).根據(jù)上述條件可得

4.4 完全的多密鑰全同態(tài)加密

上文中我們得到的方案是一個leveled MKFHE 方案. 在這一小節(jié)中我們將說明, 可以利用Gentry所提出的bootstrapping 定理, 將leveled MKFHE 方案轉化為完全的MKFHE 方案.

Gentry 在其開創(chuàng)性的工作[2,3]中提出了bootstrapping 定理, 該定理指出如果一個同態(tài)加密方案能夠同態(tài)運行自己的增強解密電路, 那么該方案就能夠轉化為一個完全的全同態(tài)加密方案. 因此, 需要對本方案的解密電路的深度進行衡量. 下面的引理給出了本方案解密電路深度的上界.

引理5 本方案的解密電路可以用GF(2) 上的深度為O(log N·(log log q+log n)) 的算術電路來實現(xiàn).

證明: 假設c 是密文, 其對應的私鑰集合為{f1,f2,··· ,fN}, 那么解密c 的過程可以表示為

文獻[4] 已經證明, 兩個Rq中的多項式的乘法可以通過深度為O(log log q+log n) 的布爾電路來實現(xiàn). N 個多項式相乘可以通過深度為log N 的二叉樹來實現(xiàn), 因此解密過程的布爾電路的深度為

根據(jù)上文的結論, 我們得到定理5.

從而得到定理中的結論.

4.5 批處理

利用中國剩余定理和文獻[24] 中提出的SIMD 技術, 可以將本方案轉化為一個支持批處理的多密鑰同態(tài)加密方案. 當選取合適的參數(shù)p 和分圓多項式時, 我們可以通過CRT 將一組明文(μ1,μ2,··· ,μk)映射為一個多項式μ=CRT(μ1,μ2,··· ,μk), 然后將μ 加密得到密文c. 根據(jù)同態(tài)加密和CRT 映射的特性, 并行加法和乘法可以分別通過密文加法和乘法實現(xiàn). 因此在本小節(jié)中, 我們將主要討論如何進行置換運算. 文獻[25] 提出了以自同構映射為基礎來實現(xiàn)置換的方法, 其中自同構映射是核心技術, 下文將介紹自同構映射在本方案中的應用.

設密文c 對應的明文為μ, 對應的密鑰為f =f1f2···fN, 因此我們可知

其中e(x),k(x)∈R1×?q. 將自同構xxi,i ∈作用于該等式可得

已知φm(x) 能夠整除φm(xi),i ∈, 從而我們可以將c(xi) 看作μ(xi) 關于密鑰f(xi) 的密文. 然而我們需要的密文應當是對應于密鑰f(x) 的密文, 因此我們在進行置換運算時, 需要借助于密鑰交換技術(key switching), 將密文c(xi) 轉化為一個新的密文c′= KeySwitch(c(xi)), 使得新密文能夠用f(x) 解密. 下面將說明本方案中為實現(xiàn)置換運算所需要的密鑰交換過程.

設密文c(x) 對應的聯(lián)合密鑰為f(x) = f1(x)f2(x)···fN(x), 密鑰交換過程KeySwitch(c(xi)) 分為以下2 步:

· 擁有密鑰fj的用戶首先計算cfj= MKHE.Enc(hj,fj(xi)), 然后每個用戶將各自的計算結果cfj發(fā)送到云端.

· 云端計算

得到的計算結果c′即是所需的密文.

其中c(0),f1f2···fN是對應于密鑰f =f1f2···fN的0 的密文. 顯然, 當密文噪聲不超過上界時, c′能夠用f =f1f2···fN解密.

5 方案對比

本節(jié)中我們將對比本方案與其他經典方案在性能上的差異.

首先簡要對比本方案與Dor?z 等人[27]在2016 年提出的方案(下稱DS16 方案) 之間的異同. 本方案與DS16 方案使用了類似的技術(即比特分解) 來處理噪聲的增長, 但是不同之處在于DS16 方案使用了BitDecomp、Flatten 等函數(shù)進行比特分解; 本方案則利用工具向量g 及其相對應的分解函數(shù)g-1(·)進行分解, 此項差異造成了兩個方案的密文大小以及同態(tài)運算的復雜度有所不同. 設n 表示分圓多項式的次數(shù), q 表示模數(shù), 那么DS16 方案中密文的尺寸為O(n log3q), 本方案中密文的尺寸為O(n log2q). 相較于DS16 方案, 本方案中的密文尺寸相對較小. 在同態(tài)運算過程中, DS16 方案需進行(維數(shù)為log q 的, 元素為多項式的) 矩陣加法和矩陣乘法, 本方案則進行的是(維數(shù)為log q 的, 元素為多項式的) 向量加法和矩陣-向量乘法. 相比之下, 本方案的計算復雜度較低. 另外, DS16 方案討論的是單密鑰場景下的同態(tài)加密算法, 不需要DSPR 假設; 而本方案是多密鑰場景下的基于NTRU 的同態(tài)加密方案, 無法避免DSPR假設.

下面我們將與經典的多密鑰同態(tài)加密方案進行對比.

5.1 與LTV12 方案的比較

本方案與LTV12 方案都是基于NTRU 的MKFHE 方案, 既有共同點也有不同點. 兩個方案在噪聲增長、可同態(tài)運行的電路深度等方面有著類似的結論, 但是二者是利用不同的技術達成的. LTV12 方案利用relinearization 技術消除了聯(lián)合私鑰中的平方項, 同時也實現(xiàn)了key switching 的功能; 又使用了modulus switching 技術, 將NTRU 方案轉化為一個leveled MKFHE 方案. 這兩項技術的使用使得LTV12 方案必須在生成公私鑰的同時生成運算密鑰, 并且在進行每一次同態(tài)運算(加法或乘法) 時都需要執(zhí)行relinearization 操作, 每一層同態(tài)運算后都要進行modulus switching, 才能使得方案成為一個leveled MKFHE 方案. 而本方案使用了工具向量和比特分解技術, 使得實現(xiàn)同態(tài)運算所需的操作變得非常簡單,不需要額外的技術,并且直接將NTRU 方案轉化為一個leveled MKFHE 方案. 另外,實現(xiàn)本方案的同態(tài)運算過程僅需要普通的多項式加法和乘法, 以及一個將多項式分解的g-1(·) 函數(shù). 相較于LTV12方案, 本方案更易于理解和代碼實現(xiàn).

表1 中列出了本方案與LTV12 方案的一些基本參數(shù)之間的對比, 其中n 表示分圓多項式的次數(shù), q表示模數(shù). 從表1 中可以看到, 我們的方案不需要運算密鑰, 而LTV12 方案需要尺寸為O(n log3q) 的運算密鑰. 雖然本方案在同態(tài)運算過程中的密文的尺寸是大于LTV12 方案的(表1 中密文尺寸一行), 但是運算后得到的最終密文(解密時所需的密文) 的尺寸與LTV12 方案相同(表1 中最終密文尺寸一行).

表1 與LTV12 方案的基本性質的比較Table 1 Comparisons of basic properties with LTV12 scheme

下面我們將對比本方案與LTV12 方案在云計算場景下, 用戶端和云端分別所需執(zhí)行的操作. 將同態(tài)加密算法應用于云計算場景時, 用戶端需要執(zhí)行的主要操作是生成密鑰和同態(tài)計算所需的參數(shù)(即運行KeyGen算法), 加密(Enc) 和解密(Dec); 云端進行的操作則是對用戶上傳的密文進行同態(tài)運算. 我們對兩個方案在用戶端所需的操作進行比較, 因為在云計算場景中, 我們希望用戶端的開銷能夠盡可能地降低. 比較結果如表2 所示.

我們將表2 中所列出的密鑰生成和加密兩個過程中用戶端所做的操作綜合起來進行對比: 若加密1 比特, 本方案中用戶端所需的全部操作是隨機生成2 個多項式, 進行l(wèi)og q 次多項式乘法和2 log q 次多項式加法; LTV12 方案中用戶端所需的全部操作是隨機生成2(log2q+log q) 個多項式, 進行6 log2q+1 次多項式乘法和8 log2q+2 次多項式加法. 由此可見, 當加密少量比特(例如對稱加密算法的密鑰) 時, 使用本方案在用戶端的計算開銷相對較低, 更符合云計算場景下用戶的計算能力有限的特點.

表2 與LTV12 方案的基本操作的比較Table 2 Comparisons of basic operations with LTV12 scheme

5.2 與BP16、PS16 和CZW17 方案的比較

表3 中bootstrapping 一行表示, 每進行一次(門電路) 運算, 是否需要執(zhí)行bootstrapping. PS16 方案中, 每執(zhí)行一次與非門(NAND) 都要運行一次bootstrapping, 而其他方案并不需要. 從表3 中可以看出CZW17 方案需要生成evaluation key, 因而用戶端的開銷相對較大. PS16 中的兩個方案雖然不需要evaluation key, 但是需要生成額外的密文或公共參數(shù), 以保證多密鑰同態(tài)運算能夠正常進行. BP16 方案是當前理論上效果最佳的MKFHE 方案, 但是從表3 中可知, BP16 方案也需要生成evaluation key, 給用戶端帶來額外負擔. 除此之外, 在BP16 方案中每執(zhí)行一次NAND 運算, 都需要運行一次bootstrapping, 不易于代碼實現(xiàn); 而上文也提到過本方案的同態(tài)運算過程僅需要實現(xiàn)簡單的多項式間的運算. 相較于BP16 方案, 本方案的同態(tài)運算過程更易于理解和代碼實現(xiàn).

表3 與其他MKFHE 方案的比較Table 3 Comparisons with other MKFHE schemes

6 總結

本文提出了一種NTRU 型的多密鑰同態(tài)加密方案. 我們利用工具向量及相應的分解函數(shù)將NTRU方案轉化為一個leveled MKFHE 方案, 并可以利用Gentry 的bootstrapping 定理將leveled FHE 方案轉化為完全的FHE 方案. 由于使用了工具向量及分解函數(shù), 我們的方案不需要使用relinearization 技術,從而不需要生成evaluation key. 與此同時, 本方案也不需要進行密文擴張以及生成額外的公共參數(shù). 相比于已有的MKFHE 方案, 我們的方案更加簡潔、易于實現(xiàn), 并且在云計算環(huán)境下用戶端的開銷相對較小. 另外, 本方案支持加密環(huán)中的元素而不僅是1 比特, 因而也支持多密鑰場景下的批處理同態(tài)運算. 本方案的安全性基于RLWE 問題和DSPR 假設, 而DSPR 假設并不是一個標準的密碼學假設. 盡管到目前為止沒有高效的方法去破解小模數(shù)情形的DSPR 假設, 我們仍可以認為DSPR 假設是安全的, 但是這個安全隱患需要引起關注. 當前, 基于NTRU 的MKFHE 方案無法避免DSPR 假設, 這是由解密時需要所有參與方的私鑰相乘所造成的固有缺陷. 因此如何構造安全性只依賴于RLWE 問題的NTRU 型多密鑰同態(tài)加密方案仍有待進一步研究.