HEBenchmark: 全同態(tài)加密測(cè)試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)*

宋新霞, 陳智罡, 李焱華

1. 浙江萬(wàn)里學(xué)院, 寧波315100

2. 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 上海201203

3. 中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100093

1 前言

全同態(tài)加密無(wú)需解密就能夠?qū)γ芪倪M(jìn)行任意計(jì)算, 因此可以立竿見(jiàn)影的解決數(shù)據(jù)隱私安全問(wèn)題, 有很大的應(yīng)用需求. 例如, 在云環(huán)境下, 用戶加密數(shù)據(jù)后存儲(chǔ)在云端, 由于數(shù)據(jù)加密使得云端無(wú)法獲得數(shù)據(jù)的內(nèi)容, 從而保證了數(shù)據(jù)的隱私. 此外, 由于是全同態(tài)加密, 云端可以對(duì)密文數(shù)據(jù)進(jìn)行任意計(jì)算. 因此, 全同態(tài)加密不但保護(hù)了數(shù)據(jù), 而且沒(méi)有喪失計(jì)算性[1-3].

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

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

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

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

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

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

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

2.1 HElib 庫(kù)

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

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

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

在HElib 中, 電路深度d具有特殊含義, 因?yàn)楦鞣N同態(tài)操作會(huì)導(dǎo)致密文噪音的增長(zhǎng). 例如, 兩個(gè)密文的加法會(huì)導(dǎo)致密文中的噪聲線性增長(zhǎng), 而密文的乘法會(huì)導(dǎo)致密文中的噪聲呈指數(shù)級(jí)增長(zhǎng). 所以MULT門電路比ADD 門電路更大地增加電路深度. 對(duì)各種門電路與電路深度的關(guān)系分析, 對(duì)于測(cè)試非常重要.表1 列出了HElib 支持的六種門類型對(duì)電路深度的貢獻(xiàn).

表1 HELib 庫(kù)每個(gè)門類型的深度Table 1 Circuit depth of every gate in HELib

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

2.2 Seal 庫(kù)

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

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

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

BFV 方案主要設(shè)置的3 個(gè)參數(shù)如下:

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

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

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

CKKS 方案主要是用來(lái)處理浮點(diǎn)數(shù). 它的參數(shù)需求與BFV 方案的主要區(qū)別是CKKS 方案不使用明文模. 但是需要使用一個(gè)額外的操作“rescale” 對(duì)浮點(diǎn)系數(shù)進(jìn)行縮放. 而且多項(xiàng)式模數(shù)除以2 才等于明文槽數(shù).

表2 列出了Seal 支持的九種門類型對(duì)電路深度的貢獻(xiàn).

表2 Seal 庫(kù)每個(gè)門類型的深度Table 2 Circuit depth of every gate in Seal

2.3 電路設(shè)計(jì)

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

HElib 庫(kù)測(cè)試都是在表1 所示的六種類型混合的門電路上運(yùn)行的. 然而, 單一門組成的電路也是有用的, 以便能夠比較HElib 對(duì)這些門類型做運(yùn)算的相對(duì)效率. 注意, 對(duì)于完全由一種門類型組成的電路, 需要對(duì)深度有不同的概念, 因?yàn)橐恍╅T類型對(duì)深度d沒(méi)有影響. 因此, 對(duì)于這種單門類型電路, 我們使用L來(lái)代替深度, 指的是從輸出門到任何輸入線的最長(zhǎng)路徑的長(zhǎng)度.

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

電路生成直到最后一級(jí)的所有門都具有大于d的深度才停止. 然后, 從一組具有正確深度d的門中隨機(jī)選擇一個(gè)門作為輸出門. 如果測(cè)試類型是單個(gè)門電路, 則電路生成直到生成L級(jí)別才停止, 并且從具有正確L級(jí)別的門中隨機(jī)選擇一個(gè)為輸出門. 一旦選擇了輸出門, 所有對(duì)輸出沒(méi)有貢獻(xiàn)的門和線都被丟棄了. 對(duì)于每個(gè)需要的明文常數(shù)輸入, 都會(huì)生成ω個(gè)長(zhǎng)度為l的二進(jìn)制字符串.

我們用于描述電路的語(yǔ)法, 詳情見(jiàn)圖1, 圖1 的第一行指定了輸入線的數(shù)量(ω), 電路的深度(d), 明文槽(l). 此后, 所有門按其級(jí)別(level) 排列. 同一級(jí)別的門以任意順序出現(xiàn). 每個(gè)門由包含字符“G” 和一個(gè)惟一的編號(hào)標(biāo)識(shí). 并非所有門編號(hào)都在1 和最大門編號(hào)之間; 這是因?yàn)椴⒎撬械拈T最終都會(huì)對(duì)輸出門產(chǎn)生影響. 輸入線由包含字符“W”, 后面跟著一個(gè)惟一的編號(hào)0,··· ,ω ?1 標(biāo)識(shí). 任何常數(shù)都是門的最后一個(gè)輸入.

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

3 系統(tǒng)設(shè)計(jì)及實(shí)現(xiàn)

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

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

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

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

3.2 測(cè)試部分實(shí)現(xiàn)

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

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

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

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

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

(1) 密文計(jì)算準(zhǔn)確度: 服務(wù)端返回的解密結(jié)果是否等于對(duì)明文運(yùn)算的結(jié)果.

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

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

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

(5) 計(jì)算時(shí)間: 服務(wù)端按照電路進(jìn)行明文、密文計(jì)算所需的時(shí)間.

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

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

3.3 密文與明文運(yùn)算性能比較實(shí)現(xiàn)

為了顯示密文運(yùn)算額外所消耗的時(shí)間, 我們提供了一個(gè)比較: 一個(gè)基于明文輸入的電路運(yùn)算的客戶端——服務(wù)端實(shí)現(xiàn). 客戶端傳密文的同時(shí)也傳送明文給服務(wù)端. 服務(wù)端對(duì)明文按照電路進(jìn)行運(yùn)算.

與測(cè)試部分一樣, 我們使用C++ 開(kāi)發(fā)了比較組件在服務(wù)端中. 在明文運(yùn)算步驟中, 這個(gè)組件使用map 函數(shù)和正則表達(dá)式來(lái)讀取文本電路進(jìn)行明文運(yùn)算. 并會(huì)對(duì)每一次運(yùn)算進(jìn)行計(jì)時(shí), 用于與密文的運(yùn)算進(jìn)行比較.

3.4 報(bào)告生成器實(shí)現(xiàn)

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

報(bào)表生成器從一個(gè)SQLite 數(shù)據(jù)庫(kù)讀取, 該數(shù)據(jù)庫(kù)包含所有的時(shí)間和正確性數(shù)據(jù), 以及測(cè)試的所有參數(shù). 自動(dòng)分析被測(cè)全同態(tài)加密庫(kù)運(yùn)算的正確性, 對(duì)這些數(shù)據(jù)進(jìn)行圖表, 曲線處理.

4 實(shí)驗(yàn)結(jié)果

我們用一臺(tái)4 核Intel Core i5-7300U, 8 GB 內(nèi)存的new surface pro 進(jìn)行了測(cè)試, 所有程序都是在64 位ubuntu-18.04.2-desktop 上運(yùn)行.

4.1 HElib 庫(kù)參數(shù)設(shè)置

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

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

4.2 HElib 庫(kù)結(jié)果概述

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

我們以100 個(gè)數(shù)據(jù)為一組, 取每組的平均值, 分別為10 組, 得出以下的散點(diǎn)圖5. 其中密文運(yùn)算時(shí)間與明文運(yùn)算時(shí)間比最小為30, 最大為1878.

圖5 HElib 庫(kù)密文計(jì)算時(shí)間與明文運(yùn)算時(shí)間散點(diǎn)圖Figure 5 Comparison ciphertext operation time and plaintext operation time

4.3 HElib 庫(kù)密鑰和公鑰生成測(cè)試

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

4.4 HElib 庫(kù)加密, 解密測(cè)試

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

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

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

4.5 HElib 庫(kù)按門類型做Evaluate 運(yùn)算測(cè)試

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

表6 HELib 中每個(gè)門的運(yùn)算時(shí)間(毫秒)Table 6 Evaluate time of each gate in HELib (ms)

4.6 Seal 庫(kù)參數(shù)設(shè)置

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

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

4.7 Seal 庫(kù)測(cè)試結(jié)果概述

我們測(cè)試了Seal 庫(kù)的正確性和性能. 我們的報(bào)告生成器工具顯示Seal 庫(kù)在測(cè)試期間正確率100%:對(duì)于所有24 000 個(gè)測(cè)試, Seal 庫(kù)的輸出與我們基線的輸出相匹配. 另外, Seal 的密文運(yùn)算時(shí)間與明文運(yùn)算時(shí)間的平均比率約為92. 說(shuō)明Seal 庫(kù)的速度略快于HElib 庫(kù).

我們以100 個(gè)數(shù)據(jù)為一組, 取每組的平均值, 分別為240 組, 得出圖6 的散點(diǎn)圖. 其中密文運(yùn)算時(shí)間與明文運(yùn)算時(shí)間比最小為27, 最大為214.

4.8 Seal 庫(kù)密鑰與公鑰生成測(cè)試

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

圖6 Seal 庫(kù)密文運(yùn)算時(shí)間與明文運(yùn)算時(shí)間散點(diǎn)圖Figure 6 Comparison ciphertext operation time and plaintext operation time in Seal

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

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

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

4.9 Seal 庫(kù)加密, 解密測(cè)試

我們?nèi)×藘蓚€(gè)有代表性的參數(shù)(明文模為1024, 密文模為8192 與明文模為4096, 密文模為16 384)為例. 總加密時(shí)間非?？? 我們的數(shù)據(jù)顯示在明文模為1024, 密文模為8192 的情況下加密平均只需0.346毫秒. Seal 庫(kù)的解密時(shí)間也很快. 有關(guān)詳細(xì)統(tǒng)計(jì)信息, 請(qǐng)參閱表10.

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

4.10 Seal 庫(kù)按門類型做Evaluate 運(yùn)算測(cè)試

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

5 結(jié)束語(yǔ)

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

表11 Seal 庫(kù)中每個(gè)門的Evaluate 運(yùn)算時(shí)間(毫秒)Table 11 Evaluate time of each gate in Seal (ms)

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

本系統(tǒng)具有靈活性, 能夠?qū)⒁阎娜魏稳瑧B(tài)加密庫(kù)加入測(cè)試, 直觀準(zhǔn)確的給出全同態(tài)加密庫(kù)的各項(xiàng)性能指標(biāo), 便于非專業(yè)客戶使用. 為全同態(tài)加密的實(shí)踐應(yīng)用, 提供了一個(gè)良好的評(píng)估測(cè)試工具.