Indonesian
J
our
nal
of
Electrical
Engineering
and
Computer
Science
V
ol.
16,
No.
2,
No
v
ember
2019,
pp.
1065
1069
ISSN:
2502-4752,
DOI:
10.11591/ijeecs.v16i2.pp1065-1069
r
1065
Pri
v
acy
pr
eser
ving
outsour
cing
algorithm
f
or
tw
o-point
linear
boundary
v
alue
pr
oblems
Nedal
M.
Mohammed
1
,
Laman
R.
Sultan
2
,
Santosh
S.
Lomte
3
1,3
Department
of
Computer
Science
,
Dr
.
Babasaheb
Ambedkar
Marathw
ada
Uni
v
ersity
,
Aurang
abad,
India
2
Department
of
Po
wer
Mechanics,
Basra
T
echnical
Institute,
Southern
T
echnical
Uni
v
ersity
,
Al-Basrah,
Iraq
Article
Inf
o
Article
history:
Recei
v
ed
Jan
25,
2019
Re
vised
Apr
15,
2019
Accepted
May
3,
2019
K
eyw
ords:
Cloud
computing
Secure
computation
outsourcing
V
erifiable
computing
Secure
and
pri
v
ac
y
BVP
.
ABSTRA
CT
One
of
a
po
werful
application
in
the
age
of
cloud
computing
is
the
outsourcing
of
sci-
entific
computations
to
cloud
computing
which
mak
es
cloud
computing
a
v
ery
po
w-
erful
computing
paradigm,
where
the
customers
with
limited
computing
resource
and
storage
de
vices
can
outsource
the
sophisticated
computation
w
orkloads
into
po
wer
-
ful
service
pro
viders.
One
of
scientific
computat
ions
problem
is
T
w
o-Point
Boundary
V
alue
Problems
(BVP)
is
a
basic
engineering
and
scientific
problem,
which
has
appli-
cation
in
v
arious
domains.
In
this
paper
,
we
propose
a
pri
v
ac
y-preserving,
v
erifiable
and
ef
ficient
algorithm
for
tw
o-point
BVP
in
outsourcing
paradigm.
W
e
implement
the
proposed
schema
on
the
customer
side
laptop
and
using
A
WS
compute
domain
elastic
compute
cloud
(EC2)
for
the
cloud
side.
Copyright
c
2019
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Nedal
M.
Mohammed,
Department
of
Computer
Science,
T
aiz
Uni
v
ersity
,
T
aiz,
Y
emen.
Email:
dr
.nedal.mohammed@gmail.com
1.
INTR
ODUCTION
The
po
werful
adv
antages
of
cloud
computing
is
called
outsourcing,
where
the
customers
with
li
mited
computing
resource
and
storage
de
vices
can
outsource
the
sophisticated
comput
ation
w
orkloads
i
nto
po
werful
service
pro
viders.
Despite
the
tremendous
benefits,
there
are
man
y
challenges
and
security
concerns
because
the
cloud
serv
er
and
customer
are
not
in
the
same
trusted
domain,
to
a
v
oid
these
problems
[1,
2,
3,
10].
First,
to
combat
the
security
c
o
nc
ern
is
applying
encryption
techniques
to
customer’
s
sensiti
v
e
information
before
outsourcing
to
the
cloud
b
ut
still,
there
is
a
challenge
ho
w
mak
es
the
task
of
computation
o
v
er
encrypted
data
[2,
4,
8].
Second,
no
guarantee
from
the
cloud
on
the
quality
of
the
computed
data
and
results.
F
ocusing
on
scientific
and
engineering
applications
problems
we
notice
that
the
dif
ferential
equati
ons
problems
(Boundary
v
alue
problems
and
initial
v
alue
problems).
The
BVP
&
IVP
frequently
appear
in
v
arious
fields
and
has
a
number
of
applications,
b
ut
solving
these
lar
ge-scale
BVP
&
IVP
problems
i
s
usually
computa
tionally
so
e
xpensi
v
e
[5,
7,
9,
11].
The
computers
with
limited
computing
resource
and
storage
de
vices
are
f
acing
the
challenge
of
solving
lar
ge-scale
BVP
&
IVP
.
T
o
address
this
challenge
(solving
lar
ge-scale
BVP
&
IVP),
an
alternati
v
e
option
is
outsourcing
to
cloud
computing.
This
w
ork,
focusing
on
secure
outsourcing
BVP
.
W
e
are
proposing
secure,
ef
ficient
and
v
erifiable
scheme
to
of
fload
lar
ge-scale
BVP
computation
to
cloud
side.
This
paper
is
or
g
anized
as
follo
ws
Section
2.
describes
our
proposed
system
model
t
o
secure
outsourcing
the
BVP
problem.
In
Section
3.
outsourcing
algorithm
of
tw
o-point
BVP
.
In
Section
4.
security
analysis
of
proposed
algorithm.
In
Section
5.
we
pro
vide
e
xperimental
result
analysis
for
proposed
schema.
At
last
the
w
ork
conclusion
is
presented
in
section
6.
J
ournal
homepage:
http://iaescor
e
.com/journals/inde
x.php/ijeecs
Evaluation Warning : The document was created with Spire.PDF for Python.
1066
r
ISSN:
2502-4752
2.
SYSTEM
MODEL
W
e
consider
an
asymmetric
architecture
in
v
olv
ed
tw
o
parties.
On
the
first
side,
there
is
a
resource-
constrained
customer
who
has
the
BVP
problem
to
solv
e
Ho
we
v
er
,
due
to
limited
computing
resources
the
customer
cannot
do
this
computation
to
solv
e
the
problem
locally
.
On
second
side,
(
S
)
cloud
with
computa-
tionally
po
werful
de
vices
and
huge
storage
f
acilities,
b
ut
cannot
be
trusted
with
the
sensiti
v
e
information.
Then
to
a
v
oid
security
problems
the
procedure
goes
as
sho
wn
in
Figure
1.
Figure
1.
System
model
of
secure
outsourcing
of
BVP
problem.
W
e
c
on
s
ider
the
procedure
is
go
wing
as
follo
w
the
customer
C
outsource
an
BVP
computation
task
:
D
!
M
to
a
cloud
serv
er
S.
Ho
we
v
er
,
S
is
not
fully
trusted
by
C
either
semi-honest
or
malicious.
So
to
protect
the
input
pri
v
ac
y
,
the
C
transfers
the
original
BVP
to
linear
system
equation
(LSE)
then
encrypts
into
an
encrypted
k
with
a
secret
K
e
y
K
then.
Then
k
is
outscrced
from
the
C
to
the
S.
The
S
runs
optimization
algorithm
to
solv
e
k
when
recei
ving
the
encrypted
BVP
problem
k
.
After
getting
the
result,
the
C
v
erifies
whether
the
solution
returned
is
correct
or
not
in
encryption
domain.
If
the
result
can
not
pass
through
v
erification,
C
requires
the
cloud
to
compute
it
ag
ain.
Otherwise,
the
customer
decrypting
the
correct
result
to
get
the
solution
to
the
BVP
.
3.
OUTSOURCING
ALGORITHM
OF
TW
O-POINT
BOUND
AR
Y
V
ALUE
PR
OBLEMS
In
this
section,
we
propose
algorithm
for
securely
outsourcing
lar
ge-scale
system
of
finite
dif
ference
method
to
find
the
solution
of
linear
boundary
v
alue
problems.
T
o
achie
v
e
goals
of
our
w
ork,
we
design
the
follo
wing
sub-algorithms.
3.1.
Using
Finite
Differ
ence
Method
T
w
o-Point
linear
boundary
v
alue
problems
formulated
as[6,
5,
9]:
u
00
=
p
(
t
)
u
0
+
q
(
t
)
u
+
r
(
t
)
;
t
2
[
a;
b
]
;
u
(
a
)
=
;
u
(
b
)
=
:
(1)
The
problem
for
securely
outsourcing
lar
ge-scale
Linear
BVP
with
Finite
Dif
ferences
can
be
for
-
mulated
as
follo
ws:
The
client
C
seeks
for
the
solution
to
a
lar
ge-scale
Linear
Boundary
V
alue
Problems
A
h
y
h
=
b
h
,
where
A
h
2
R
N
N
is
gi
v
en
matrix
in
the
form
[8,
9]
A
h
=
0
B
B
B
B
@
2
1
0
:
:
:
0
0
0
0
1
2
1
:
:
:
0
0
0
0
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
0
0
0
:
:
:
0
1
2
1
0
0
0
:
:
:
0
2
1
0
1
C
C
C
C
A
and
b
h
2
R
N
is
a
v
ector
of
the
form
Indonesian
J
Elec
Eng
&
Comp
Sci,
V
ol.
16,
No.
2,
No
v
ember
2019
:
1065
–
1069
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
r
1067
b
h
=
0
B
B
@
r
(
t
1
)
+
h
2
r
(
t
i
)
;
i
=
2
;
3
;
:
:
:
;
N
1
r
(
t
N
)
+
h
2
1
C
C
A
3.2.
K
ey
Generation
Algorithm.
In
k
e
y
generation
algorit
hm,
client
firstly
picks
a
random
disguising
coef
ficient
v
ector
r
2
R
n
and
M
;
N
2
R
n
n
;
tw
o
random
sparse
matrices
as
belo
w
.
M
(
i
;
f
)
=
m
i
m
(
i
)
f
1
i
;
f
m
;
(2)
N
(
i
;
f
)
=
n
i
n
(
i
)
f
1
i
;
f
n
;
r
(
i
)
=
r
i
1
i
n:
Here
m
i
;
n
i
;
r
i
are
all
randomly
generated
from
the
space
and
m
;
n
are
tw
o
dif
ferent
bijection
functions.
These
tw
o
k
e
y
matrices
and
one
v
ector
constitut
e
the
k
e
y
which
can
be
written
as
K
(
M
;
N
;
r
)
and
must
be
k
ept
secret
by
client.
3.3.
Outsour
cing
Algorithm
Due
to
the
lack
of
computing
resources,
C
could
be
infeasible
to
carry
out
such
e
xpensi
v
e
computa
tion
as
O
(
n
)
for
2
<
3
locally
.
Therefore,
client
will
outsource
the
computation
w
orkloads
to
cloud
serv
er
in
a
pay-per
-use
manner
[11].
Client
chooses
M
;
N
2
R
nn
tw
o
random
sparse
matrices
which
generate
from
3.2.
to
hide
A
h
then
computes
K
=
M
A
h
N
.
So
that
the
input
of
problem
generation
(ProbGen)
algorithm
is
a
c
oef
ficient
matrix
A
h
u
h
A
2
R
n
n
and
a
coef
ficient
v
ector
b
h
2
R
n
.
From
abo
v
e
transformation
the
original
matrix
of
finite
dif
ference
method
of
BVP
can
be
re
wri
tten
as
A
(
x
+
r
)
h
=
c
.
Then,
C
computes
K
=
M
AN
and
d
=
M
c
.
W
ithout
loss
of
generality
,
we
denote
u
=
N
1
(
x
+
r
)
,
where
N
1
is
the
in
v
erse
of
matrix
N
.
Note
that
in
our
algorithm,
no
party
needs
to
compute
N
1
.
It
appears
h
e
re
only
for
representing
the
form
of
u
.
In
f
act,
if
N
1
had
to
be
computed,
the
algorithm
w
ould
no
longer
be
ef
ficient
as
the
time
and
computational
comple
xities
incurred
by
computing
N
1
w
ould
be
v
ery
undesirable.
Note
that
K
u
h
=
M
A
h
N
pN
1
(
u
h
+
r
)
=
M
A
(
u
h
+
r
)
=
M
c
=
d
,
then
outsource
this
K
;
d
to
the
cloud
and
get
th
solution
as
a
coef
ficient
v
ector
u
h
such
t
hat
K
h
u
h
=
d
h
.
Using
the
random
disguising
technique,
we
can
pro
v
e
the
pri
v
ac
y
of
proposed
outsourcing
schema
for
A
h
;
b
h
and
the
solution
x
.
Besides,
The
proposed
schema
only
requires
one
round
interaction
between
cloud
and
serv
er
and
does
not
require
an
y
special
encryption
techniques,
so
the
comple
xity
to
compute
K
is
O
(
n
2
)
.
4.
SECURITY
AN
AL
YSIS
Theorem
1:
In
the
fully
malicious
model,
the
algorithms
(C,
S)
ar
e
privacy
for
A
h
;
b
h
,
and
u
h
.
Pr
oof
.
W
e
first
pro
v
e
the
pri
v
ac
y
for
input
b
h
and
output
u
h
of
B
VP
.
Note
that
the
adv
ersary
A
h
can
only
kno
w
K
and
d
throughout
the
whole
algorithm.
Besides,
we
ha
v
e
b
h
=
M
1
d
Ar
;
and
u
h
=
N
x
r
.
Since
r
is
a
random
blinding
coef
ficient
v
ector
in
R
n
,
both
b
and
u
h
are
blinded
by
r
in
the
sense
of
indistinguishability
.
W
e
then
pro
v
e
the
pri
v
ac
y
for
input
A
h
.
Let
M
=
(
m
ij
)
;
N
=
(
n
ij
)
;
M
0
=
(
m
ij
)
;
and
N
0
=
(
n
0
ij
)
be
four
random
nonsingular
sparse
matrices
generated
by
C.
Gi
v
en
tw
o
nonsingular
dense
matrices
A
=
(
aij
)
and
A
0
=
(
a
0
ij
)
which
are
chosen
by
the
adv
ersary
A
h
,
C
computes
K
=
M
A
h
N
=
(
k
ij
)
and
K
0
=
M
0
A
h
0
N
0
=
(
k
0
ij
)
,
where
k
ij
=
n
X
i
=1
n
X
j
=1
m
if
a
k
f
n
if
Privacy
pr
eserving
outsour
cing
algorithm
for
two-point
linear
...
(Nedal
M.
Mohammed)
Evaluation Warning : The document was created with Spire.PDF for Python.
1068
r
ISSN:
2502-4752
and
t
0
ij
=
n
X
i
=1
n
X
j
=1
m
0
if
a
0
f
i
n
0
ij
Note
that
the
numerical
v
alue
and
position
of
all
non-zero
elements
of
four
matrices
M
;
N
;
M
0
and
N
0
are
randomly
chosen
by
C,
thus
k
ij
and
k
0
ij
are
computationally
indistinguishable.
As
a
result,
the
adv
antage
of
A
h
to
distinguish
between
K
and
K
0
is
ne
gligible.
Theorem
2:
In
the
fully
malicious
model
,
the
algorithms
(C,
S)
ar
e
an
O
(
1
n
)
ef
ficient
implementation
of
sc
hema.
Pr
oof
.
In
the
propos
ed
algorithm,
C
needs
to
perform
four
matrix-v
ector
multiplication
(we
omit
the
v
ector
-addition
operations),
which
tak
es
O
(
n
2
)
computations.
Besides,
C
also
ne
eds
to
compute
K
=
M
AN
,
which
also
tak
es
O
(
n
2
)
computations.
Thus,
the
ef
ficient
implementation
of
our
algorithm
(C,
S)
are
an
O
(
1
n
)
.
5.
EXPERIMENT
AL
RESUL
T
AN
AL
YSIS
The
e
xperimental
results
are
the
a
v
erage
of
multiple
trials.
W
e
design
numerical
e
xperiments
to
e
v
al-
uate
the
ef
ficienc
y
of
the
mechanism.
W
e
implemented
it
using
Matlab
(2013a),
with
the
system
configuration
is
”
C
P
U
I
ntel
R
C
or
e
TM
i
3(
C
P
U
s
)
˜
1
:
8
GH
Z
4
GB
R
am
”
on
a
laptop
and
Amazon
Elastic
Compute
Cloud
(EC2)
cluster
.
The
test
benchmark
for
randomly
generated
sparse
matrices
only
focuses
on
the
lar
ge-
scale
problems
where
n
ranges
from
5
;
000
to
20
;
000
;
as
T
able
1.
T
able
1.
Performance
of
the
proposed
scheme
Pr
oblem
K
eyGen
Pr
obGen
V
erify
Solv
e
Client
Size
Algorithm
Algorithm
Algorithm
Algorithm
Cost
T
ime
1
n
=
5000
10.15
116.88
6.13
10.54
133.03
2
n
=
10000
19.20
231.23
10.89
14.02
261.32
3
n
=
15000
23.13
347.72
20.54
17.43
391.39
4
n
=
20000
33.97
580.73
27.85
18.56
642.55
T
o
measure
the
ef
ficienc
y
of
our
proposed
mechanism,
we
simulated
all
four
phases
(i.e.,
K
e
yGen,
ProbGen,
V
erify
and
solv
e).
The
corresponding
time
costs
for
dif
ferent
size
of
problems
are
sho
wn
in
Figure
2.
0.5
1
1.5
2
x 10
4
0
100
200
300
400
500
600
700
Problem Size
Tim in (sec)
Cost of ProbGen
Cost of Cloud(slove)
Cost of KeyGen
Cost of Client
Cost of Verify
Figure
2.
T
ime
cost
for
each
phase
of
secure
outsourcing
BVP
algorithm.
Indonesian
J
Elec
Eng
&
Comp
Sci,
V
ol.
16,
No.
2,
No
v
ember
2019
:
1065
–
1069
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
r
1069
6.
CONCLUSION
In
this
paper
,
we
proposed
a
ne
w
secure,
ef
ficient
algorithm
for
securely
outsourcing
of
lar
ge-s
cale
finite
dif
ference
method
to
find
the
solution
of
linear
BVP
computation
using
cloud
computing.
W
e
implement
schema
on
the
customer
side
laptop
and
using
A
WS
compute
domain
elastic
compute
cloud
(EC2)
for
the
cloud
side.
W
e
find
that
the
proposed
schema
is
suitable
to
approxi
mate
solutions
to
dif
ferential
equations
(BVP)
problem
and
only
requires
O
(
n
2
)
computational
o
v
erhead
e
v
en
in
the
fully
malicious
model.
REFERENCES
[1]
C.
Hu,
A.
Alhothaily
,
A.
Alra
w
ais,
X.
Cheng,
C.
Sturti
v
ant
and
H.
Liu,
”A
secure
and
v
erifiable
out-
sourcing
scheme
for
matrix
in
v
erse
computation,
”
IEEE
INFOCOM’17
(Atlanta,
GA,
USA)
,
V
ol.
4,
pp.
2304–2312,
2017.
[2]
N.
M.
Mohammed
and
S.
S.
Lomte,
”Recent
adv
ances
on
secure
computations
outsourcing
in
cloud
computing,
”
Asian
Journal
of
Mathematics
and
Computer
Research
,
V
ol.
24,
pp.192–205,
2017.
[3]
K.
Zhou
and
J.
Ren,
”CASO:
Cost-A
w
are
Secure
Outsourcing
of
General
Computational
Problems,
”
IEEE
T
ransactions
on
Services
Computing
,
2018.
[4]
W
.
Shen,
Y
.
Bo,
C.
Xianghui,
C.
Y
u
and
S.
Xuemin,
”A
distrib
uted
secure
outsourcing
scheme
for
solving
linear
algebraic
equations
in
ad
hoc
clouds,
”
IEEE
T
ransactions
on
Cloud
Computing
,
V
ol.
4,
2017.
[5]
H.
C.
Sax
ena,
”Finite-Dif
ferences
and
Numerical
Analysis,
Thirteen
Re
vised
Edition,
”
Published
by
S.
Chand&
Compan
y
Ltd.
Ne
w
Delhi
,
1997.
[6]
U.
Ascher
,
R.
Mattheij
and
R.
Russell,
”Numerical
Solution
of
Boundary
V
alue
Problems
for
Ordinary
Dif
ferential
Equations,
”
Prentice-Hall
,
1988.
[7]
N.
M.
Mohamm
ed
and
S.
S.
Lomte,
”Secure
Computations
Outsourcing
of
Mathematical
Optimization
and
Linear
Algebra
T
asks:
Surv
e
y
,
”
International
Journal
for
Research
in
Engineering
Application
&
Management
,
pp.
6–11,
2019.
[8]
A.
Geor
ge
and
J.
Liu,
”Computer
Solution
of
Lar
ge
Sparse
Positi
v
e-definite
Systems,
”
Prentice-Hall
,
1981.
[9]
D.
M.
Y
oung,
”Iterati
v
e
Solution
of
Lar
ge
Linear
Systems,
”
Academic
Press
,
1971.
[10]
N.
M.
Mohammed
and
S.
S.
Lomte,
”Secure
and
Ef
ficient
Outsourcing
of
Lar
ge
Scale
Linear
Fractional
Programming,
”
International
Conference
on
Computing
in
Engineering
and
T
echnology(I
CCET)
,
2019,
T
o
Appear
.
[11]
S.
Salinas,
C.
Luo,
X.
Chen,
W
.
Liao
and
P
.
Li,
”Ef
ficient
Secure
Outsourcing
of
Lar
ge-scale
Sparse
Linear
Systems
of
Equations,
”
IEEE
T
ransactions
on
Big
Data
,
2017.
DOI
10.1109/TBD
A
T
A.2017.2679760,
Privacy
pr
eserving
outsour
cing
algorithm
for
two-point
linear
...
(Nedal
M.
Mohammed)
Evaluation Warning : The document was created with Spire.PDF for Python.