2024年3月16日发(作者：)
第
4
5
卷第
2
期
2021
年
4
月
北京交通大学学报
JOURNAL
OF
BEIJING
JIAOTONG
UNIVERSITY
Vol.
5
No.2
Apr.
202
1
文章编号
1673-0291
2021
02-0127-08
：
(
)
DOI
：
10.11860
力
essml673-0291(0200098
一种实现数据库同态计算的
ELGamal
重加密算法
黎琳
1
，
张芳X张闻宇
2a,b
(.
北京交通大学计算机与信息技术学院
，
北京
100044;
2.
山东财经大学
a.
计算机科学与技术学院
，
b
山东省区块链金融重点实验室
，
济南
250014)
摘要
：
数据库加密技术旨在解决数据库隐私数据泄露问题.现有的关于加密数据库的研究应用未
实现或仅部分实现密文数据的同态计算功能，
使得
SQL
查询语句在加密数据库中无法高效执行甚
至失效.提出一种实现数据库同态计算的
ELGamal
重加密算法
，
该算法基于
ELGamal
乘法同态密
码体制和数据库外层加密方式
，
通过将
SQL
查询语句中算术表达式重写为具有同态计算的重加密
表达式
，
实现数据库基于密文进行同态计算的目标.本文提出的
ELGamal
重加密算法在
DDH
问
题是困难的假设下可以抵抗选择明文攻击
.
关键词
：
信息安全
；
ELGamal
重加密算法
；
重加密策略
；
同态计算
；
数据库外层加密方式
中图分类号
:
TP309
文献标志码
:
A
ELGamal
re-encryption
algorithm
for
database
homomorphic
computation
LI
i
ZHANG
Fang
1
ZHANG
Wenyu
2
,
(1.
School
of
Computer
and
Information
'Technology,
Beijing
Jiaotong
University
,
Beijing
100044,
China
；
2a.
School
of
Computer
Science
and
Technology
,
ng
Key
Laboratory
of
Blockchain
Finance
,
Shandong
University
of
Finance
and
Economics
,
Jinan
250014
,
China)
Abstract
:
Database
encryption
technology
aims
at
solving
the
problem
of
database
privacy
data
leakage.
The
existing
researches
and
applications
on
encrypted
database
have
not
realized
or
only
partially
realized
the
homomorphism
calculation
function
of
ciphertext,
data
,
which
makes
the
SQL
query
statements
una
ble
to
be
executed
efficiently
or
even
invalid
in
encrypted
database.
This
paper
proposes
an
ETGamal
re
encryption
algorithm
based
on
ETGamal
multiplicative
homomorphism
cryptography
and
database
outer
encryption
method
to
realize
database
homomorphism
computation.
By
rewriting
the
arithmetic
expression
in
SQL
query
statement
to
the
re-encryption
expression
that
can
carry
out
homomorphism
computation
,
the
homomorphism
computation
target
of
database
based
on
ciphertext
is
realized.
Assum
ing
that
the
DDH
problem
is
difficult,
the
ETGamal
algorithm
proposed
in
this
paper
can
resist
the
choice
of
plaintext.
Keywords
:
information
security;
ELGamal
algorithm
；
policy;
homo
morphic
calculation
；
database
outer
layer
encryption
收稿日期
：
2020-08-26
基金项目
：
国家自然科学基金
(U1836105)
；
国家重点研发计划
(2019QY2403)
Foundation
items
：
National
Natural
Science
Foundation
of
China
(UJ.836J.05)
；
National
Key
R
&■
D
Plan(2019QY2403
)
第一作者
：
黎琳
(
1978
—
)
，
女，
山东济南人
，
副教授
，
博士.研究方向为密码学及应用.
：
**************.cn
.
引用格式
：
黎琳•张芳•张闻宇
.
一种实现数据库同态计算的
ELGamal
重加密算法
［
J.
北京交通大学学报
.2021.45(2)
：
127
—
134.
LI
Lin
,
ZHANG
F
an
g.
ZHANG
W
eny
u.
E
Ldml!
r
e-e
n
cry
p
tio
n
al
g
orith
m
for
c
II
i
s
c
h
omom
orp
h
ic
c
o
mp
iita
io
n
L
JJ
eJ
)li
ml
of
B
eijin
g
J
iaoton
g
U
niversity
,
2021,
45(2)
:
12?
—
134.(in
Chinese)
128
北京交通大学学报
第
4
5
卷
随着数据泄露问题频发
，
造成的经济损失和社
1)
Alice
生成密钥
.
①
随机生成大素数
P
,
且要求
p
至少有一个大
会影响持续加剧.人们基于数据库系统设计出一系
列保护数据机密性的安全策略
［
1
］
.当前防火墙
、
访问
控制和入侵检测等方案的安全性均基于攻击者未攻
素数因子
.
②
生成模
p
的乘法群
G
，
选取乘法群
G
的一个
入服务器.但是事实证明数据泄露问题主要由攻击
者绕开或攻破以上防御方案直接攻入服务器⑵或者
生成元
g
.
③
随机选择
x
e
Z
p
-1
作为私钥
.
④
计算公钥
y
=
g
x
mod
p
.
恶意服务器管理员闪引发.为从根本上保护数据安
全
，
主流数据库产品开始研究加密数据库技术
.
⑤
公开公钥
：
p
、
g
、
y
,
保存私钥
x
.
相比于无法基于密文进行计算的传统密码体
制
［
4
］
，
全同态加密的同态性质可以解决数据隐私和
密文计算问题.自
2009
年
Gentry
首次提出基于格
困难问题的全同态加密构造方案
［
5
］
，
发展到无需密
钥参与即可进行同态计算的第三代技术方案
［
6
］
,
同
态计算的效率不断提高
［
58
］
，但是依然存在密钥生成
困难
，
同态计算耗时过长等问题
，
无法真正实际应
用
［
9
］
.为此研究人员提出使用部分同态加密算法解
决实际应用中密文计算的方案
［
10
］
.
2011
年麻省理工
计算机科学与人工智能实验室
(
Computer
Science
and
Artificial
Intelligence
laboratory,
CSAIL)
首
次提出具有加法同态性质的
［
11
］
系统
，
该系
统采用
Paillier
［
213
］
加法同态算法和洋葱加密策略
,
支持在密文数据库中进行
SQL
加法查询
，
目前已被
和林肯实验室
(Lincoln
Labs)
采用.然而由
于
CryptDB
只应用了加法同态密码体制
，
无法对密
文进行乘法以及混合运算
，
对密文计算应用意义
较小
.
本文作者基于数据库管理系统
(
Database
Man
agement.
System
,
DBMS
)
外层加密技术和
ELGamal
乘法同态密码体制提出一种实现数据库
同态性质的
ELGamal
重加密算法
，
在
ELGamal
密
码体制乘法同态性质的基础上新增实现了加法同态
性质
，
并实现了密文加法和乘法混合运算.区别于代
理端为实现数据共享采用的重加密技术
［
14
］
,
本文中
的重加密是一种为实现同态性质对
SQL
查询表达
式进行重加密计算的技术
.
1
ELGamal
密码体制及其同态性质
ELGamal
密码体制是
1
985
年
Taher
Elgamal
利用单向陷门函数构造的公钥密码体制.本节通过
模拟
Alice
和
Bob
利用
ELGamal
密码体制通信的
过程
，
详细描述
ELGamal
密码体制
［
1516
］
.
通信过程
中
Alice
作为消息接收方
,
Bob
作为消息发送方
.
1.1
ELGamal
密码体制
ELGamal
密码体制由密钥生成
、
加密消息
、
解
密消息三部分组成
.
2)
Bob
对消息进行加密
.
①
选取随机数
d
满足
1
<
d
<
p
.
②
生成明文消息
m
的密文对
C
1
=
g
d
,
c
2
=
mg
dx
mod
p
.
③
将密文对发送给
Alice.
3)
Alice
解密得到消息
.
Alice
解密密文对
，
得到明文
m
=c
2
/
c
i
x
mod
p
.
1.2
基于
DDH
困难问题的
IND-CPA
ELGamal
密码体制基于
DDH
［
1718
］
困难问题具
有选择明文攻击下的不可区分性
(
INDistinguish-
ability
under
Chosen-Plaintext.
Attack,
IND-CPA).
DDH
困难问题为已知大素数
p
，
生成元
g
,
g
a
和
g
b
情况下以不可忽略概率区分
g
”
的准确值是困难
的
，
其中
"
e
{
()
,1},
g
1
=
g"
b
,g
2
=
g
c
.
假设
Alice
和
Bob
使用
ELGamal
密码体制对
通信消息进行加密.通信过程中攻击者可以从信道
中截获到所有公钥信息
：
大素数
p
、
乘法群
G
的生成
元
g
、
公钥
y
以及密文对
c
,
2
.
目前不存在以不可忽
略概率解决
DDH
困难问题的神谕机
，
所以攻击者
根据截获信息无法以不可忽略概率计算出解密必需
参数
g
xd
,
进而解密密文
c
得到明文消息
.
1.3
ELGamal
密码体制的同态性质
1)
ELGamal
密码体制具有乘法同态性质
.
明文
m
1A
m
2
分别由密钥
g
,x
和随机数
d
1
,d
2
加密得到密文对
(
c
n
,2
)和
(
C
1
,
22
)
，
密文对相
乘可得
(
C
］
1
*
C
21,
C
12
*
C
22
)
即
(
g
d
*
g
d
2
,
mg
d1
m
2
g
d2
mod
p
)
.显而易见
，
该密文对为密钥
y
,
x
和随机数
(
d
1
+
d
2
)
对明文
m
1
*
m
2
加密密文.计
算解密公式
c
12
*5/(
11
*
C
21
)
x
mod
p
即可正确解
密得到明文乘积
m
1
*
m
2
.
所以
ELGamal
密码体制
具有乘法同态性质
.
2)
ELGamal
密码体制具有混合乘法同态性质
.
已知明文
m
1
由密钥
g
,
x
及随机数
d
加密得
到的密文组
(
C
1
,c
),
明文
m
2
和密文相乘得到
(
c
,
m
2
*
c
2
)
即
(
g
d
,m
1
*
m
2
g
d
mod
p
)
.
显而易见
，
该密
文对为密钥
g
x
和随机数
d
对明文乘积
m
］
*
m
2
加
密得到密文.计算解密公式
mcC
mod
p
即可正确
第
2
期
黎
琳等
：
一种实现数据库同态计算的
ELGamal
重加密算法
129
解密得到明文乘积
m
1
*
m
2
.
所以
ELGamal
密码体
制具有混合乘法同态性质
•
3)
ELGamal
密码体制不具有加法同态性质
.
DBMS
服务器的连接
•
2)
用户通过客户端请求向数据库插入数据
，
代
理端调用用户密钥和加密算法对数据进行加密
，
将
明文
m
、
、
m
2
由密钥
g
,
x
和随机数
d
1
,
d
2
加密
密文存入数据库
•
3)
用户在客户端发出
SQL
查询请求
，
代理端根
分别得到密文组
(
c
h
,
5
)和
(
C
1
,
cc
)
，
密文进行
任何计算都无法得到明文相加即
m
+
m
2
加密的密
据查询语句类型和加密算法对
SQL
查询请求加密
文.故
ELGamal
密码体制不具有加法同态性质
•
重写
，
向
DBMS
服务器密文数据进行查询
，
DBMS
2
ELGamal
重加密算法
2.1
应用场景
服务器正常完成数据库查询生成应答响应提交代理
端
，
代理端对
DBMS
服务器应答重写解密返回客户
端完成整个会话过程
•
当前加密数据库通常采用数据库安全中间件对
数据进行加密
，
主要分为:
DBMS
外层(客户端)加
密
.DBMS
内层(服务器)加密和基于文件级的加解
密技术
3
种方式.相比
DBMS
内层加密和基于文件
级加解密技术
.DBMS
外层加密方式将数据加解密
功能放在可信第三方
，无需对客户端和服务器进行
改动即可实现数据库密文存储保障数据安全
，
在实
际生活中被广泛应用
•
本加密数据库选择
DBMS
外层加密方式实现
数据库加解密功能•数据库系统由客户端、
加密代理
端和
DBMS
服务器三部分构成
，
见图
1.
I
I
-----
L
宾
客户端
「
1
发送
1
•客户端
SQL
语句
通信模块
响应数据|
3
•舲|
加密代理端
发送
1
•客户端
SQL
语句
客户端
图
1
DBMS
外层加密数据库系统
Fig.1
DBMS
outer
encrypted
databasesystem
代理端由密钥管理模块
、
通信模块和加解密模
块构成•密钥管理模块负责为用户生成密钥并对密
钥进行存储和调用
；
通信模块对客户端和
DBMS
服
务器之间的会话分析重写
，
通过调用密钥管理模块
和加解密模块存储实现密文存储和查询功能
；
加解
密模块实现数据加解密功能
•
DBMS
外层加密数据库客户端和数据库服务
器会话过程如下
：
1)
用户在客户端发出会话请求连接
，
代理端调
用密钥管理模块进行密钥管理
，
同时完成客户端与
2.2
ELGamal
重加密算法
2.2.1
ELGamal
重加密算法定义
ELGamal
重加密算法由
5
个算法构成
：
密钥生
成算法
KenGen
、
随机数
d
生成算法
DGen
、
加密算
法
Encry
、
解密算法
Decry
和重加密表达式生成算
法
Recry
,
具体算法定义如下
：
1)
密钥生成算法
KenGen
Ck)
•
K1
：
输入安全参数
入
，
入
为公钥
P
二进制位数
；
K2
：
生成
入
位大素数
P
；
K3
：
生成模
P
乘法群
G
的随机生成元
g
；
K4
：
随机选取
x
6
乙
-
1
；
K5
:
输出公钥
Pk
s
:
P
,
g
,
g
x
mod
P
，
私钥
sk
s
=
x
.
2)
随机数
d
生成算法
DGen
(Pk
s
)
•
DI
：
输入公钥
P
；
D2
：
选取随机数
d
6
乙-
1
；
D3
：
输出随机数
d
；
3)
加
密
算
法
Encry
(
Pk
s
,
d
,
m
).
El
：
输入公钥
Pk
s
、
随机数
d
和明文
m
；
E2
：
计算密文
c
=
mg
xd
mod
P
；
E3
：
输出密文
c
；
4)
解密算法
Decry
(
k
s
,
•
D1
:输入私钥
sk
s
、
随机数
d
和密文
c
；
D2
：
计算明文
m
=
c
(„g
x
d
)
-
1
mod
P
；
D3
：
输
出
明
文
m
；
5)
重加密表达式生成算法
RecyPk
s
,d
,
exPression
).
Rl
：
输入公钥
Pk
s
、
随机数
d
和查询语句中逻
辑表达式
exPression
；
R2
：
根据重加密策略生成重加密表达式
；
R3
：
输出重加密表达式
rcytExPression
.
2.2.2
重加密策略
ELGamal
重加密算法根据表达式运算符类型
为
SQL
查询表达式制定重加密策略
.+
，
和
‘
*
，
运
算符可以组成三种不同类型
SQL
查询语句表达式
:
130
北京交通大学学报
第
4
5
卷
乘法计算表达式
、
加法计算表达式和混合计算表达
式
(
2)
表示加法表达式
c
+
c
+
…
c
重加密计
算
，
密文同样是
ELGamal
密码体制中密文
，
同时实
现了加法同态计算
.
3)
混合运算重加密策略的正确性和同态性
.
式
，
ELGamal
重加密算法针对以上每种情况制定相
应重加密策略以实现密文同态计算
.
1)
乘法重加密策略
.
SQL
查询语句只存在乘法算术运算即表达式
查询语句中的混合计算重加密时需要遵循乘法
形式如
cc
…C
”
,
通过乘法重加密策略生成表达式
C
1C2-Cn
Y(Y
=
(g
xd1
g
l
d
2
-g
l
d
n
)
—
1
g
xd
mod
p
)
.
数据
项和加法项的重加密规则.重加密表达式具有同态
性质
，
可以进行混合计算.公式表示如下
c
1C2
Y
+
c
3
Y
3
=
(
n
J
g
I
dJ
m
2
g
l
d2
:
*
(
g
xd
1
g
xd
2
)
—
1
g
xd
(mod
P
)
+
库服务器对重加密表达式计算结果对应表达式
m
1
m-
i
"-
m
n
g
l
d
(mod
p
:
计算结果
，
即私钥
x
和随机
数
d
对
m
1
m
2
…
m
n
加密密文
.
mg
d
(.
g
I
d3
)
—
J
g
I
d
(nod
P
)
=
2)
加法重加密策略
.
SQL
查询语
句
只
存
在
加
法
算
术
运
算
即
表
达
式
形如
c
+
c
-------
C
n
,
重加密策略对每个加法项进
行重加密生成重加密表达式
C
1
Y
1
+
c
2
Y
2
+
…
+
C
n
Y
n
(
Y
,
=
(g
xd
)
—
1
g
xd
mod
p
:
，重加密表达式可看
作
(
m
i
+
m
2
+
m
n
)g
xd
(mod
p
:
，
即私钥
x
和随
机数
d
对
m
i
+
m
2
+
…
+
m
n
加密密文
.
3)
混合运算重加密策略
.
SQL
查询语
句
表
达
式
为
混
合
运
算
即
加
法
和
乘
法运算同时存在时
，
重加密策略规定如果表达式是
包含括号的复杂表达式则将表达式修改为不存在括
号的简单表达式如
cc
+
C
,
并按照乘法重加密策
略和加法重加密策略生成重加密表达式.此例中先
对乘法项进行重加密
c
1C
2
Y
，
再对加法项进行重加
密
c
3
Y
3
,
生成的重加密表达式为
cc
^
Y
+
cY
s
,
即
(mm
2
+
m
3
)g
l
d
(mod
p
)
.
同时规定混合运算重加
密策略对所有计算项仅进行一次重加密
.
2.2.3
重加密策略正确性与同态性
ELGamal
重加密算法满足乘法同态和加法同
态.下面进行证明
.
1)
乘法重加密策略的正确性和同态性
.
cc
…
cY
=
(m/
M
m
^
g
S
…
m
”
g
xd
n
:
*
(g
xd
1
g
xd
2
...
g
xd
n
)
—
1
g
xd
mod
p
=
m
]
m
2
…
m
”
g
xd
(mod
p
)
(1
)
由式
(
1)
可知乘法表达式重加密计算结果为对
应明文乘积加密密文
，
密文为相同密钥和新随机数
d
对明文乘积加密得到.显而易见
，
重加密密文依然
是一个
ELGamal
密码体制中的密文
，
实现了乘法
同态计算
.
2)
加法重加密策略的正确性和同态性.
cY
1
+
cY
2
+
•••+
c
”
nn
Y,
(
c
(g
xd
1
)
—
1
g
xd
+
c
(g
xd
xd
2
2
)
1
1
g
xd
—
xd
+
----
+
c
n
g
d
n
)
—
1
g
xd
)
mod
p
=
(
m
1
+
m
+
…
+
m
n
)g
l
d
(mod
p
:
m
1
m
2
g
xd
(mod
p
)
+
m
3
g
xd
(mod
p
)
=
(
m
1
m
2
+
m
3
)
g
xd
(mod
p
)
(
)
2.3
数据库同态计算实现方案
加密数据库在加解密模块使用
ELGamal
重加
密算法实现
SQL
表达式同态计算
，
图
2
表示加密数
据库同态计算实现过程
.
1
)
客户端请求连接
，
代理端调用密钥管理模块,
建立客户端和数据库服务器连接
.
①
客户端首次请求连接
，
代理端调用密钥管理
模块
KenGenk)
算法为客户端生成并保存密钥
.
②
客户端非首次连接或代理端完成密钥管理,
通信模块实现客户端和数据库服务器连接
.
2)
客户端插入数据
，
代理端对明文
SQL
语句中
明文数据进行加密
，
保证数据库中存储的所有数据
都是密文
.
①
代理端查找数据所在列
，
取出该列对应随机
数
d
(
本方案中加密随机数
d
的维度为数据库表的
列
，
即表中每列数据加密的随机数
d
相同
)
.
②
代理端通信模块调用加解密模块
Encry(pk
s
,d
,m)
算法重写
SQL
语句中明文数据
为密文
.
③
代理端通信模块向数据库服务器发送插入数
据请求，
在数据库中插入密文
.
3)
客户端查询语句中含有表达式时
，代理端生
成重加密表达式
recryptExpression
，
向密文数据
库发送请求查询
，
以查询
m
1
*
m
2
+
m
3
(
m
i
在数据
库中以密文
c
形式存储)为例
.
①
代理端调用算法
DGenpk
s
)
生成新的随机
数
d
.
②
通信模块调用加解密模块中重加密表达式生
成算法
Recry
pk
s
,d
,
expression
:
,
根据运算表达式
和重加密策略
，
生成可以进行加法乘法同态运算的重
加密表达式
recryptExpression
即
c
1
*
c
2
Y
+
c
3
Y
3
.
③
通信模块向数据库服务器发送重加密表达
式
，
发起密文查询.由于数据库中存储数据为密文
,
第
2
期
黎
琳等
：
一种实现数据库同态计算的
ELGamal
重加密算法
131
数据库实际查询表达式为
c
1
*
c
2
Y
+
c
3
Y
3
,
根据式
(3
)
可知
，
查询结果为同态计算结果
(
m
1
m
2
+
m
3
')g
x
d
(mod
p
)
•
①
通信模块调用加解密模块解密算法
Decry
Qpk
s
d
,)
解密重写密文
.
②
通信模块向客户端发送查询结果
，
响应客户
4)
数据库服务器返回应答响应
，
代理端解密重
端查询请求
•
写密文数据响应应答客户端查询请求
•
-N-
首次连接?
J
客户端
连接请求
-Bit
数据库管理系统
数据
加密重写
通信模块
发送
/
重写
会謠请求
4
会话-会话请求
|应答
U
密文
解密重写
加密代理端
卜
一
I
会话处理
+应答响应
_____
I
Q
据库
加密数据
应答
响应
客户端
DBNS
服务器
图
2
加密数据库同态计算实现过程
Fig.
2
Implementation
process
of
encrypted
database
homomorphic
calculation
3
安全性分析
3.1
ELGamal
重加密算法安全
加密.挑战者
B
获得敌手
A
猜测比特值
，
如果
”
=
”
输出
“
True
”
，
否则输出
“
False
”
.
2)
挑战阶段
B
对
g
a
不同的选择会导致敌手
A
定理
假设
DDH
问题是困难的
，
则
ELGamal
在猜测阶段出现两种不同情况
.
①
挑战者
B
选择
g
a
=
g
a
，
挑战阶段敌手
A
收
重加密算法在随机预言机模型下是
IND-CPA
安
全的
.
到的是一个合法密文对
，
如果敌手
A
可以攻破
EL-
Gamal
密码体制改进方案
，
则会正确猜测
”
值
，
挑
现在通过一个游戏来证明以上定理.游戏中假
设概率多项式时间算法
A
为敌手
，
多项式时间算法
B
为挑战者.如果敌手
A
能以不可忽略优势
Adv
A
战者
B
将以不可忽略概率输出
“
True
”
即
Pr
[B
p
,
g
g
a
g
b
g
a
b
)
=
1
]
=
Adv
A
•
②
挑战者
B
选择
g
a
=
g
c
，
挑战阶段敌手
A
收到
攻破
ELGamal
重加密算法
，
挑战者
B
可以在以
p
,
g
g
1
=
g
a
g
2
=
g
b
g
a
)
为输入(其中
g
a
=
g
a
b
或者
的是一个非法密文对
，
此时敌手
A
对
”
值的猜测与
g
c
a
b
,
是随机数
)
，
调用算法
A
的情况下以不
值无关
，
挑战者
B
将以相等的概率输出
“
True
”
或
"False",
即
Pr[_Bp
,
g
,
g
a
,
g
b
,
g
c
)
=
1]
=
1/2.
可忽略的概率解决
DDH
问题.挑战者
B
与敌手
A
交互过程如下
：
1)
初始化阶段
：
挑战者
B
生成公钥
p
,
g
,
由于
DDH
问题是困难的
,
不存在多项式时间
解决
算
法
所
以
挑
战
者
B
存
在
可
忽
略
概
率
优
势
输
出
“
True
”
,
即存在可忽略概率函数
neglCk)
满足
negKk
)
>|
P
厂
[
B(
p,
g
,
g
a
,
g
b
,
g
b
=
1]
—
g
x
mod
p
，
私钥
x
，
随机数
a
,
b
,
c
，
并将公钥发送
给敌手
A.
①
问询阶段
1
敌手
A
在明文域中随机选取两
PrLBp
,
g
,
g
a
,
g
b
,
g
c
)
=
1]
|
>
Adv
A
—
1/2
(4)
个相同长度的明文
m
。
,
m
发送给挑战者
B.
②
挑战阶段
：
挑战者
B
获得明文后
，
从比特值
所以
AV
a
<
negl
(k
)
+
1/2,
由此证明不存在具有概
率多项式时间算法的敌手
A
可以以不可忽略概率攻
破
ELGamal
密码体制改进方案
，
定理
1
得以证明
：假
设
DDH
问题是困难的
，
则
ELGamal
密码体制改进方
{0,1}
中随机选取
”
的值
，
计算
c
1
=
g
a
,
2
=
mg
a
(mod
p
)
，
其中
g
a
=
g
a
b
或者
g
c
，
并将密文组
(
c
1
,
c
2
)
发送给敌手
A.
③
问询阶段
2
：
同问询阶段
1
过程相同
•
④
猜测阶段
：
敌手
A
获得密文后
，
猜测
”
值
,
案在随机预言机模型下是
IND-CPA
安全的
•
3.2
加密数据库安全
基于
ELGamal
重加密算法的加密数据库中客
户端和加密代理端是可信的
，
DBMS
服务器容易遭
即挑战者
B
是对
m
0
进行的加密还是对
m
1
进行的
132
北京交通大学学报
第
45
卷
受攻击.本文提出的加密数据库的安全目标是在攻
击者攻破数据库的情况下保证数据的安全性
，
攻击
模型包括数据库管理员
(
Datatase
Administrator,
DBA)
攻击和外部攻击
，
如图
3
所示
.
客户端
力口密代理端
DBMS服务器
图
3
攻击模型
Fig.
3
Attack
Model
DBA
攻击为恶意数据库管理员使用高级权限
内存为
16
G
；
操作系统为
Linux.
2)
实现语言与参数选择
.
获取数据库中密文数据
；
外部攻击为攻击者利用系
统漏洞攻破数据库或者获取数据库管理权限从而窃
实现语言为
C+
+
；
大素数计算为
NTL
库大整
取服务器存储数据
，
两种攻击模型中攻击者均致力
于获取数据库存储数据不会破坏查询请求和数据结
数函数
；
安全参数
入
为
1024
；
公钥
P
为
1024
位二进
制大素数
•
构.本加密数据库系统中攻击者即使成功攻破数据
库
，
获取信息也均为
ELGamal
重加密算法密文
，
定
理证明假设
DDH
问题是困难的
，
则
ELGamal
重加
重加密表达式流程需要对
SQL
表达式进行简
化,并生成重加密表达式.重加密表达式生成流程
如下
：
FunctionparseSqlStatement
密算法在随机预言机模型下是
IND-CPA
安全的
,
所以本文实现加密数据库在被攻破情况下是
IND-
CPA
安全
•
Input
：
SqlStatement
Output
：
receyptSqlStatement
如表
1
所示
，
CryptDB
系统使用的
Paillier
算法
1
if
CMDType
==
SELECT
,
parse
SELECTexpression
具有语义安全
，
本文方案中的
ELGamal
重加密算
法具有
IND-CPA
安全.相比较而言
，
本文方案虽然
略低于
CryptDB
系统
，
仍可以保证隐私数据安全
.
表
1
本文方案与
CryptDB
系统功能及
安全性对比分析
Tab.1
Function
and
security
comparative
analysis
2
if
expression
has
arithmetic
operator,
parseoperator
3
4
distributive
expression
exprexpression
5
return
receyptSqlStatement
SQL
语句表达式化简流程
：
F
unctiondistributive
of
the
scheme
in
this
paper
and
the
CryptDBsystem
系统功能
Input
：
Expression
安全性
Output
:
distributiveExpression
加法运算
IND-CPA
IND-CPA
IND-CPA
语义安全
1
vectorAdd=
splitCexpression
,'+')
；
基于
ELGamal
重加密
算法的加密数据库
乘法运算
混合运算
2
for
item
:
vector
Add
do
3
/
vectorMul=
splitCitem
,'
*
')
for
item
:
vectorMul
do
CryptDB
系统
加法运算
5
addValues
=
Distributive
(item)
mulResult=append(mulResult,
‘
*
'
>
add
Values)
4
实现与分析
4.1
实验实现
1)
实现平台搭建
•
6
7
result=
append
(result
，
‘
+
‘，
mulResult)
8returndistributiveExpression
生成重加密表达式流程
：
Function
expr
实验硬件环境
：
台式机
；
GPU
I7-9700
3
GHz
；
第
2
期
黎
琳等
：
一种实现数据库同态计算的
ELGamal
重加密算法
133
Input
：
Expression
Output
:
recryptExpression
1
expBlock=
splitCexpression,
‘
+
')
2
for
item
:
expBlock
3
if
operator=
=
'
*
)
item
=
recryptMuK
item)
;
else
4
5
6
item
=
recrypt
Add
(item)
；
7returndistributiveExpression
4.2
实验测试
实验对加法
、
乘法
、
混合运算
3
种不同类型算术
表达式进行了测试,测试过程如下
：
1)
创建测试表
，
并在测试表中插入数据
，
测试表
中变量
LaJ,-
f
J
分别代表数值
［
0,20,
・・・
，
60J.
2)
对加法
、
乘法及混合运算
3
种表达式进行测
试
，
表
2
为测试表达式同态计算结果及查询时间
•
表
2
测试表达式同态计算结果及查询时间
Tab.
2
Test
expression
homomorphic
calculation
results
and
query
time
测试表达式
计算结果
查询解密时间
/s
a
*
b
*
c
6000
<0.01
a+b+
c
60
005
a
*
b
*
c
+
C+f
*
e
9040
<001
4.3
实验效率分析
图
4
从实现功能与运行效率两个方面对本文方
案同
CryptDB
系统进行对比分析.功能方面
CryptDB
系统仅能实现加法同态计算
，
本文方案在
密文基础上可以进行加法
、
乘法以及二者混合运算
,
可以应用于更多场景
；
效率方面
：
以
CryptDB
系统
完成一次加法同态计算查询时间为基本事件单元
(Basic
Time
Unit,BTU),
本文方案进行乘法运算
和混合运算时表现良好
，
完成一次同态查询大约需
要
0.5BTU,
由于需要对所有加法项进行重加密导
致同态加法运算表现略差
，
完成一次加法同态查询
需要
1.14BTU.
5
结论
1)
提出一种实现数据库同态计算的
ELGamal
重加密算法
，并详细介绍了实现方案.同可以基于密
文进行加法计算的
CryptDB
系统相比
，
本文方案在
保证安全性的前提下实现了密文数据库更多计算
功能
•
2)
在抵抗选择明文攻击情况下
，
增加实现基于
密文乘法及加法乘法混合运算性质
，
满足了数据库
在密文上进行同态计算的需求.实验表明
，
该方案性
能表现良好
•
图
4
本文方案与
CryptDB
系统运行
效率对比分析
Fig.
4
Efficiency
comparative
analysis
of
the
scheme
in
this
paper
and
the
CryptDB
system
下一步将该方案在并行服务器上进行应用
,
以
进一步提高效率•在云计算日益普及的背景下
，不改
变数据库结构实现密文同态计算的算法和数据处理
策略将成为未来的研究热点
•
参考文献
(
References
)
:
[1J
王金国
，
高鹏.核心数据库保护安全技术实践
[J.
网络安
全和信息化
,2019(7):121
—
124.
WANG
Jinguo
,
GAO
Peng.
Practice
of
security
technol
ogy
for
core
database
protection]
J
J.
Cybersecurity
&
in-
formatization,
2019(7)
:
121
—
124.
(in
Chinese)
[J
朱鲁华
，
陈荣良.数据库加密系统的设计与实现
[J.
计算
机工程
,2002,28(8)
：
61
—
63.
ZHU
Luhua,
CHEN
RongLiang.
Design
and
implemen
tation
of
database
encryption
system[J.
Computer
En
gineering
,2002,
28(8)
：
61
—
63.
(in
Chinese)
[3
J
TATE
R.
Why
you
shouldn't
trust
with
your
da
ta
：
an
employee's
revelations
[EB/OLJ.
(2010-01-11)
[2020-06-19
J.
https
：
/
/gawker,
com/
5445592
/
why-you-
shouldn--
trust-
facebook-
with-
your-
data-
an-
employees-
reve
lations.
[4J
吴婧.浅析数据库加密技术
[J.
数字技术与应用
，
2016
(5)
：
212.
WU
is
of
database
encryption
technologyUJ.
Digital
Technology
and
Application,
2016(5)
：
212.
(in
Chinese)
[5
J
GENTRY
C.
Fully
homomorphic
encryption
using
ideal
lattices[CJ//Proceedings
of
the
41st
Annual
ACM
Sym
posium
on
Theory
of
Computing.
Bethesda,
2009
：
169
—
178.
[J
GENTRY
C,
SAHAI
A,
WATERS
B.
Homomorphic
encryption
from
learning
with
errors
:
conceptually-sim-
pler
,
asymptotically-faster
,
attribute-based
[
CJ//Ad
vances
in
Cryptology.
Berlin,
2013
:
75
—
92.
134
北京交通大学学报
第
45
卷
[7]
BRAKERSKI
Z,
GENTRY
C,
VA1KUNTANATHAN
V.
Fully
homomorphic
encryption
without
bootstrapping
Cryptology.
Berlin,
1
999：
223
—
238.
[13]
刘雪萍
•
CryptDB
中具有同态性质的加密算法的研究
JJ
].
ACM
'Transactions
on
Computation
Theory,
2014
,
6(3)
：
1
—
36.
与应用
[)].
北京
：
北京邮电大学
，
201
&
LIU
Xueping.
Research
and
application
of
homomorphic
[]
王付群
•
全同态加密的发展与应用信息安全与通信
encryption
algorithm
in
cryptI)B[l)].
Beijing：
Beijing
Uni
versity
of
Posts
and
Telecommunications
,
2018.
(in
Chi
nese)
[14]
LIN
H
Y.
Secure
content
distribution
using
multi-hop
保密
,2018,
16(11)
：
81
—
91.
WANG
Fuqun.
Development
and
application
of
homo
morphic
encryption
[J
].
Information
Security
and
Com
munications
Privacy
,
2018,
16(11)
：
81
―
9
1.
(
in
Chi
nese)
proxy
rc-cncryptionJJ
].
Wireless
Personal
Communica
tions,
2015,
82(3)
：
1449
—
1459.
[]
李浪
，
余孝忠
，
杨娅琼
，
等
.
同态加密研究进展综述
JJ]
[1
5]
ELGAMAL
T.
A
public
key
cryptosystem
and
a
signa
ture
scheme
based
on
discrete
algorithms
[C]
//Ad
vances
in
Cryptology.
Berlin
,
1
985
:
10
—
18.
计算机应用研究
，
2015,
32(1
1)
:
3209
—
3214.
LI
Lang
,
YU
Xiaozhong
,
YANG
Yaqiong
,
ct
al
Survey
on
homomorphic
encryption
technology
[J
]•
Application
Research
of
Computers,
2015,
32(1
1)
：
3209
—
32
14.
(in
[16]
杨波
.
现代密码学
[M]
2
版
•
北京
：
清华大学出版
社
，
2007.
YANG
cryptography
[M
]
.2ndedBeijing
：
Chinese
)
[10]
陈志伟
，
白健
，
杨亚涛
，
等
•
基于同态加密的密文数据
TsinghuaUniversityPress
,
2007.
(
inChinese)
库统计模型的设计与实现
[]•
信息网络安全
，
2013
(3)
：
12—
15.
[17]
陈恭亮.信息安全数学基础
[M]
北京
：
清华大学出版
社
，
2014.
CHEN
Gongliang.
Fundamentals
of
information
security
mathematics
[M
]
.Beijing：
Tsinghua
University
Press
,
CHEN
Zhiwei
,
BAI
Jian
,
YANG
Yatao
,
ct
al
The
en
crypted
database
statistical
method
based
on
homomor
phism
encryption]].
Nctinfo
Security,
2013(3)
：
12
一
2014.
(in
Chinese)
1
5.
(in
Chinese)
[18]
朱鲁华
，
陈荣良.数据库加密系统的设计与实现
[11]
POPA
R
A,
REDFIEID
C
M
S,
ZEIDOVICH
N,
ct
计算机工程
，
2002,
28(8)
：
61
—
63.
ZHU
Luhua,
CHEN
Rongliang.
Design
and
implcmcn-
tationofdatabaseencryptionsystem
[
J
].ComputerEn-
al
CryptDB[J
].
Communications
of
the
ACM
,
2012,
55(9)
：
103
—
111.
[12]
PAILLIER
P.
Public-key
cryptosystems
based
on
com
posite
degree
rcsiduosity
classes
[
C
[//Advances
in
ginccr
,
2002
,
28(8)
：
6
1
—
63.
(in
Chinese)
(
上接第
118
页
)
[13]
JIA
M
,
ZHU
S,
WANG
L
,
ct
al
Routing
algorithm
SDN
controller
placement
in
a
LEO
constellation
satellite
network
[C]//
Global
Communications
Conference.
Abu
with
virtual
topology
toward
to
huge
numbers
of
LEO
mobile
satellite
network
based
on
SI)N[J].
Mobile
Net
works
and
Applications
,
2018,
23(2):285
―
300.
Dhabi,
2018:206
—
212.
[1
6]
XU
S,
WANG
X,
GAO
B,
ct
al
Controller
placement
in
software-defined
satellite
networks
[C]//
International
[14]
ZHANG
Z,
ZHAO
B,
YU
W,
ct
al
Poster
：
an
efficient
control
framework
for
supporting
the
future
SDN/NFV-
Conference
on
Mobile
Ad-Hoc
and
Sensor
Networks.
She
nyang
,
2018
：
146
—
151.
cnablcd
satellite
nctwork[C]//
International
Conference
on
Mobile
Computing
and
Networking.
New
York,
2017
：
603
[17]
LUONG
D)
K,
HU
Y
F,
I
」
J
P,
ct
al
Mctahcuristic
ap
proaches
to
the
joint
controller
and
gateway
placement
in
5(-satellite
SDN
nctworks[C]//
International
Conference
on
Communications.
Dublin
,
2020
:
1
—
6.
—
605.
[15]
PAPA
A,
COLAT
D),
KELL
ER
ER
W,
ct
al.
Dynamic
发布者：admin，转转请注明出处：http://www.yc00.com/web/1710579534a1780823.html
评论列表（0条）