Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
6, N
o
. 1
,
Febr
u
a
r
y
201
6,
pp
. 33
7
~
34
3
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
1.9
335
3
37
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
A Comparison of the Query Exec
ution Algorithms in Secure
Da
ta
base
Syste
m
Yo
un
g-
Dal
J
a
n
g,
Ji
-H
on
g K
i
m
Department o
fIn
formation and
Teleco
mmunication, Sem
y
ungU
niversity
,
Korea
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
J
u
l 28, 2015
Rev
i
sed
No
v
21
, 20
15
Accepte
d Dec 2, 2015
In ac
cordanc
e
with the
dat
a
ba
s
e
m
a
nagem
e
nt,
DAS
(databas
e
as
s
e
rvic
e
)
model is one
solution for
ou
tsourcing.
However, we need some data
protection mech
anisms in order to main
ta
in the
datab
a
se secur
i
t
y
Them
ost
effec
tive
algor
it
hm
to secure dat
a
bases from
the
securit
y
th
rea
t
o
f
third par
t
y
att
ackers
is to e
n
cr
y
p
t th
e sensit
ive da
ta wi
thin t
h
e dat
a
base
. Ho
wever, on
c
e
we encr
ypt th
e sensitive d
a
t
a
, we
have diffi
cul
ties
in queries ex
ecu
tion on th
e
encr
ypt
e
d dat
a
b
a
s
e
. In this
pap
e
r, we focus
on
the s
earch pro
ces
s
on the
encr
y
p
ted datab
a
se. We proposed th
e selective tuple en
cr
y
p
tion metho
d
using Bloom Filter which cou
l
d
tell us
th
e ex
iste
nce of
the
da
ta
.
Finall
y,
we
compare the search performance between
th
e pro
posed method and the other
encr
y
p
tion meth
ods we know.
Keyword:
Blo
o
m
Filter
Bucket Inde
x
DAS (data
b
ase
as a se
rvice)
Datab
a
se en
cryp
tio
n
Copyright ©
201
6 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Ji
-H
on
g Ki
m
,
Depa
rt
em
ent
of
In
f
o
rm
at
i
on and
Te
lecommuincation, Semyung Uni
v
ersit
y
,
6
5
, Sem
y
eo
n
g
-r
o, Jech
eon-
si,
Ch
ung
ch
eon
gbu
k-d
o
, Kor
e
a
.
E-m
a
il
:
jh
ki
m
@
sem
y
ung.ac.
kr
1.
INTRODUCTION
Th
e n
e
w tren
d o
f
DAS system [1
] lead
s to
a n
e
w
con
c
ern, secu
rity. Especially, wh
en
th
e sen
s
itiv
e
in
fo
rm
atio
n
is
co
n
t
ain
e
d
in
the d
a
tab
a
se, it n
eed
s its co
n
f
i
d
en
tiality
in
su
ch
a
m
o
d
e
l. In
a typ
i
cal se
ttin
g
o
f
th
e
p
r
ob
lem
,
th
e co
nfid
en
tial p
o
rtio
n
s
of th
e d
a
t
a
sh
ou
ld
b
e
stored
at a rem
o
te lo
catio
n
in
an
en
cry
p
ted
fo
rm
at al
l
t
i
m
e
s. For ex
am
pl
e, dat
a
encry
p
t
i
on
bec
o
m
e
s im
port
a
nt
w
h
en t
h
e c
l
i
e
nt
cho
o
ses
t
o
hi
de a
w
ay
cert
a
i
n
co
n
t
en
ts fro
m
serv
er-sid
e en
t
ities. Two
n
e
w ch
alleng
es emerg
e
: (1) How to
en
cryp
t th
e sen
s
itiv
e
d
a
ta. (2)
How t
o
su
ppo
rt q
u
e
ries
o
n
th
e en
cryp
ted relatio
n
a
l d
a
ta.
In
or
der t
o
q
u
e
ry
effect
i
v
el
y
on t
h
e e
n
cry
p
t
e
d
dat
a
base,
user
que
ry
sho
u
l
d
be t
r
a
n
s
l
at
ed t
o
t
h
e
modified for
m
. The
m
o
d
i
fied q
u
e
ry shou
ld
b
e
su
itab
l
e to
search
th
e d
a
ta
in
th
e en
cryp
ted
d
a
tab
a
se stored
in
a DB serv
er.
Th
erefo
r
e
we
u
s
e th
e Bl
o
o
m
Filter an
d Buck
et ind
e
x
for
th
e in
dex
on
th
e en
cryp
ted
datab
a
se
search
. The m
e
t
a
dat
a
i
n
acl
i
e
nt
m
odul
e has
has
h
f
unct
i
o
ns
fo
r ge
nerat
i
n
g
B
l
oom
Fi
lt
er and t
h
e b
u
c
k
et
i
nde
x
for the
num
e
rical attributes.
There
f
ore
t
h
e
o
r
i
g
in
al qu
ery is co
nv
erted
to th
e m
o
d
i
fied
q
u
e
ry with th
e h
e
lp
of
t
h
e m
e
t
a
dat
a
. The i
nde
x i
n
se
rve
r
part
i
s
use
d
t
o
searc
h
t
h
e
exact
dat
a
f
r
o
m
t
h
e enc
r
y
p
t
e
d
dat
a
base
.
The rem
a
i
nder
of t
h
i
s
pa
per
i
s
or
ga
ni
zed
as fo
l
l
o
ws
. Se
ct
i
on 2
desc
ri
bes t
h
e
ge
ner
a
l
dat
a
bas
e
encry
p
t
i
on m
e
tho
d
s.
Sect
i
on
3 sh
o
w
s t
h
e
de
t
a
i
l
s
of t
h
e p
r
o
pos
ed m
e
t
hod
and
Sect
i
on
4 s
h
o
w
s t
h
e c
o
m
p
ari
s
o
n
bet
w
ee
n t
h
e
p
r
op
ose
d
m
e
t
hod
an
d t
h
e
ot
her
m
e
t
hods
. Fi
nal
l
y
, we c
oncl
u
d
e
wi
t
h
a
sum
m
a
ry
an
d
di
rect
i
ons
f
o
r
fut
u
re w
o
r
k
.
2.
RELATED WORK
In
ge
ne
ral
,
we
can cl
assi
fy
t
h
e dat
a
base e
n
c
r
y
p
t
i
o
n m
e
t
hods acc
o
r
di
ng
t
o
t
h
e e
n
cry
p
t
i
o
n
uni
t
.
T
h
e
r
e
aret
he el
em
ent based e
n
cry
p
t
i
on m
e
t
hods, t
h
e col
u
m
n
/
r
ow base
d enc
r
y
p
t
i
on m
e
t
hods
,
and t
h
e t
a
bl
e base
d
encry
p
tion m
e
thods.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 1, Feb
r
uar
y
20
1
6
:
33
7 – 34
3
33
8
Tabl
e
1. T
h
e
c
o
m
p
ari
s
on
bet
w
een
va
ri
o
u
s
Encry
p
t
i
o
n
M
e
t
h
o
d
s
Encryption Unit
Encryption Speed
Me
m
o
r
y
Size
Search
Speed
Keyword Sear
ch
Nu
m
e
ric
Opera
tion
Ele
m
ent
Slow
Large
High
Low
Colu
m
n
/Row M
e
diu
m
M
e
diu
m
M
e
diu
m
M
e
diu
m
Tab
l
e
Fast
S
m
all
Lo
w
Lo
w
The el
em
ent
b
a
sed e
n
cry
p
t
i
o
n m
e
t
hod i
s
us
eful
o
n
l
y
fo
r t
h
e searc
h
fo
r t
h
e sam
e
val
u
ed
dat
a
,
but
i
t
i
s
not
g
o
od f
o
r t
h
e num
eri
c
oper
a
t
i
ons. It
al
wa
y
s
needs t
o
d
o
t
h
e el
em
ent
l
e
vel
decry
p
t
i
o
n b
e
fo
re d
o
i
n
g n
u
m
eri
c
ope
ration. For exam
ple,
there
is
o
n
e
pl
ai
n t
e
xt
t
a
bl
e s
u
ch
a
s
,
,
,
..,
.
In this case
,
we store a
n
en
cry
p
ted
relatio
n
,
,
,
..,
where eac
h attribute
corresponds
to t
h
e encry
p
ted
da
ta for eac
h
attrib
u
t
e
.
Fi
gu
re
1.
The
e
l
em
ent
based
e
n
cry
p
t
i
o
n
m
e
t
h
od
Tabl
e
2. T
h
e
o
r
i
g
i
n
al
q
u
ery
a
n
d
t
h
e m
odi
fi
e
d
que
ry
T
h
e or
iginal plain-text quer
y
T
h
e tr
ansform
e
d q
u
er
y
SELEC
T n
a
m
e
FROM
std_info
WH
ERE ci
ty
= se
o
u
l
SELEC
T n
a
m
e
FROM
std_info(
E
)
WH
ERE ci
ty
= se
o
u
l
(E)
In Fi
g
u
r
e1
, a query
ge
nerat
e
d
by
a dat
a
base user i
s
t
r
ans
f
or
m
e
d t
o
t
h
e
m
odi
fi
ed
que
ry
w
h
i
c
h co
ul
d
search t
h
e exa
c
t
dat
a
from
the enc
r
y
p
t
e
d
d
a
t
a
base. I
n
Ta
bl
e 2, i
f
t
h
e st
d_i
nf
o t
a
bl
e i
s
t
h
e st
ude
nt
pe
rso
n
al
i
n
f
o
rm
at
i
on, st
d_i
nf
o(
E) i
s
t
h
e e
n
cry
p
t
e
d
dat
a
base
w
h
i
c
h c
ont
ai
ns
t
h
e
encry
p
t
e
d el
e
m
ent
s
i
n
t
h
e s
t
d_i
n
f
o
tab
l
e. Th
e “seou
l
(E)” is th
e encryp
ted fo
rm
of th
e seou
l
The c
o
l
u
m
n
/
r
o
w
base
d e
n
cry
p
t
i
o
n
m
e
t
hod i
s
t
h
e m
e
t
hod
whi
c
h e
n
cry
p
t
s
t
h
e
dat
a
by
t
h
e
uni
t
of
t
h
e
co
lu
m
n
o
r
ro
w. Typ
i
cally
,
t
h
e row
based e
n
cry
p
t
i
on m
e
tho
d
w
h
i
c
h i
s
al
so cal
l
e
d by
tupl
e base
d enc
r
y
p
t
i
o
n
m
e
t
hod,
i
s
gen
e
ral
l
y
used
.
Fo
r each
relatio
n
,
,
,
..,
,
w
e
s
t
o
r
e on
th
e s
e
r
v
er
an
en
c
r
yp
te
d
r
e
la
tio
n
,
,
,
,
..,
whe
r
e the
etuple
stores an
e
n
cry
p
ted stri
ng that c
o
rrespo
nd
s t
o
a tup
l
e in
relation
R.
Each attribute
co
rre
sp
o
nds
t
o
t
h
e
b
u
c
k
et
i
n
dex
fo
r t
h
e
at
t
r
i
but
e
t
h
at will
b
e
u
s
ed
fo
r
query p
r
o
cessing
at the
serve
r
. In t
h
is
case
we
have
t
o
m
a
p
t
h
e do
m
a
in
of v
a
lu
es
of attri
b
u
t
e
.
in
to
p
a
rtitio
n
,
,
,.
.
,
su
ch
th
at th
ese p
a
rtitio
n
s
tak
e
n
tog
e
th
er co
v
e
r th
e who
l
e d
o
m
ain
;
an
d
an
y two
p
a
rtitio
n
s
do
no
t o
v
e
rlap.
Form
ally
, we
defi
ne a
fu
nction
p
a
rtitio
n
as fo
llows;
.
,
,
,.
.
,
. We will
call k
t
h
e
n
u
m
b
er of
t
h
e
b
u
c
k
et
. Thi
s
m
e
t
hod
i
s
p
r
op
ose
d
by
Ho
r
e
[
2
]
an
d k
n
o
w
n
t
o
be
a ge
ner
a
l
l
y
go
od
m
e
t
h
od
t
o
pr
ot
ect
t
h
e
dat
a
base t
h
ese
da
y
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISS
N
:
2088-8708
A comparis
on
of the
query ex
ecution al
gorithms
in secure dat
abase
syste
m
(Ji-
Ho
ng
Kim
)
33
9
Fi
gu
re
2.
The
t
y
pi
cal
t
upl
e e
n
cry
p
t
i
o
n m
e
t
hod
Tabl
e
3. T
h
e
o
r
i
g
i
n
al
q
u
ery
a
n
d
t
h
e m
odi
fi
e
d
que
ry
T
h
e or
iginal plain-text quer
y
T
h
e tr
ansform
e
d q
u
er
y
SELEC
T n
a
m
e
FROM
std_info
WH
ERE ag
e
= 3
0
SELEC
T etu
p
l
e
FROM
std_info(
E
)
WH
ERE (ag
e
)
bi
=
age (30)
bi
In Figure
2, B
I
m
eans the B
u
cket
Inde
x
us
ed
fo
r
que
ry
c
o
n
v
e
r
si
o
n
pr
oc
ess an
d
ED
m
eans et
upl
e
decry
p
tion process.
A query ori
g
inated
fr
o
m
a user i
s
t
r
a
n
sf
orm
e
d t
o
t
h
e
m
odi
fi
ed
q
u
e
ry
i
n
o
r
der t
o
searc
h
t
h
e exact
dat
a
fr
om
t
h
e encry
p
t
e
d
dat
a
base.
The m
e
t
a
dat
a
st
ore t
h
e
buc
ket
i
nde
x
o
f
t
h
e
e
ach at
t
r
i
b
ut
e.
S
o
, t
h
e
v
a
lu
e
o
f
th
e att
r
ibu
t
e in
vo
lv
ed in
th
e u
s
er query is co
nv
erted
to
th
e
b
u
ck
et
in
d
e
x
.
Th
en
the b
u
c
k
e
t ind
e
x v
a
lu
e
is in
serted in
to th
e m
o
d
i
fied
q
u
e
ry wh
ich co
u
l
d
search
the
exact
data from
the tuple e
n
crypted
data
ba
se. T
h
e
q
u
e
ry resu
lt retu
rn
ed
fro
m
th
e serv
er is th
e
en
cry
p
ted
stri
ng
etuple.
The c
l
i
e
nt
m
odul
e s
h
o
u
l
d
decry
p
t
et
upl
e
an
d ex
t
r
act th
e
righ
t resu
lt from
th
e d
e
cryp
ted
d
a
ta.
In Tab
l
e 3, the std_
in
fo tab
l
e co
nt
ai
ns t
h
e
pl
ai
nt
ext
fo
rm
o
f
t
h
e
st
u
d
e
n
t
pe
rso
n
al
i
n
f
o
r
m
at
i
on a
n
d
t
h
est
d
_i
nf
o
(
E)
i
s
t
h
e e
n
cry
p
t
e
d
dat
a
base
w
h
i
c
h c
ont
ai
n
s
t
h
e
enc
r
y
p
t
e
d
st
ri
ng
o
f
eac
h t
upl
e. T
h
e
is th
e
buc
ket inde
x
value of t
h
e a
g
e
ele
m
ent.
Fi
nal
l
y
, t
a
bl
e based enc
r
y
p
t
i
o
n m
e
t
hod
, i
s
us
ed t
o
m
a
ke t
h
e back
up
dat
a
i
n
orde
r t
o
st
o
r
e dat
a
on t
h
e
ori
g
i
n
al
dat
a
ba
se peri
odi
cal
l
y
. The
r
ef
ore
,
t
h
i
s
m
e
t
hod i
s
n
o
t
g
o
o
d
f
o
r
q
u
ery
p
r
ocessi
n
g
o
n
t
h
e e
n
cr
y
p
t
e
d
dat
a
base
.
3.
THE PROPOSED
D
A
T
A
B
A
S
E EN
CRYPTION MODEL
Ev
en
if so
m
e
sen
s
itiv
e data ex
ists in
th
e
datab
a
se, th
ere
is still a lo
t o
f
in
sen
s
itiv
e data in
th
e
database
. S
o
we propose
d the
selec
tive tuple encryption m
e
thod with B
l
oom
Filter. A Bloom
Filter
[3] is a
si
m
p
le space-efficient
randomized data st
ructure used
to represen
t the existence
of the da
ta. The filter is a bi
t
array
ove
r
whi
c
h m
e
m
b
ershi
p
que
ri
es are
c
o
n
d
u
ct
ed t
o
di
st
i
n
g
u
i
s
h
bet
w
een m
e
m
b
ers o
f
t
h
e
gi
ve
n set
or
n
o
t
.
Hash
function techniques a
r
e
used
to
bot
h save space a
nd
allow m
e
m
b
er
lookup. Bloom Filters allow false
positives
but the space savi
ngs often
ou
twe
i
gh this
dra
w
back whe
n
the
prob
ability of
an error is controlled.
Th
e Bloo
m
Fi
lter is an
array o
f
m
b
its, in
itially al
l set
to
0. The Blo
o
m
Filter u
s
es k
ind
e
p
e
nd
en
t h
a
sh
functions
with range m
.
The
num
b
er of the sam
p
le sp
ace is n elem
ents. After i
n
serti
n
g n
elem
ents
with
k
h
a
sh
fu
n
c
tion
s
in
th
e m
b
its
Blo
o
m
Fil
t
er, th
e p
r
ob
ab
ility o
f
th
e false
p
o
s
itiv
e erro
r
[3
] is
f
1
1
1mk
n
k
≈
1
−
e
−
knm
k
. Th
is false po
sitiv
e rate co
u
l
d
b
e
redu
ced
b
y
cho
o
s
i
n
g
th
e larg
e nu
m
b
er o
f
m
in
p
r
op
or
tio
n to
t
h
e nu
m
b
er
of
i
n
pu
t elem
en
t n
.
In
Figur
e 3,
Th
e BF m
ean
s th
e qu
er
y conv
er
si
o
n
pr
o
c
ess u
s
ing
B
l
oom
Fi
lt
er val
u
e a
nd E
D
m
eans t
h
e selective etuple de
cryption proce
ss.
The m
e
tadata store the bucket
i
nde
x
of
t
h
e ea
ch at
t
r
i
b
ut
e.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 1, Feb
r
uar
y
20
1
6
:
33
7 – 34
3
34
0
Fig
u
re
3
.
Selectiv
e tu
p
l
e en
cryp
tio
n
with
Bl
o
o
m
Filter m
e
t
h
od
We
p
r
op
o
s
e two k
i
n
d
s
of en
cry
p
tio
n m
e
t
h
od
s
fo
r
t
h
e sen
s
itiv
e
d
a
ta
o
n
l
y.
Th
e first
typ
e
is the
characte
r
istic data involve
d in each attribute.
The keyw
ord
for the searc
h
process
is extracted from
the each
characte
r
istic attribute. T
h
e ci
ty na
m
e
“seoul
” is one
e
x
am
ple as a keyword. T
h
e e
x
tracte
d
key
w
ord is hashe
d
an
d th
e
resu
ltin
g v
a
l
u
e
o
f
t
h
e h
a
sh
fun
c
tion
is co
nsid
ered
a b
it nu
m
b
er and
th
e correspon
d
i
n
g
b
its are
set b
y
one i
n
the Bloom
Filter, BF=Hash(se
oul
). T
h
e second type
is th
e n
u
m
erical d
a
ta in
vo
lv
ed
in
each
attrib
u
t
e.
The n
u
m
e
ri
cal dat
a
i
s
conve
rt
ed t
o
t
h
e b
u
c
ket
i
nde
x w
h
i
c
h i
s
st
ored i
n
t
h
e m
e
t
a
dat
a
. The g
r
ade i
s
one
exam
ple as a
num
erical data
. T
h
e
value
of the
grade
w
ou
l
d
b
e
di
vi
de
d
by
t
h
e
l
a
r
g
e
n
u
m
b
er o
f
t
h
e
buc
ket
s
because the
bucket inde
x
value is not discl
o
se
d, and
only
involve
d
in the Bloom
Filter
using ha
sh
functions.
So
, th
e nu
m
e
rical attrib
u
t
e i
n
v
o
l
v
e
d in th
e
u
s
er qu
ery is
co
nv
er
te
d
to
th
e bu
ck
e
t
ind
e
x
f
i
r
s
t,
th
e
n
th
e
b
u
c
k
e
t
inde
x value is
converted to t
h
e corr
es
ponding
bits of the Bloom
Filter,
according to the res
u
lt of the hash
fu
nct
i
o
ns.
A que
r
y originated from
a us
er is
transform
e
d to t
h
e m
odified query i
n
order t
o
search t
h
e e
x
act data
from
the encrypted
database
.
W
e
call this
m
e
thod
SE
BF
(Selective T
u
ple Enc
r
yp
tion with Bloom
Filter).
Tab
l
e4 show
s
th
e qu
er
y conv
er
si
o
n
pro
cess in
SEBF.
Th
e ge
nerat
i
o
n
p
r
oces
s
of t
h
e e
n
cry
p
t
e
d
dat
a
b
a
se i
n
SEB
F
i
s
s
h
ow
n i
n
Fi
g
u
r
e
4.
Tabl
e
4. T
h
e
q
u
ery
use
d
i
n
S
E
B
F
m
e
t
hod
T
h
e or
iginal plain-text quer
y
T
h
e tr
ansform
e
d q
u
er
y
SELEC
T n
a
m
e
FROM
std_info
WH
ERE ci
ty
= se
o
u
l
SELEC
T s-
etu
p
l
e
FROM
std_info(
E
)
W
H
E
R
E
BF =Has
h(
seoul)
Fi
gu
re
4.
The
s
t
ruct
u
r
e
of
t
h
e
SEB
F
m
e
t
hod
4.
D
I
SC
USSION AN
D CONCLSIONS
In this cha
p
te
r, we will com
p
are the propos
e
d
enc
r
yption m
e
thod
with the othe
r encry
p
tion
m
e
t
hods
.The
F
i
rst
encry
p
t
i
o
n
m
e
t
hod i
s
t
h
e
Tu
pl
e Enc
r
y
p
t
i
on
wi
t
h
B
u
c
k
et
I
nde
xi
n
g
m
e
t
hod.
W
e
c
a
l
l
t
h
i
s
m
e
t
hod a
s
TE
B
I
. T
h
i
s
m
e
t
hod
i
s
pr
op
ose
d
by
Ho
re
[2
,
5
,
6]
a
n
d t
h
e
sa
m
e
t
o
t
h
e t
y
pi
cal
t
upl
e e
n
cry
p
t
i
o
n
m
e
t
hod.
I
n
Fi
g
u
re
5,
y
o
u
ca
n s
ee t
h
at
i
t
o
n
l
y
uses t
h
e
buc
ke
t
i
nde
x
rega
r
d
l
e
ss o
f
t
h
e at
t
r
i
but
e
dat
a
t
y
pe
.
Al
l
o
f
the tuple elements are enc
r
y
p
ted by th
e e
-
t
upl
e (e
nc
ry
pt
e
d
t
upl
e
)
an
d ea
ch at
t
r
i
but
e
of
t
h
e t
upl
e i
s
co
nve
rt
ed
by
b
u
ck
et
i
nde
x. T
h
e
r
ef
ore
,
we ca
n searc
h
t
h
e dat
a
usi
n
g
t
h
e b
u
c
k
et
i
n
d
e
x w
h
i
c
h i
s
st
ore
d
i
n
t
h
e m
e
t
a
dat
a
.
The e-tuple da
ta is extracted
from
th
e database according to the buc
ket inde
x. If we
wa
nt to search the city
n
a
m
e
“seo
u
l
”,
th
en
we
first co
nv
ert th
e city n
a
m
e
to
th
e acco
rd
ing
bu
ck
et
in
d
e
x
u
s
ing
t
h
e m
e
tad
a
ta in
a clien
t
m
odul
e. T
h
e m
odi
fi
ed
q
u
ery
i
s
sent
t
o
t
h
e
da
t
a
base ser
v
e
r
, a
n
d
q
u
ery
res
u
l
t
s
, w
h
i
c
h
are t
h
e e-t
u
pl
es acc
o
r
di
ng
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISS
N
:
2088-8708
A comparis
on
of the
query ex
ecution al
gorithms
in secure dat
abase
syste
m
(Ji-
Ho
ng
Kim
)
34
1
to the bucket inde
x, a
r
e returned
fr
om
t
h
e serve
r
. T
h
e cl
i
e
nt
sh
oul
d dec
r
y
p
t
t
h
e cor
r
esp
o
n
d
i
n
g e-t
upl
e
s
an
d
coul
d
get
t
h
e e
x
act
dat
a
.
Th
e
fat
a
l
dra
w
back
of
t
h
i
s
m
e
t
hod i
s
t
h
e
ex
p
o
su
re o
f
t
h
e b
u
c
k
e
t
i
nde
x
val
u
e
o
f
t
h
e
attribute. T
h
e
attacker ca
n
guess t
h
e
di
st
ri
b
u
t
i
o
n
o
f
t
h
e
da
t
a
fr
om
t
h
e en
cry
p
t
e
d
dat
a
ba
se by
t
h
e
val
u
e
of
t
h
e
buc
ket
i
n
de
x.
Fi
gu
re
5.
The
s
t
ruct
u
r
e
of
t
h
e
TEB
I m
e
t
hod
Anothe
r m
e
thod is t
h
e T
upl
e Enc
r
yption
with Bl
oom
F
ilter
m
e
thod [4,
7].
W
e
call this m
e
thod
TEBF. In
Figure 6
,
you
can
see th
at it
u
s
es th
e Blo
o
m
Filte
r with
th
e e-tup
l
e. In
th
is
m
e
t
h
od
, th
e
b
u
c
k
e
t in
d
e
x
is
rep
l
aced
b
y
th
e
Bloo
m
Filt
er. After
each
attrib
u
t
e o
f
the
tuple is
conve
r
ted t
o
a
bucket inde
x, the
bucket
inde
x
value is conve
rted t
o
t
h
e c
o
rr
espondi
ng bits
of t
h
e
Bloom
Filter
according to the result of the
hash
fu
nct
i
o
ns. A q
u
ery
ori
g
i
n
at
e
d
f
r
om
a
user
i
s
t
r
ans
f
o
r
m
e
d
to
th
e m
o
d
i
fied
qu
ery in
o
r
der to
search
the ex
act
dat
a
f
r
om
t
h
e e
n
cry
p
t
e
d
dat
a
b
a
se.
Fi
gu
re
6.
The
s
t
ruct
u
r
e
of
t
h
e
TEB
F m
e
t
hod
Thi
s
m
e
t
hod i
s
m
o
re secure t
h
an t
h
e T
E
B
I
m
e
t
hod p
r
e
v
i
o
usl
y
m
e
nt
i
one
d, b
u
t
al
l
t
h
e el
em
ent
s
are
en
cry
p
ted
reg
a
rd
less of t
h
e sen
s
itiv
ity o
f
the d
a
ta. Even
if we
wan
t
to search th
e
on
e
or two
attri
b
u
t
es,
we
have
t
o
dec
r
y
p
t
al
l
of t
h
e acc
or
di
n
g
e
-
t
u
pl
es
. N
o
w,
we c
o
m
p
are the search
perform
a
nce betwee
n t
h
e
plain-
t
e
xt
an
d t
h
e t
h
r
ee enc
r
y
p
t
i
o
n
m
e
t
hods
(T
EB
I, T
E
B
F
,
SEB
F
).
The
SEB
F
i
s
t
h
e
pr
o
pose
d
m
e
t
hod i
n
t
h
i
s
pa
per
.
In
o
r
de
r t
o
c
o
m
p
are t
h
ree
d
a
t
a
base e
n
cry
p
t
i
on m
e
t
hods
,
TEB
I a
n
d TE
B
F
use
t
h
e
b
u
c
ket
i
n
de
x
rat
h
er
t
h
a
n
key
w
or
d sea
r
c
e
h.
Onl
y
SEB
F
uses t
h
e key
w
or
d f
o
r sear
ch
i
ng t
h
e c
h
aracte
r
type
data and the buc
k
et index for
searchi
ng
the
num
e
rical type data
and
the
num
b
er of the bucket
used
in
SEBF is ab
ou
t fiv
e
ti
m
e
s as
man
y
as
TEBI an
d TEBF m
e
th
o
d
s.
It m
ean
s th
at we d
i
v
i
d
e
th
e num
erical attrib
utes in
to
m
o
re
p
a
rtitio
n
s
in
SEBF. In
or
der t
o
c
h
ec
k t
h
e sea
r
c
h
per
f
o
r
m
a
nce o
f
t
h
e t
h
r
ee encryp
tion
m
e
th
o
d
s
,
we u
s
e th
e fo
llowing
tab
l
es.
st
d_i
nf
o(st
d_i
d
,
nam
e
, ssn1,
ssn
2,ci
t
y
, bt
, h
e
i
ght
, wei
ght
),
st
d_
gra
d
e(st
d
_
i
d
,
gra
d
e,
d_i
d, ave
r
a
g
e, e-
gra
d
e,
advise
r) In
TE
BI,
st
d_
inf
o
and
st
d_
gr
ade
are c
o
m
posed of t
h
e
e-tuple and
buck
et index of e
ach attribute.
In
TEBF,
st
d_inf
o
and
st
d_gr
ade
are co
m
p
o
s
ed
o
f
t
h
e e-tup
l
e and
Blo
o
m
Filter valu
e wh
ich is co
m
p
o
s
ed wit
h
the res
u
lt of t
h
e has
h
functions
us
i
ng buc
k
et
inde
x of each
attribute.
In SEB
F
, St
d_grade ta
ble is not
encry
p
t
e
d a
nd
som
e
at
t
r
i
but
es (st
d
_i
d,
nam
e
, ssn
1 an
d ss
n
2
)
i
n
t
h
e St
d_i
nf
ot
abl
eare e
n
c
r
y
p
t
e
d. Ta
bl
e 5
sho
w
s
the two
que
rie
s
used
for pe
rform
a
nce analysis
.
Tabl
e 6 s
h
o
w
s t
h
e
resul
t
of t
h
e pe
rf
or
m
a
nce t
e
st
. Tabl
e 7
shows
the
pe
rform
a
nce com
p
arison
of
each encry
p
tion
m
e
thod.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
6, No
. 1, Feb
r
uar
y
20
1
6
:
33
7 – 34
3
34
2
Tabl
e 5.
T
w
o q
u
ei
es used
for perform
a
nce
analysis
Query1
Query2
SELEC
T count(*)
FROM
std_info,
std_gar
d
e
W
H
ERE (e-grade
>750)AND
(city =jecheon)
SELEC
T count(*)
FROM
std_info,
std_gar
d
e
W
H
E
R
E
(
d
-
i
d=electr
onics)
AND
(
g
r
a
de >average(
g
rade)
)
Tab
l
e
6
.
Th
e resu
lt of th
e
search perform
a
nce
test
Return
No
(Q1
)
Search
Ti
m
e
(Q1
)
Return No
(Q2
)
Search
Ti
m
e
(Q2
)
Plaintext
764
0.
0450
026
2565
0.
1170
67
T
E
B
I 7388
0.
2150
123
1998
1
0.
4550
263
T
E
B
F 7436
0.
2480
136
2199
6
0.
6182
54
SE
BF 807
0.
0650
031
1001
8
0.
3101
77
Table
7. T
h
e
c
o
m
p
arison bet
w
een three m
e
thods
E
n
cr
y
p
tion
Unit
I
ndex Key
w
or
d
Search
Nu
m
e
ric
a
l
Operation
Security Co
mm
ent
T
E
B
I
T
uple
BI
L
o
w
M
e
diu
m
L
o
w
Disclose the distr
i
bution o
f
the data.
T
E
B
F
T
uple
BI
,
BF
M
e
diu
m
M
e
diu
m
High
High speed only
if we use lar
g
e
nu
m
b
er of bucket index.
SEBF
Selective tuple
BI, BF
High
High
Mediu
m
Only
sensitive data
should be
encrypted
We ca
n see
tha
t
the SEBF m
e
thod
has t
h
e
be
st sear
ch
p
e
rform
a
n
ce. Bu
t it
is a v
e
ry d
i
fficu
lt prob
lem
to
d
eci
d
e
h
o
w
m
u
ch
d
a
ta wou
l
d
b
e
en
cry
p
ted
acco
r
d
i
ng
t
o
th
e sensitiv
ity. In fact, t
h
e
search p
e
rforman
ce is
di
ffe
re
nt
de
pe
n
d
i
n
g
o
n
t
h
e
q
u
e
ri
es t
y
pes
we
cho
o
se
.I
f
we
u
s
e cha
r
act
er
t
y
pe ci
phe
r-t
e
x
t
as a sea
r
c
h
c
o
n
d
i
t
i
on,
SEB
F
ha
s bet
t
er pe
rf
orm
a
nce t
h
an
ot
he
r
m
e
t
hods
bec
a
use i
t
use
s
k
e
y
w
o
r
d se
arc
h
. I
n
t
h
e cas
e
of t
h
e
agg
r
e
g
at
i
on
o
p
e
rat
i
o
n
,
SEB
F
has bet
t
e
r
per
f
o
rm
ance t
h
an
ot
he
r m
e
t
hods
onl
y
i
f
i
t
uses
t
h
e l
a
rge
num
bers o
f
the buc
k
et inde
x.
ACKNOWLE
DGE
M
ENTS
Thi
s
pape
r
was
su
pp
o
r
t
e
d
by
t
h
e Sem
y
ung
U
n
i
v
e
r
si
t
y
R
e
search
G
r
ant
o
f
20
15
.
REFERE
NC
ES
[1]
S.
Vime
rc
a
t
i,
a
n
d S.
Fore
sti,
"
P
r
ivacy of Outs
o
u
r
ced Data
", Auerbach Publications (Tay
lor an
d Francis Group),
320: 174-187.
[2]
B. Hore, S. Meh
r
otra,
and H. Hacig
ὓ
.m
ὓ
.s
, “
Managing and Querying Encrypted d
a
ta
”, Handbook
of Data Security,
pp 163-190, 200
8.
[3]
A. Broder
and
M. Mit
zenm
a
c
h
er. Ne
twork a
pplic
ations of
Bloom
Filters:
A surve
y
.
Inter
n
et Ma
thematics
,
1(4):pp.485-509
, 2004.
[4]
J.
Ki
m,
T
.
Sa
ha
ma
,
S.
Ki
m,
"A
Pe
rforma
n
c
e
t
e
st of Quer
y
Operation on Encr
y
p
ted Database",
LN
CS 235
, pp 801-
810, 2013
[5]
B. Hore, S. Mehrotra, G.
Tsudik, “
A privacy-
p
r
eserving index
for range queries
”, Proceedings
of the Thir
tieth
intern
ation
a
l
con
f
erence on
Ver
y
large databases-
Volume30. VLD
B
’04, VLDB Endowment pp 72
0–731, 2004
.
[6]
H.
Hacig
ὓ
.m
ὓ
.s
, B. I
y
e
r
, C
.
L
i
,
and S
.
M
e
hrot
r
a
, "
Executing
S
Q
L over encryp
ted data
in
the
database service
provider model
"
,
In Proc. of
theA
CM SIGMOD, pp. 45-49
, 2002
[7]
D. S
h
in, T
.
S
h
aham
a, J
.
Kim
and J
.
Kim
,
“
T
he S
cal
abil
it
y a
nd the S
t
ra
teg
y
for EM
R Data
bas
e
Encr
yp
tio
n
Techn
i
ques
”
,
JI
CCE
, pp
. 556-58
2, 2011
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
A comparis
on
of the
query ex
ecution al
gorithms
in secure dat
abase
syste
m
(Ji-
Ho
ng
Kim
)
34
3
BIOGRAP
HI
ES OF
AUTH
ORS
Young-Dal Jang (jang_
y
d
@naver.com) receiv
e
d
his B.S an
d M.S degrees
in electronic
engineering
fro
m Semy
ung
University
, Jech
eon, Korea in 1998
and 2008.
H
e
is
curren
t
l
y
i
n
his
P
h
.D
cours
e
in inform
ation
and telecommunication in Sem
y
u
ng University
,
J
echeon,
Korea
.
His
current
res
e
a
r
ch in
ters
ets
inc
l
ude th
e n
e
towrk
s
ecurit
y
a
nd d
a
ta
bas
e
s
ecu
rit
y
.
Ji-Hong Kim (jhkim@
semy
ung
.ac.kr)
r
e
ceived
his B.S degree in electron
ic
eng
i
neer
ing from
Han
y
ang Univer
sity
, Seoul, Korea in 1982. and r
e
cei
v
e
d his M.S and Ph.D degrees
in electron
ic
and communication eng
i
neer
ing
from Han
y
ang
U
n
iversity
, Seoul,
Korea in
1984
and 1996.
He has worked
in th
e Dep
a
rtment of th
e
in
f
o
rmation and
telecommunication in Sem
y
ung
University
sin
c
e
1991.
His
current
res
e
arch
inters
e
t
s
in
clude
the
netow
r
k s
ecuri
t
y
and
datab
a
s
e
s
e
curi
t
y
and
cloud
computing.
Evaluation Warning : The document was created with Spire.PDF for Python.