一种实现数据库同态计算的ELGamal重加密算法

2021-06-03张闻宇

北京交通大学学报 2021年2期

黎琳，张芳，张闻宇

(1.北京交通大学计算机与信息技术学院，北京100044;2. 山东财经大学 a.计算机科学与技术学院,b. 山东省区块链金融重点实验室，济南 250014)

随着数据泄露问题频发，造成的经济损失和社会影响持续加剧.人们基于数据库系统设计出一系列保护数据机密性的安全策略[1].当前防火墙、访问控制和入侵检测等方案的安全性均基于攻击者未攻入服务器.但是事实证明数据泄露问题主要由攻击者绕开或攻破以上防御方案直接攻入服务器[2]或者恶意服务器管理员[3]引发.为从根本上保护数据安全，主流数据库产品开始研究加密数据库技术.

相比于无法基于密文进行计算的传统密码体制[4]，全同态加密的同态性质可以解决数据隐私和密文计算问题.自2009年Gentry首次提出基于格困难问题的全同态加密构造方案[5]，发展到无需密钥参与即可进行同态计算的第三代技术方案[6]，同态计算的效率不断提高[5-8]，但是依然存在密钥生成困难，同态计算耗时过长等问题，无法真正实际应用[9].为此研究人员提出使用部分同态加密算法解决实际应用中密文计算的方案[10].2011年麻省理工计算机科学与人工智能实验室(Computer Science and Artificial Intelligence Laboratory, CSAIL)首次提出具有加法同态性质的CryptDB[11]系统，该系统采用Paillier[12-13]加法同态算法和洋葱加密策略，支持在密文数据库中进行SQL加法查询，目前已被Google和林肯实验室(Lincoln Labs)采用.然而由于CryptDB只应用了加法同态密码体制，无法对密文进行乘法以及混合运算，对密文计算应用意义较小.

本文作者基于数据库管理系统(DataBase Management System, DBMS)外层加密技术和ELGamal乘法同态密码体制提出一种实现数据库同态性质的ELGamal重加密算法，在ELGamal密码体制乘法同态性质的基础上新增实现了加法同态性质，并实现了密文加法和乘法混合运算.区别于代理端为实现数据共享采用的重加密技术[14]，本文中的重加密是一种为实现同态性质对SQL查询表达式进行重加密计算的技术.

1 ELGamal密码体制及其同态性质

ELGamal密码体制是1985年Taher Elgamal利用单向陷门函数构造的公钥密码体制.本节通过模拟Alice和Bob利用ELGamal密码体制通信的过程，详细描述ELGamal密码体制[15-16].通信过程中Alice作为消息接收方，Bob作为消息发送方.

1.1 ELGamal密码体制

ELGamal密码体制由密钥生成、加密消息、解密消息三部分组成.

1)Alice生成密钥.

①随机生成大素数p，且要求p至少有一个大素数因子.

②生成模p的乘法群G，选取乘法群G的一个生成元g.

③随机选择x∈Zp-1作为私钥.

④计算公钥y=gxmodp.

⑤公开公钥：p、g、y，保存私钥x.

2)Bob对消息进行加密.

①选取随机数d满足1

②生成明文消息m的密文对c1=gd，c2=mgdxmodp.

③将密文对发送给Alice.

3)Alice解密得到消息.

Alice解密密文对,得到明文m=c2/c1xmodp.

1.2 基于DDH困难问题的IND-CPA

ELGamal密码体制基于DDH[17-18]困难问题具有选择明文攻击下的不可区分性(INDistinguishability under Chosen-Plaintext Attack, IND-CPA). DDH困难问题为已知大素数p，生成元g，ga和gb情况下以不可忽略概率区分gn的准确值是困难的，其中n∈{0,1}，g1=gab，g2=gc.

假设Alice和Bob使用ELGamal密码体制对通信消息进行加密.通信过程中攻击者可以从信道中截获到所有公钥信息：大素数p、乘法群G的生成元g、公钥y以及密文对c1，c2.目前不存在以不可忽略概率解决DDH困难问题的神谕机，所以攻击者根据截获信息无法以不可忽略概率计算出解密必需参数gxd,进而解密密文c2得到明文消息.

1.3 ELGamal密码体制的同态性质

1)ELGamal密码体制具有乘法同态性质.

明文m1、m2分别由密钥g，x和随机数d1，d2加密得到密文对(c11，c12)和(c21，c22)，密文对相乘可得(c11*c21，c12*c22)即(gd1*gd2，m1gd1m2gd2modp).显而易见，该密文对为密钥y，x和随机数(d1+d2)对明文m1*m2加密密文.计算解密公式c12*c22/(c11*c21)xmodp即可正确解密得到明文乘积m1*m2.所以ELGamal密码体制具有乘法同态性质.

2)ELGamal密码体制具有混合乘法同态性质.

3)ELGamal密码体制不具有加法同态性质.

明文m1、m2由密钥g，x和随机数d1，d2加密分别得到密文组(c11，c12)和(c21，c22)，密文进行任何计算都无法得到明文相加即m1+m2加密的密文.故ELGamal密码体制不具有加法同态性质.

2 ELGamal重加密算法

2.1 应用场景

当前加密数据库通常采用数据库安全中间件对数据进行加密，主要分为：DBMS外层(客户端)加密、DBMS内层(服务器)加密和基于文件级的加解密技术3种方式.相比DBMS内层加密和基于文件级加解密技术，DBMS外层加密方式将数据加解密功能放在可信第三方，无需对客户端和服务器进行改动即可实现数据库密文存储保障数据安全，在实际生活中被广泛应用.

本加密数据库选择DBMS外层加密方式实现数据库加解密功能.数据库系统由客户端、加密代理端和DBMS服务器三部分构成，见图1.

图1 DBMS外层加密数据库系统Fig.1 DBMS outer encrypted database system

代理端由密钥管理模块、通信模块和加解密模块构成.密钥管理模块负责为用户生成密钥并对密钥进行存储和调用；通信模块对客户端和DBMS服务器之间的会话分析重写，通过调用密钥管理模块和加解密模块存储实现密文存储和查询功能；加解密模块实现数据加解密功能.

DBMS外层加密数据库客户端和数据库服务器会话过程如下：

1)用户在客户端发出会话请求连接，代理端调用密钥管理模块进行密钥管理，同时完成客户端与DBMS服务器的连接.

2)用户通过客户端请求向数据库插入数据，代理端调用用户密钥和加密算法对数据进行加密，将密文存入数据库.

3)用户在客户端发出SQL查询请求，代理端根据查询语句类型和加密算法对SQL查询请求加密重写，向DBMS服务器密文数据进行查询，DBMS服务器正常完成数据库查询生成应答响应提交代理端，代理端对DBMS服务器应答重写解密返回客户端完成整个会话过程.

2.2 ELGamal重加密算法

2.2.1 ELGamal重加密算法定义

ELGamal重加密算法由5个算法构成：密钥生成算法KenGen、随机数d生成算法DGen、加密算法Encry、解密算法Decry和重加密表达式生成算法Recry，具体算法定义如下：

1)密钥生成算法KenGen(k).

K1：输入安全参数λ，λ为公钥p二进制位数；

K2：生成λ位大素数p；

K3：生成模p乘法群G的随机生成元g；

K4：随机选取x∈Zp-1;

K5: 输出公钥pks：p，g，gxmodp，私钥

sks=x.

2)随机数d生成算法DGen(pks).

D1：输入公钥p；

D2：选取随机数d∈Zp-1；

D3：输出随机数d；

3)加密算法Encry(pks,d,m).

E1：输入公钥pks、随机数d和明文m；

E2：计算密文c=mgxdmodp；

E3：输出密文c；

4)解密算法Decry(pks,d,c).

D1：输入私钥sks、随机数d和密文c；

D2：计算明文m=c(gxd)-1modp;

D3：输出明文m；

5)重加密表达式生成算法Recry(pks,d,expression).

R1：输入公钥pks、随机数d和查询语句中逻辑表达式expression；

R2：根据重加密策略生成重加密表达式；

R3：输出重加密表达式recryptExpression.

2.2.2 重加密策略

ELGamal重加密算法根据表达式运算符类型为SQL查询表达式制定重加密策略.‘+’和‘*’运算符可以组成三种不同类型SQL查询语句表达式：乘法计算表达式、加法计算表达式和混合计算表达式，ELGamal重加密算法针对以上每种情况制定相应重加密策略以实现密文同态计算.

1)乘法重加密策略.

SQL查询语句只存在乘法算术运算即表达式形式如c1c2…cn，通过乘法重加密策略生成表达式c1c2…cnY(Y=(gxd1gxd2…gxdn)-1gxdmodp).数据库服务器对重加密表达式计算结果对应表达式m1m2…mngxd(modp)计算结果，即私钥x和随机数d对m1m2…mn加密密文.

2)加法重加密策略.

SQL查询语句只存在加法算术运算即表达式形如c1+c2+…+cn，重加密策略对每个加法项进行重加密生成重加密表达式c1Y1+c2Y2+…+cnYn(Yi=(gxdi)-1gxdmodp)，重加密表达式可看作(m1+m2+…+mn)gxd(modp)，即私钥x和随机数d对m1+m2+…+mn加密密文.

3)混合运算重加密策略.

SQL查询语句表达式为混合运算即加法和乘法运算同时存在时，重加密策略规定如果表达式是包含括号的复杂表达式则将表达式修改为不存在括号的简单表达式如c1c2+c3，并按照乘法重加密策略和加法重加密策略生成重加密表达式.此例中先对乘法项进行重加密c1c2Y，再对加法项进行重加密c3Y3，生成的重加密表达式为c1c2Y+c3Y3，即(m1m2+m3)gxd(modp).同时规定混合运算重加密策略对所有计算项仅进行一次重加密.

2.2.3 重加密策略正确性与同态性

ELGamal重加密算法满足乘法同态和加法同态.下面进行证明.

1)乘法重加密策略的正确性和同态性.

c1c2…cnY=

(m1gxd1m2gxd2…mngxdn)*

(gxd1gxd2…gxdn)-1gxdmodp=

m1m2…mngxd(modp)

(1)

由式(1)可知乘法表达式重加密计算结果为对应明文乘积加密密文，密文为相同密钥和新随机数d对明文乘积加密得到.显而易见，重加密密文依然是一个ELGamal密码体制中的密文，实现了乘法同态计算.

2)加法重加密策略的正确性和同态性.

c1Y1+c2Y2+…+cnYn=

(c1(gxd1)-1gxd+c2(gxd2)-1gxd+…+

cn(gxdn)-1gxd)modp=

(m1+m2+…+mn)gxd(modp)

(2)

式(2)表示加法表达式c1+c2+…cn重加密计算，密文同样是ELGamal密码体制中密文，同时实现了加法同态计算.

3)混合运算重加密策略的正确性和同态性.

查询语句中的混合计算重加密时需要遵循乘法项和加法项的重加密规则.重加密表达式具有同态性质，可以进行混合计算.公式表示如下

c1c2Y+c3Y3=(m1gxd1m2gxd2)*

(gxd1gxd2)-1gxd(modp)+

m3gxd3(gxd3)-1gxd(modp)=

m1m2gxd(modp)+m3gxd(modp)=

(m1m2+m3)gxd(modp)

(3)

2.3 数据库同态计算实现方案

加密数据库在加解密模块使用ELGamal重加密算法实现SQL表达式同态计算，图2表示加密数据库同态计算实现过程.

图2 加密数据库同态计算实现过程Fig.2 Implementation process of encrypted database homomorphic calculation

1)客户端请求连接，代理端调用密钥管理模块，建立客户端和数据库服务器连接.

①客户端首次请求连接，代理端调用密钥管理模块KenGen(k)算法为客户端生成并保存密钥.

②客户端非首次连接或代理端完成密钥管理，通信模块实现客户端和数据库服务器连接.

2)客户端插入数据，代理端对明文SQL语句中明文数据进行加密，保证数据库中存储的所有数据都是密文.

①代理端查找数据所在列，取出该列对应随机数d(本方案中加密随机数d的维度为数据库表的列，即表中每列数据加密的随机数d相同).

②代理端通信模块调用加解密模块Encry(pks,d,m)算法重写SQL语句中明文数据为密文.

③代理端通信模块向数据库服务器发送插入数据请求，在数据库中插入密文.

3)客户端查询语句中含有表达式时，代理端生成重加密表达式recryptExpression，向密文数据库发送请求查询，以查询m1*m2+m3(mi在数据库中以密文ci形式存储)为例.

①代理端调用算法DGen(pks)生成新的随机数d.

②通信模块调用加解密模块中重加密表达式生成算法Recry(pks,d,expression)，根据运算表达式和重加密策略，生成可以进行加法乘法同态运算的重加密表达式recryptExpression即c1*c2Y+c3Y3.

③通信模块向数据库服务器发送重加密表达式，发起密文查询.由于数据库中存储数据为密文，数据库实际查询表达式为c1*c2Y+c3Y3，根据式(3)可知,查询结果为同态计算结果(m1m2+m3)gxd(modp).

4)数据库服务器返回应答响应，代理端解密重写密文数据响应应答客户端查询请求.

①通信模块调用加解密模块解密算法Decry(pks,d,c)解密重写密文.

②通信模块向客户端发送查询结果，响应客户端查询请求.

3 安全性分析

3.1 ELGamal重加密算法安全

定理假设DDH问题是困难的，则ELGamal重加密算法在随机预言机模型下是IND-CPA安全的.

现在通过一个游戏来证明以上定理.游戏中假设概率多项式时间算法A为敌手，多项式时间算法B为挑战者.如果敌手A能以不可忽略优势AdvA攻破ELGamal重加密算法，挑战者B可以在以(p,g,g1=ga,g2=gb,g3)为输入(其中g3=gab或者gc，a，b，c是随机数)，调用算法A的情况下以不可忽略的概率解决DDH问题.挑战者B与敌手A交互过程如下：

1)初始化阶段：挑战者B生成公钥p，g，gxmodp，私钥x，随机数a,b,c，并将公钥发送给敌手A.

①问询阶段1：敌手A在明文域中随机选取两个相同长度的明文m0，m1发送给挑战者B.

②挑战阶段：挑战者B获得明文后，从比特值{0，1}中随机选取n的值，计算c1=ga，c2=mng3(modp),其中g3=gab或者gc，并将密文组(c1，c2)发送给敌手A.

③问询阶段2：同问询阶段1过程相同.

④猜测阶段：敌手A获得密文后，猜测n′值，即挑战者B是对m0进行的加密还是对m1进行的加密.挑战者B获得敌手A猜测比特值，如果n′=n输出“True”,否则输出“False”.

2)挑战阶段B对g3不同的选择会导致敌手A 在猜测阶段出现两种不同情况.

①挑战者B选择g3=gab，挑战阶段敌手A收到的是一个合法密文对，如果敌手A可以攻破ELGamal密码体制改进方案，则会正确猜测n′值，挑战者B将以不可忽略概率输出“True”即Pr[B(p,g,ga,gb,gab)=1]=AdvA.

②挑战者B选择g3=gc，挑战阶段敌手A收到的是一个非法密文对，此时敌手A对n′值的猜测与n值无关，挑战者B将以相等的概率输出“True”或“False”，即Pr[B(p,g,ga,gb,gc)=1]=1/2.

由于DDH问题是困难的，不存在多项式时间解决算法，所以挑战者B存在可忽略概率优势输出“True”，即存在可忽略概率函数negl(k)满足

negl(k)≥|Pr[B(p,g,ga,gb,gab)=1]-

Pr[B(p,g,ga,gb,gc)=1]|≥

|AdvA-1/2|

(4)

所以AdvA≤negl(k)+1/2，由此证明不存在具有概率多项式时间算法的敌手A可以以不可忽略概率攻破ELGamal密码体制改进方案，定理1得以证明：假设DDH问题是困难的，则ELGamal密码体制改进方案在随机预言机模型下是IND-CPA安全的.

3.2 加密数据库安全

基于ELGamal重加密算法的加密数据库中客户端和加密代理端是可信的，DBMS服务器容易遭受攻击.本文提出的加密数据库的安全目标是在攻击者攻破数据库的情况下保证数据的安全性，攻击模型包括数据库管理员(Database Administrator,DBA)攻击和外部攻击，如图3所示.

图3 攻击模型Fig.3 Attack Model

DBA攻击为恶意数据库管理员使用高级权限获取数据库中密文数据；外部攻击为攻击者利用系统漏洞攻破数据库或者获取数据库管理权限从而窃取服务器存储数据，两种攻击模型中攻击者均致力于获取数据库存储数据不会破坏查询请求和数据结构.本加密数据库系统中攻击者即使成功攻破数据库，获取信息也均为ELGamal重加密算法密文，定理证明假设DDH问题是困难的，则ELGamal重加密算法在随机预言机模型下是IND-CPA安全的，所以本文实现加密数据库在被攻破情况下是IND-CPA安全.

如表1所示,CryptDB系统使用的Paillier算法具有语义安全，本文方案中的ELGamal重加密算法具有IND-CPA安全.相比较而言，本文方案虽然略低于CryptDB系统，仍可以保证隐私数据安全.

表1 本文方案与CryptDB系统功能及安全性对比分析Tab.1 Function and security comparative analysis of the scheme in this paper and the CryptDB system

4 实现与分析

4.1 实验实现

1)实现平台搭建.

实验硬件环境：台式机；GPU I7-9700 3 GHz；内存为16 G；操作系统为Linux.

2)实现语言与参数选择.

实现语言为C++；大素数计算为NTL库大整数函数；安全参数λ为1024；公钥p为1024位二进制大素数.

重加密表达式流程需要对SQL表达式进行简化，并生成重加密表达式.重加密表达式生成流程如下：

Function parseSqlStatement

Input: SqlStatement

Output: receyptSqlStatement

1 if CMDType == SELECT, parse

SELECT expression

2 if expression has arithmetic operator,

parse operator

3 distributive expression

4 expr expression

5 return receyptSqlStatement

SQL语句表达式化简流程：

Functiondistributive

Input: Expression

Output: distributiveExpression

1 vectorAdd=split(expression,`+`);

2 for item:vectorAdd do

3 vectorMul=split(item,`*`)

4 for item:vectorMul do

5 addValues=Distributive(item)

6 mulResult=append(mulResult,‘*’,addValues)

7 result=append(result,‘+’,mulResult)

8 return distributiveExpression

生成重加密表达式流程：

Function expr

Input: Expression

Output: recryptExpression

1 expBlock=split(expression,‘+’)

2 for item:expBlock

3 if operator==‘*’

4 item=recryptMul(item);

5 else

6 item=recryptAdd(item);

7 return distributiveExpression

4.2 实验测试

实验对加法、乘法、混合运算3种不同类型算术表达式进行了测试，测试过程如下：

1)创建测试表，并在测试表中插入数据，测试表中变量[a,b,…,f]分别代表数值[10,20,…,60].

2)对加法、乘法及混合运算3种表达式进行测试，表2为测试表达式同态计算结果及查询时间.

表2 测试表达式同态计算结果及查询时间Tab.2 Test expression homomorphic calculation results and query time

4.3 实验效率分析

图4从实现功能与运行效率两个方面对本文方案同CryptDB系统进行对比分析.功能方面CryptDB系统仅能实现加法同态计算，本文方案在密文基础上可以进行加法、乘法以及二者混合运算，可以应用于更多场景；效率方面:以CryptDB系统完成一次加法同态计算查询时间为基本事件单元(Basic Time Unit,BTU)，本文方案进行乘法运算和混合运算时表现良好，完成一次同态查询大约需要0.5BTU，由于需要对所有加法项进行重加密导致同态加法运算表现略差，完成一次加法同态查询需要1.14BTU.