宋新霞, 陳智罡, 李焱華

1. 浙江萬里學院, 寧波315100

2. 復旦大學 計算機科學技術學院, 上海201203

3. 中國科學院 信息工程研究所 信息安全國家重點實驗室, 北京100093

1 前言

全同態(tài)加密無需解密就能夠對密文進行任意計算, 因此可以立竿見影的解決數據隱私安全問題, 有很大的應用需求. 例如, 在云環(huán)境下, 用戶加密數據后存儲在云端, 由于數據加密使得云端無法獲得數據的內容, 從而保證了數據的隱私. 此外, 由于是全同態(tài)加密, 云端可以對密文數據進行任意計算. 因此, 全同態(tài)加密不但保護了數據, 而且沒有喪失計算性[1-3].

在過去的十年里, 學術界對全同態(tài)加密算法進行了大量的研究[2,4-12]. 一些全同態(tài)加密算法已經在軟件中實現[13-18]. 然而, 面對各種全同態(tài)加密算法, 工業(yè)界缺乏一個標準的易于使用的測試工具, 以便讓用戶測試與選擇. 不同全同態(tài)加密庫的比較是困難的. 一方面由于不同全同態(tài)加密算法所基于的噪音管理技術不同, 甚至基于的數學結構也不同. 例如HEAAN 方案支持浮點數計算, 在明文空間上就與BGV 和BFV 等方案有差異. 而且在計算過程上也無法做到統(tǒng)一衡量. 另一方面, 不同電腦不同操作系統(tǒng)的平臺也會導致無法站在同一基準上對各種全同態(tài)加密庫進行客觀統(tǒng)一的比較.

為此, 我們前期對各種全同態(tài)加密算法進行了抽象層面的研究[17]. 該研究為我們探索統(tǒng)一的測試標準提供了理論支持. 在全同態(tài)加密算法中, 有兩個技術非常重要. 一是噪音管理技術, 二是獲得同態(tài)性技術(主要指的是獲得乘法同態(tài)性). 這些關鍵技術在各個全同態(tài)加密庫中都是不同的. 盡管這些關鍵技術在理論設計中非常重要, 但是對于測試而言不是用戶所關心的. 因此我們需要換個觀點看問題.

工業(yè)界尤其關心全同態(tài)加密的效率, 例如通過1 次密文乘法的時間來比較. 但是這里存在一個誤區(qū),沒有把參數大小考慮進來. 例如, 80 位安全等級下與128 位安全等級下, 其參數大小是不同的. 參數大小不同直接導致計算的效率不同. 此外, 就算在同一安全等級下, 電路深度的不同也導致參數大小的不同. 例如, 在128 位安全等級下, 能夠計算10 次乘法的電路參數與能夠計算2 次乘法的電路參數大小完全不同,導致計算1 次乘法的時間完全不同. 所以通過1 次乘法或者幾次乘法的時間來比較是完全不科學的.

我們的主要貢獻是為全同態(tài)加密方案的測試提供一個公平科學的比較方法, 形成一個通用的測試系統(tǒng). 為了制定根據全同態(tài)加密具體安全參數的研究, 我們將安全等級與電路深度作為兩個關鍵基準點, 通過統(tǒng)一這兩個基準點的大前提下設置相應的測試方法. 測試方法主要分為3 類. 第1 類, 在相同的關鍵基準點的前提下, 對乘法計算效率進行比較: 第2 類, 密文計算與相應明文計算比較, 也稱為自己和自己比:第3 類, 通過在標準算法上執(zhí)行同態(tài)計算進行比較, 例如執(zhí)行機器學習里的邏輯回歸算法. 通過這3 類測試就能夠勾勒出各種全同態(tài)加密庫的性能. 此外, 為了提供全同態(tài)加密性能上的方便, 我們給出了性能研究性測試, 例如: 噪音增長測試、密文大小隨參數大小變化測試、密文打包性能測試等等. 為了直觀給出各種性能指標與分析, 我們提供了報表圖表的生成. 由于全同態(tài)加密目前都是基于C/C++ 語言的, 為了實現這個功能, 我們開發(fā)了Python 接口庫, 便于生成報表圖表的應用.

在本系統(tǒng)中, 我們預先在服務端和客戶端安裝好全同態(tài)加密庫, 用戶可以根據自己的需求, 在客戶端設置參數, 生成電路、密鑰、公鑰、密文后, 把電路、公鑰、密文發(fā)送給服務端做運算, 返回計算后的密文結果, 客戶端進行解密, 驗證結果并生成測試報告.

2 兩個主流全同態(tài)加密庫

目前, 兩個主流的全同態(tài)加密庫, 分別是HElib 庫[8,11]和Seal 庫[19], 本節(jié)先概述HElib 庫和Seal庫, 然后分析參數的設置和測試所需的電路設計.

2.1 HElib 庫

Helib 庫是基于Brakerski、Gentry 和Vaikuntanathan 提出的環(huán)LWE 上的全同態(tài)加密方案[3], 該方案一般稱為BGV 全同態(tài)加密方案. 在該方案中, 明文表示為Fp[x]/(f(x)) 環(huán)上多項式的系數. Gentry、Halevi 和Smart 對BGV 方案的實現進行了改進[7], HElib 庫是這個加密算法的一個實現. 系統(tǒng)中選擇p= 2 和f(x) 為n次分圓多項式Φn(x), 并且進一步優(yōu)化了密文打包技術[13]. 特別是, 如果多項式環(huán)Φn(x) 可以被模2 分解為l個不可約多項式, 應用中國剩余定理可以將l個多項式編碼為一個明文多項式. 因此明文空間可以看成是含有l(wèi)個明文槽的向量. 利用這種構造, 多項式環(huán)Fp[x]/(f(x)) 中的加法和乘法對應于槽向量中各個元素的加法和乘法, 從而能夠同時對l個數進行相同的操作, 該技術也稱為密文打包技術, 即Single Instruction, Multiple Data (SIMD).

根據分圓多項式在有限域上的性質, 假設有限域的元素個數是p, 其中p是素數而且p不是n的因子, 則分圓多項式Φn(x) 可以分解為φ(n)/m個次數為m的不可約多項式, 其中pm= 1(modn). 其中φ(·) 表示歐拉整數函數. 為了最大化l, 需要選擇使得m最小化的n, 但是n也受到安全參數λ和最大電路深度d的選擇的約束.

在HElib 庫中, 參數n設置在4500 和45 000 之間,λ= 80 位安全性,d ∈[4,24]. 這些具體參數所對應產生的明文槽約為l ∈[256,1285]. 方案產生的密文大小為O(φ(n)·d·log(λ)). 為了保證同態(tài)計算,密文大小增長較大, 使得同態(tài)計算成本較高. 為了提高計算效率降低計算成本, 將多個獨立的明文位打包成單個密文是提高效率的關鍵手段.

在HElib 中, 電路深度d具有特殊含義, 因為各種同態(tài)操作會導致密文噪音的增長. 例如, 兩個密文的加法會導致密文中的噪聲線性增長, 而密文的乘法會導致密文中的噪聲呈指數級增長. 所以MULT門電路比ADD 門電路更大地增加電路深度. 對各種門電路與電路深度的關系分析, 對于測試非常重要.表1 列出了HElib 支持的六種門類型對電路深度的貢獻.

表1 HELib 庫每個門類型的深度Table 1 Circuit depth of every gate in HELib

由上面的介紹可以看出, 我們對HElib 庫測試需要設置的參數有: 電路深度d, 明文槽l, 安全參數λ,以及電路寬度ω(即輸入線的數量).

2.2 Seal 庫

Microsoft Seal 全同態(tài)加密庫實現了兩種同態(tài)加密方案: BFV 方案和CKKS 方案[20].

在Seal 庫的BFV 方案中, 每個密文都有一個特定的量, 稱為“噪聲預算常量” (constant noise budget), 以比特為單位度量.

初始噪聲預算中的噪聲預算由參數決定. 在BFV 方案中, 對密文數據允許的兩種基本操作是加法和乘法, 其中加法幾乎可以認為不消耗噪聲預算. 一旦密文的噪聲預算達到零, 密文將無法解密. 所以, 對于具體執(zhí)行的計算, 應該提供相應的參數以支持足夠的噪音空間進行該計算. 否則會導致錯誤的結果. 此外,Seal 庫還提供了再線性化操作(relinearize) 來解決密文增長的問題.

BFV 方案主要設置的3 個參數如下:

(1) The degree of the polynomial modulus (poly-modulus-degree): 多項式模的次數是影響方案安全性的主要因素. 多項式模的次數越大, 方案的安全性越高. 但是次數越大, 密文的大小也越大,導致同態(tài)操作的計算效率降低. 在Seal 庫中, 推薦的次數是1024, 2048, 4096, 8192, 16384,32768. 而且多項式模數次數的大小等于明文槽數.

(2) The ciphertext coefficient modulus (coeff-modulus): 密文系數模, 越大意味著噪聲預算越多, 同時較大的系數模會降低方案的安全性. 因此, 復雜的計算需要較大的噪聲預算, 從而需要使用較大的系數模量. 但是必須同時增加多項式模的次數來抵消安全等級的降低.

(3) The plaintext modulus (plain-modulus): 明文模, 可以是任何正整數. 在很多情況下, 最好是素數. 明文模決定了明文數據的大小, 同時也影響了噪聲預算消耗. 因此, 為了獲得最佳性能,必須盡量保持明文盡可能小. 初始密文的噪聲預算公式是log2 (coeff-modulus/plain-modulus)(bits), 同態(tài)乘法的噪聲預算消耗形式為log2 (plain-modulo)+(other terms). 這些都是測試系統(tǒng)中需要重點考慮的因素.

CKKS 方案主要是用來處理浮點數. 它的參數需求與BFV 方案的主要區(qū)別是CKKS 方案不使用明文模. 但是需要使用一個額外的操作“rescale” 對浮點系數進行縮放. 而且多項式模數除以2 才等于明文槽數.

表2 列出了Seal 支持的九種門類型對電路深度的貢獻.

表2 Seal 庫每個門類型的深度Table 2 Circuit depth of every gate in Seal

2.3 電路設計

Seal 庫的電路設計和HElib 庫的很類似, 我們以HElib 庫舉例. 電路生成需要的參數包括電路深度d, 明文槽數l, 電路門類型的分布以及輸入線的數量ω.

HElib 庫測試都是在表1 所示的六種類型混合的門電路上運行的. 然而, 單一門組成的電路也是有用的, 以便能夠比較HElib 對這些門類型做運算的相對效率. 注意, 對于完全由一種門類型組成的電路, 需要對深度有不同的概念, 因為一些門類型對深度d沒有影響. 因此, 對于這種單門類型電路, 我們使用L來代替深度, 指的是從輸出門到任何輸入線的最長路徑的長度.

電路從輸入線開始生成, 并以輸出門結束. 總共創(chuàng)建了ω個輸入線, 對于電路的每一個后續(xù)級別, 都創(chuàng)建了ω個門, 其中的輸入是從其上兩個級別的門和線中隨機選擇的.

電路生成直到最后一級的所有門都具有大于d的深度才停止. 然后, 從一組具有正確深度d的門中隨機選擇一個門作為輸出門. 如果測試類型是單個門電路, 則電路生成直到生成L級別才停止, 并且從具有正確L級別的門中隨機選擇一個為輸出門. 一旦選擇了輸出門, 所有對輸出沒有貢獻的門和線都被丟棄了. 對于每個需要的明文常數輸入, 都會生成ω個長度為l的二進制字符串.

我們用于描述電路的語法, 詳情見圖1, 圖1 的第一行指定了輸入線的數量(ω), 電路的深度(d), 明文槽(l). 此后, 所有門按其級別(level) 排列. 同一級別的門以任意順序出現. 每個門由包含字符“G” 和一個惟一的編號標識. 并非所有門編號都在1 和最大門編號之間; 這是因為并非所有的門最終都會對輸出門產生影響. 輸入線由包含字符“W”, 后面跟著一個惟一的編號0,··· ,ω ?1 標識. 任何常數都是門的最后一個輸入.

圖1 生成電路的語法(左) 和同一電路的圖解說明(右)Figure 1 Grammar of generated circuit (left) and schematic description of same circuit (right)

3 系統(tǒng)設計及實現

3.1 系統(tǒng)架構與流程

本文設計的測試系統(tǒng)有三個目標. 第一, 在相同的關鍵基準點的前提下, 對乘法計算效率進行比較; 第二, 密文計算與相應明文計算比較, 也稱為自己和自己比; 第三, 通過在標準算法上執(zhí)行同態(tài)計算進行比較,例如執(zhí)行機器學習里的邏輯回歸算法. 通過這3 類測試就能夠勾勒出各種全同態(tài)加密庫的性能. 此外, 為了提供全同態(tài)加密性能上的方便, 我們給出了性能研究性測試, 例如: 噪音增長測試, 密文大小隨參數大小變化測試, 密文打包性能測試等等. 為了直觀給出各種性能指標與分析, 我們提供了報表圖表的生成. 由于全同態(tài)加密目前都是基于C/C++ 語言的, 為了實現這個功能, 我們開發(fā)了Python 接口庫, 便于生成報表圖表的應用. 系統(tǒng)架構如圖2, 系統(tǒng)流程如圖3 所示.

圖2 系統(tǒng)架構Figure 2 System architecture

圖3 系統(tǒng)流程Figure 3 System flow chart

3.2 測試部分實現

測試部分是我們用C++ 開發(fā)的程序的, 由客戶端和服務端交互完成. 客戶端和服務器用標準輸入和輸出流通過socket 通信. 在啟動時由用戶在客戶端設置相關參數. 在兩個進程都正確初始化后, 服務端會不斷發(fā)送接收參數的請求, 等客戶端發(fā)送參數之后, 連通成功, 它們互相通信, 重復執(zhí)行密鑰生成、加密、電路攝取、計算密文和解密.

客戶端從軟件界面讀取用戶設置的參數, 生成電路并且把參數值、電路發(fā)送到服務端. 客戶端在本地生成公鑰、密鑰. 在加密步驟中, 客戶端在本地加密, 并且發(fā)送公鑰與密文、明文給服務端, 并發(fā)送接收明文運算與密文運算結果的請求. 接下來, 在計算步驟中, 服務端使用密文作為輸入, 根據電路來做運算, 并將輸出結果的密文發(fā)送給客戶端. 同樣, 由于需要與明文計算做對比, 服務端也需要對明文進行運算, 并將輸出結果發(fā)送給客戶端. 最后, 在解密步驟中, 客戶端根據收到的最終密文結果進行解密, 并返回明文消息, 與在服務端對明文進行運算后的結果進行比較, 驗證其正確性.

客戶端和服務端之間的通信由我們開發(fā)的簡單通信協議決定的, 如圖4 所示. 在發(fā)送數據包之前, 會先計算數據包的大小, 方便之后判斷數據是否傳送完畢, 并且在發(fā)送請求時, 將數據包大小一起發(fā)送給對方. 安全參數、公鑰、明文消息和電路描述以ASCII 編碼, 用vector 的形式保存. 而密文以二進制編碼.

圖4 客戶端與服務端在測試全同態(tài)加密庫時的通信流程Figure 4 Test communication process of fully homomorphic encryption library

我們的測試系統(tǒng)捕獲了以下指標:

(1) 密文計算準確度: 服務端返回的解密結果是否等于對明文運算的結果.

(2) 公鑰、密鑰生成時間: 客戶端生成公鑰、密鑰所需的時間.

(3) 公鑰、密鑰大小: 客戶端生成的公鑰、密鑰大小.

(4) 加密時間: 客戶端加密明文消息所需的時間.

(5) 計算時間: 服務端按照電路進行明文、密文計算所需的時間.

(6) 解密時間: 客戶端解密密文所需的時間.

(7) 總耗用時間: 加密、計算和解密時間的總和.

3.3 密文與明文運算性能比較實現

為了顯示密文運算額外所消耗的時間, 我們提供了一個比較: 一個基于明文輸入的電路運算的客戶端——服務端實現. 客戶端傳密文的同時也傳送明文給服務端. 服務端對明文按照電路進行運算.

與測試部分一樣, 我們使用C++ 開發(fā)了比較組件在服務端中. 在明文運算步驟中, 這個組件使用map 函數和正則表達式來讀取文本電路進行明文運算. 并會對每一次運算進行計時, 用于與密文的運算進行比較.

3.4 報告生成器實現

在執(zhí)行測試之后, HEbenchmark 中的最后一步是在客戶端生成圖表報告, 以一種人性化的方式快速得出關于同態(tài)加密庫性能與正確性的結論.

報表生成器從一個SQLite 數據庫讀取, 該數據庫包含所有的時間和正確性數據, 以及測試的所有參數. 自動分析被測全同態(tài)加密庫運算的正確性, 對這些數據進行圖表, 曲線處理.

4 實驗結果

我們用一臺4 核Intel Core i5-7300U, 8 GB 內存的new surface pro 進行了測試, 所有程序都是在64 位ubuntu-18.04.2-desktop 上運行.

4.1 HElib 庫參數設置

在測試中, 我們選擇的安全參數是λ= 80, 所有時間都以毫秒為單位, 所有參數的大小以字節(jié)為單位.如表3 所示.

表3 根據明文槽l, 電路深度d 和最大輸入線ω 的參數Table 3 Parameters of plaintext slot, circuit depth and maximum input line in HELib

4.2 HElib 庫結果概述

我們測試了HElib 庫的參數、正確性以及性能. 我們的報告圖表生成器工具顯示HElib 庫在測試期間正確率100%: 對于所有1000 個測試, HElib 庫密文運算的輸出與明文運算的輸出相匹配. 另外, HElib的總計算時間與明文計算運算時間的平均比率約為114. 這個比值反映了同態(tài)計算所帶來的計算成本.

我們以100 個數據為一組, 取每組的平均值, 分別為10 組, 得出以下的散點圖5. 其中密文運算時間與明文運算時間比最小為30, 最大為1878.

圖5 HElib 庫密文計算時間與明文運算時間散點圖Figure 5 Comparison ciphertext operation time and plaintext operation time

4.3 HElib 庫密鑰和公鑰生成測試

我們發(fā)現在安全參數(λ= 80) 固定不變的情況下, 公鑰、密鑰大小與密文空間參數的設置高度相關.我們統(tǒng)計了λ=80 時, 不同密文空間的密鑰和公鑰大小. 表4 中的數據是私鑰和公鑰大小之和. 該值與計算電路的深度直接相關.

4.4 HElib 庫加密, 解密測試

加密、解密時間比較快, 我們的數據顯示加密平均需要280 毫秒(統(tǒng)計次數為1000 次). 有關詳細統(tǒng)計信息, 請參閱表5.

表4 HELib 庫的密鑰和公鑰大小(字節(jié))Table 4 Private key and public key size in HELib(bytes)

表5 HELib 加解密時間(毫秒)Table 5 Encryption time and Decryption time in HELib(ms)

4.5 HElib 庫按門類型做Evaluate 運算測試

最后, 我們通過測試系統(tǒng)運行了幾個所有門都是相同的類型的電路. 這些測試為我們提供了計算HElib 支持的各種類型的單個門所需時間的結果. 我們的結果如表6 所示.

表6 HELib 中每個門的運算時間(毫秒)Table 6 Evaluate time of each gate in HELib (ms)

4.6 Seal 庫參數設置

在測試中, 我們用參數多項式模的次數為1024, 2048, 4096, 8192 和密文系數模分別為8192, 16384和scale 取260和dbc 分別取15, 30, 45, 60 時來測試不同電路深度、輸入線時結果, 時間以毫秒為單位顯示, 所有參數大小都以字節(jié)為單位顯示. 如表7 所示.

表7 Seal 庫中不同明文槽l, 電路深度d 和最大輸入線ω 測試各類參數組合Table 7 Parameters of plaintext slot, circuit depth and maximum input line in Seal

4.7 Seal 庫測試結果概述

我們測試了Seal 庫的正確性和性能. 我們的報告生成器工具顯示Seal 庫在測試期間正確率100%:對于所有24 000 個測試, Seal 庫的輸出與我們基線的輸出相匹配. 另外, Seal 的密文運算時間與明文運算時間的平均比率約為92. 說明Seal 庫的速度略快于HElib 庫.

我們以100 個數據為一組, 取每組的平均值, 分別為240 組, 得出圖6 的散點圖. 其中密文運算時間與明文運算時間比最小為27, 最大為214.

4.8 Seal 庫密鑰與公鑰生成測試

我們發(fā)現密鑰和公鑰大小與明文模和密文模設置的參數高度相關. 而且參數一旦固定, 大小不會發(fā)生改變和偏差. 密鑰和公鑰的生成時間與明文模和密文模設置的參數也高度相關.

圖6 Seal 庫密文運算時間與明文運算時間散點圖Figure 6 Comparison ciphertext operation time and plaintext operation time in Seal

表8 和9 提供了生成的密鑰和公鑰大小與生成時間的描述性統(tǒng)計.

表8 Seal 庫密鑰和公鑰大小(字節(jié))Table 8 Private key and public key size in Seal (bytes)

表9 Seal 庫公鑰, 密鑰平均生成時間(毫秒)Table 9 Average time of generation of public key and private key in Seal (ms)

4.9 Seal 庫加密, 解密測試

我們取了兩個有代表性的參數(明文模為1024, 密文模為8192 與明文模為4096, 密文模為16 384)為例. 總加密時間非?？? 我們的數據顯示在明文模為1024, 密文模為8192 的情況下加密平均只需0.346毫秒. Seal 庫的解密時間也很快. 有關詳細統(tǒng)計信息, 請參閱表10.

表10 Seal 庫的加解密時間(毫秒)Table 10 Encryption time and decryption time in Seal (ms)

4.10 Seal 庫按門類型做Evaluate 運算測試

我們通過測試系統(tǒng)運行了幾個電路, 所有門都是相同的類型. 這些測試為我們提供了計算Seal 支持的各種類型的單個門所需時間的結果, 具體見表11. 其中參數選擇為多項式模的次數1024, 密文系數模8192.

5 結束語

為了回答全同態(tài)加密具體性能問題, 我們提出一個公平科學的比較方法, 將安全等級與電路深度作為兩個關鍵基準點, 通過統(tǒng)一這兩個基準點的大前提下設計了3 類測試方法. 此外, 為了提供全同態(tài)加密性能上的方便, 我們給出了性能研究性測試環(huán)節(jié). 為了直觀給出各種性能指標與分析, 我們開發(fā)了Python接口庫, 提供了報表圖表生成工具.

表11 Seal 庫中每個門的Evaluate 運算時間(毫秒)Table 11 Evaluate time of each gate in Seal (ms)

本系統(tǒng)(HEbenchmark) 能夠自動化的完成整個測試過程. 例如: 自動生成測試電路, 執(zhí)行測試, 密文計算與明文計算進行性能比較, 生成測試結果的統(tǒng)計分析與圖表. 本系統(tǒng)的實現由客戶端和服務端組成.客戶端用于電路, 密鑰, 公鑰的生成, 密文的解密. 客戶端具有友好的使用界面和報告生成界面. 客戶端與服務端之間采用socket 進行通信. 服務端用于電路讀取, 密文計算, 明文運算與密文計算比較等工作.

本系統(tǒng)具有靈活性, 能夠將已知的任何全同態(tài)加密庫加入測試, 直觀準確的給出全同態(tài)加密庫的各項性能指標, 便于非專業(yè)客戶使用. 為全同態(tài)加密的實踐應用, 提供了一個良好的評估測試工具.