密码学报 ISSN 2095-7025 CN 10-1195/TN Journal of Cryptologic Research, 2020, 7(6): 853-863 ©《密码学报》编辑部版权所有.E-mail: *************** http: / / www. Tel/Fax: +86-10-82789618HEBenchmark：全同态加密测试系统设计与实现** 基金项目：宁波市自然科学基金(2018A610159,202003N4320,202003N4321)；浙江省科技厅一般项目(LGG18F020001); 浙江省公益技术研究项目(LGF20F020004)；浙江省教育厅项目(Y202045245) Foundation: Natural Science Foundation of Ningbo City (2018A610159, 202003N4320, 202003N4321); General Pro gram of Science and Technology Bureau, Zhejiang Province (LGG18F020001); Technology Research for Public Welfare of Zhejiang Province (LGF20F020004); Program of Education Bureau, Zhejiang Province (Y202045245)
收稿日期：2019-11-20 定稿日期：2020-03-09
1. 浙江万里学院，宁波315100
2. 复旦大学计算机科学技术学院，上海201203 3. 中国科学院信息工程研究所信息安全国家重点实验室，北京100093
通信作者：陈智罡，E-mail: *********************
摘要：随着全同态加密飽需求和发展，学术界和工业界非常关注各种全同态如密库的计算效率.为了回 答全同态加密具体性能问题，我们提出一个公平科学的比较方法，将安全等级与电路深度作为两个关键基 准点，在统一这两个基准点的大前提下设置相应的测试方法.测试方法主要分为3类.第1类，在相同的 关键基准点的前提下，对乘法计算效率进行比较；第2类，密文计算与相应明文计算比较；第3类，通过在 标准算法上执行同态计算进行比较，例如执行机器学习里的逻辑回归算法.通过这3类测试就能够勾勒出 各种全同态加密库的性能.此外，我们还设计了研究性测试环节，例如：噪音增长测试，密文大小随参数大 小变化测试，密文打包性能测试等等.为了直观给出各种性能指标与分析，我们开发了 Python 接口库，提 供了报表图表生成工具.该系统(HEBenchmark)能够自动化的完成整个测试过程，并且具有灵活性，能 够将已知鈴任何全同态加密库加入测试，便于非专业客户使用.为全同态加密的实践应用，提供了一个良 好的评估测试工具. 关键词：全同态加密；测试系统；性能；密码学
中图分类号：TP309.7 文献标识码：A DOI: 10.13868/jki.jcr.0004U
FANPN中文引用格式：宋新霞，陈智罡，李離华.HEBenchmark：全同态加密测试系统设计与实现[J].密码学报，2020, 7(6): 853-863. [DOI: 10.13868/jki.jcr.0004U]
英文引用格式：SONG X X, CHEN Z G, LI Y H. HEBenchmark: Design and implementation of
fully homomorphic encryption test system[J]. Journal of Cryptologic Research, 2020, 7(6): 853-863. [DOI: 10.13868/jki.jcr.000411]
HEBenchmark: Design and Implementation of Fully Homomorphic Encryption Test System
SONG Xin-Xia 1'2, CHEN Zhi-Gang 1'3, LI Yan-Hua 1
1. Zhejiang Wanli University, Ningbo 315100, China
2. School of Computer Science, Fudan University, Shanghai 201203, China
3. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093,
China
854Journal of Cryptologic Research密码学报Vol.7,No.6,Dec.2020 Corresponding author:CHEN Zhi-Gang,E-mail:*********************
Abstrac t:With the demand and development of homomorphic encryption,academia and industry pay close attention to the efficiency of all kinds of homomorphic encryption libraries.In order to test the efficiency of homomorphic encryption libraries,a fair and scientific comparison method is proposed in this paper.The security level and circuit depth are taken as two key reference points,and corresponding test methods under these two reference points are studied.The test methods are mainly divided into three types.First,the efficiency of homomorphic multiplication is compared on the same key point.Second,homomorphic evaluation on the encrypted data is compared with the corresponding evaluation on the plaintext data.Last,homomorphic operations are performed on the standard algorithm,such as the logic regression algorithm in machine learning.Through these three types of tests,the performance of all kinds of homomorphic encryption libraries can be tested.In addition, this paper also proposes noise growth test,ciphertext size changes with parameter size test,cipher-text packaging performance test and other tests.In order to give a variety of performance indicators and analysis intuitively,the Python interface library is developed with a report chart generation tool. The test system(HEBenchmark)can automatically complete the whole test process,and can add any known homomorphic encryption library to the system,which is convenient for non-professional users. It provides a good evaluation and test tool for fully homomorphic encryptions.
Key words:fully homomorphic encryption;test system;performance;Cryp t o g raphy
1前言
全同态加密无需解密就能够对密文进行任意计算，因此可以立竿见影的解决数据隐私安全问题，有很大的应用需求.例如，在云环境下，用户加密数据后存储在云端，由于数据加密使得云端无法获得数据的内容，从而保证了数据的隐私.此外，由于是全同态加密，云端可以对密文数据进行任意计算.因此，全同态加密不但保护了数据，而且没有丧失计算性HF
在过去的十年里，学术界对全同态加密算法进行了大量的研究2412]—些全同态加密算法已经在软件中实现218】.然而，面对各种全同态加密算法，工业界缺乏一个标准的易于使用的测试工具，以便让用户测试与选择.不同全同态加密库的比较是困难的.一方面由于不同全同态加密算法所基于的噪音管理技术不同，甚至基于的数学结构也不同.例如HEAAN方案支持浮点数计算，在明文空间上就与BGV和BFV等方案有差异.而且在计算过程上也无法做到统一衡量.另一方面，不同电脑不同操作系统的平台也会导致无法站在同一基准上对各种全同态加密库进行客观统一的比较.
为此、我们前期对各种全同态加密算法进行了抽象层面的研究XI.该研究为我们探索统一的测试标准提供了理论支持.在全同态加密算法中，有两个技术非常重要.一是噪音管理技术，二是获得同态性技术(主要指的是获得乘法同态性).这些关键技术在各个全同态加密库中都是不同的.尽管这些关键技术在理论设计中非常重要，但是对于测试而言不是用户所关心的.因此我们需要换个观点看问题.
工业界尤其关心全同态加密的效率，例如通过1次密文乘法的时间来比较.但是这里存在一个误区，没有把参数大小考虑进来.例如，80位安全等级下与128位安全等级下，其参数大小是不同的.参数大小不同直接导致计算的效率不同.此外，就算在同一安全等级下，电路深度的不同也导致参数大小的不同•例如，在128位安全等级下，能够计算10次乘法的电路参数与能够计算2次乘法的电路参数大小完全不同，导致计算1次乘法的时间完全不同.所以通过1次乘法或者几次乘法的时间来比较是完全不科学的.
我们的主要贡献是为全同态加密方案的测试提供一个公平科学的比较方法，形成一个通用的测试系统.为了制定根据全同态加密具体安全参数的研究，我们将安全等级与电路深度作为两个关键基准点，通过统一这两个基准点的大前提下设置相应的测试方法.测试方法主要分为3类•第1类，在相同的关键基准点的前提下，对乘法计算效率进行比较：第2类，密文计算与相应明文计算比较，也称为自己和自己比：第3类，通过在标准算法上执行同态计算进行比较，例如执行机器学习里的逻辑回归算法.通过这3类测
宋新霞等：HEBenchmark：全同态加密测试系统设计与实现855
试就能够勾勒出各种全同态加密库的性能.此外，为了提供全同态加密性能上的方便，我们给岀了性能研究性测试，例如：噪音增长测试、密文大小随参数大小变化测试、密文打包性能测试等等.为了直观给出各种性能指标与分析，我们提供了报表图表的生成.由于全同态加密目前都是基于C/C++语言的，为了实现这个功能，我们开发了Python接口库，便于生成报表图表的应用.
在本系统中，我们预先在服务端和客户端安装好全同态加密库，用户可以根据自己的需求，在客户端设置参数，生成电路、密钥、公钥、密文后，把电路、公钥、密文发送给服务端做运算，返回计算后的密文结果，客户端进行解密，验证结果并生成测试报告.
2两个主流全同态加密库
目前，两个主流的全同态加密库，分别是HElib库[8'ul和Seal库1191，本节先概述HElib库和Seal 库，然后分析参数的设置和测试所需的电路设计.
2.1HElib库
Helib库是基于Brakerski,Gentry和Vaikuntanathan提出的环LWE上的全同态加密方案冏，该方案一般称为BGV全同态加密方案.在该方案中，明文表示为环上多项式的系数.Gentry. Halevi和Smart对BGV方案的实现进行了改进⑺，HElib库是这个加密算法的一个实现.系统中选择p=2和/(x)为n次分圆多项式◎”(©，并且进一步优化了密文打包技术特别是，如果多项式环可以被模2分解为I个不可约多项式，应用中国剩余定理可以将I个多项式编码为一个明文多项式.因此明文空间可以看成是含有I个明文槽的向量.利用这种构造，多项式环F p[t]/(/(x))中的加法和乘法对应于槽向量中各个元素的加法和乘法，从而能够同时对I个数进行相同的操作，该技术也称为密文打包技术，即Single Instruction,Multiple Data(SIMD).
根据分圆多项式在有限域上的性质，假设有限域的元素个数是p，其中p是素数而且p不是n的因子，则分圆多项式$n(K)可以分解为个次数为m的不可约多项式，其中p m=l(mod n).其中0(・)表示欧拉整数函数.为了最大化I，需要选择使得m最小化的n，但是n也受到安全参数A和最大电路深度d的选择的约束.
在HElib库中，参数n设置在4500和45000之间,A=80位安全性，d6[4,24].这些具体参数所对应产生的明文槽约为I€[256,1285].方案产生的密文大小为O®(n)•d•log。)).为了保证同态计算，密文大小增长较大，使得同态计算成本较高.为了提高计算效率降低计算成本，将多个独立的明文位打包成单个密文是提高效率的关键手段.
争吵教学设计在HElib中，电路深度d具有特殊含义，因为各种同态操作会导致密文噪音的增长.例如，两个密文的加法会导致密文中的噪声线性增长，而密文的乘法会导致密文中的噪声呈指数级增长.所以MULT 门电路比ADD门电路更大地增加电路深度.对各种门电路与电路深度的关系分析，对于测试非常重要.表1列出了HElib支持的六种门类型对电路深度的贡献.
表1HELib库每个门类型的深度
Table1Circuit depth of every gate in HELib
门深度(d)门深度(d)
爱上验尸官
MULT1ADDconst0
MULTconst0.5SELECT0.6 ADD0.1ROTATE0.25到0.75之间由上面的介绍可以看出，我们对HElib库测试需要设置的参数有：电路深度d，明文槽/，安全参数A，以及电路宽度3(即输入线的数量)•
2.2Seal库
Microsoft Seal全同态加密库实现了两种同态加密方案：BFV方案和CKKS方案[201.
在Seal库的BFV方案中，每个密文都有一个特定的量，称为“噪声预算常量”(constant noise budget)，以比特为单位度量.
856Journal of Cryptologic Research密码学报Vol.7,No.6,Dec.2020
初始噪声预算中的噪声预算由参数决定.在BFV方案中，对密文数据允许的两种基本操作是加法和乘法，其中加法几乎可以认为不消耗噪声预算.一旦密文的噪声预算达到零，密文将无法解密.所以，对于具体执行的计算，应该提供相应的参数以支持足够的噪音空间进行该计算.否则会导致错误的结果.此外, Seal库还提供了再线性化操作(relinearize)来解决密文增长的问题.
BFV方案主要设置的3个参数如下：
(1)The degree of the polynomial modulus(poly-modulus-degree)：多项式模的次数是影响方案安
全性的主要因素.多项式模的次数越大，方案'的安全性越高.但是次数越大，密文的大小也越大，导致同态操作的计算效率降低.在Seal库中，推荐的次数是1024,204&4096,8192,16384, 3276&而且多项式模数次数的大小等于明文槽数.奥斯维辛
(2)The ciphertext coefficient modulus(coeff-modulus)：密文系数模，越大意味着噪声预算越多，同
时较大的系数模会降低方案的安全性.因此，复杂的计算需要较大的噪声预算，从而需要使用较大的系数模量•但是必须同时增加多项式模的次数来抵消安全等级的降低.
(3)The plaintext modulus(plain-modulus)：明文模，可以是任何正整数.在很多情况下，最好是
素数.明文模决定了明文数据的大小，同时也影响了噪声预算消耗.因此，为了获得最佳性能，必须尽量保持明文尽可能小.初始密文的噪声预算公式是log2(coeff-modulus/plain-modulus) (bits)，同态乘法的噪声预算消耗形式为log2(plain-modulo)+(other terms).这些都是测试系统中需要重点考虑的因素.
CKKS方案主要是用来处理浮点数.它的参数需求与BFV方案的主要区别是CKKS方案不使用明文模.但是需要使用一个额外的操作“rescale”对浮点系数进行缩放.而且多项式模数除以2才等于明文槽数.
乙醇钠
表2列出了Seal支持的九种门类型对电路深度的贡献.
表2Seal库每个门类型的深度
Table2Circuit depth of every gate in Seal
门深度(d)门深度(d)
MULT1SUBconst0 MULTconst0.5SQUARE1 ADD0.1NEGATE0 ADDconst0ROTATE0.25到0.75之间SUB0.1
2.3电路设计
Seal库的电路设计和HElib库的很类似，我们以HElib库举例.电路生成需要的参数包括电路深度d，明文槽数/，电路门类型的分布以及输入线的数量3.
HElib库测试都是在表1所示的六种类型混合的门电路上运行的.然而，单一门组成的电路也是有用的、以便能够比较HElib对这些门类型做运算的相对效率.注意，对于完全由一种门类型组成的电路，需要对深度有不同的概念，因为一些门类型对深度d没有影响.因此，对于这种单门类型电路，我们使用L 来代替深度，指的是从输出门到任何输入线的最长路径的长度.
电路从输入线开始生成，并以输出门结束.总共创建了3个输入线，对于电路的每一个后续级别，都创建了3个门，其中的输入是从其上两个级别的门和线中随机选择的.
电路生成直到最后一级的所有门都具有大于d的深度才停止.然后，从一组具有正确深度d的门中随机选择一个门作为输出门.如果测试类型是单个门电路，则电路生成直到生成厶级别才停止，并且从具有正确L级别的门中随机选择一个为输出门.一旦选择了输出门，所有对输出没有贡献的门和线都被丢弃T.对于每个需要的明文常数输入，都会生成3个长度为I的二进制字符串.
陕西金号网我们用于描述电路的语法，详情见图1、图1的第一行指定了输入线的数量(3)，电路的深度(d)，明文槽(Z).此后，所有门按其级别(level)排列.同一级别的门以任意顺序岀现.每个门由包含字符“G”和一 个惟一的编号标识.并非所有门编号都在1和最大门编号之间；这是因为并非所有的门最终都会对输出门
宋新霞 等：HEBenchmark：全同态加密测试系统设计与实现857产生影响.输入线由包含字符“W ”，后面跟着一个惟一的编号0,--. ,u;-l 标识.任何常数都是门的最后 一个输入.
W=4, D=3.1, L=5
G5: LSELECT(WOAV1 ,[00001])
G7: LMULconst(W2,[01011])Gil: LMUL(G5,W3)
GIO: LADDconst(G7,[11110])G14: LROTATE(G10,34)
G17: LMUL(G14,G11)
G23: LNIULconst (G 17, [11100])G5： LSELECT Gil: LMUL G17: LMUL
G23: LMULx oust
G7: LMUSust
GIO: LADDcmist.
G14： LROTATE
图1生成电路的语法(左)和同一电路的图解说明(右)
Figure 1 Grammar of generated circuit (left) and schematic description of same circuit (right)3系统设计及实现
3.1系统架构与流程
本文设计的测试系统有三个目标.第一，在相同的关键基准点的前提下，对乘法计算效率进行比较；第 二，密文计算与相应明文计算比较，也称为自己和自己比；第三，通过在标准算法上执行同态计算进行比较, 例如执行机器学习里的逻辑回归算法.通过这3类测试就能够勾勒出各种全同态加密库的性能.此外，为 了提供全同态加密性能上的方便，我们给出了性能研究性测试，例如：噪音增长测试，密文大小随参数大小 变化测试，密文打包性能测试等等.为了直观给出各种性能指标与分析，我们提供了报表图表的生成.由于 全同态加密目前都是基于C/C++语言的，为了实现这个功能，我们开发了 Python 接口库，便于生成报 表图表的应用.系统架构如图2，系统流程如图3所示.
C++
Python
用户界面眼务进程
幣痊匸I I 明文运算I 1时间统计］
［大小统计）
本地数据解密结頁：丽兀叵廷亟初'：亟回研瓦 込“次数 公钥「密钳人小 噪音预“ …… J
图2系统架构Figure 2 System architecture
图3系统流程
Figure 3 System flow chart 3.2测试部分实现
测试部分是我们用C++开发的程序的，由客户端和服务端交互完成.客户端和服务器用标准输入和 输出流通过socket 通信.在启动时由用户在客户端设置相关参数.在两个进程都正确初始化后，服务端会 不断发送接收参数的请求，等客户端发送参数之后，连通成功，它们互相通信，重复执行密钥生成、加密、 电路摄取、计算密文和解密
.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议