TELKOM
NIKA
, Vol. 13, No. 4, Dece
mb
er 201
5, pp. 1113
~1
120
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i4.3122
1113
Re
cei
v
ed Au
gust 25, 20
15
; Revi
sed
No
vem
ber 3, 20
15; Accepted
No
vem
ber 1
8
,
2015
A Polynomial-Based Pairwise Key Pre-distribution and
Node Authentication Protocol for WSNs
Fateme
h Ba
naie
1
, Se
y
e
d Amin Hoss
e
i
ni Seno*
2
, Is
mat Aldmour
3
, Rahmat Budiarto
4
1,2
Net
w
ork R
e
s
earch L
a
b
o
rato
r
y
, Dep
a
rtment
of Engine
eri
n
g
,
F
e
rdo
w
s
i
Un
i
v
ersit
y
of Mas
h
had
3,4
Smart Net
w
o
r
ked Com
putin
g Rese
arch Group, Co
lle
ge of
Computer Sci
ence a
nd Infor
m
ation
T
e
chnolog
y, Al
Baha Un
iversit
y
, Kin
gdom of
Saud
i Arabi
a
*Corres
p
o
ndi
n
g
author, em
ail
:
Banaie.F
@
st
u-mail.um.
a
c.ir
1
, Hosseini@
u
m
.ac.ir
2
, iaald
m
our@b
u.ed
u.sa
3
,
rahmat@
bu.ed
u.sa
4
A
b
st
r
a
ct
Conti
nuo
us ad
vances i
n
the
areas of sen
s
or netw
o
rks have
ma
de w
i
r
eless se
nsor
netw
o
rks
(W
SNs) attractive for
a w
i
de
variety of
app
li
cations, w
i
th v
a
stly varyi
ng r
equ
ire
m
e
n
ts a
nd ch
aracter
i
stics.
As the d
a
ta
sense
d
by
no
des us
ual
ly c
ontai
n se
ns
itiv
e infor
m
ation,
adh
ere
n
ce t
o
data
protec
tion
requ
ire
m
e
n
ts is vital in W
S
Ns.T
his pap
er intr
od
uces
a new
and
robust key pre-distri
buti
o
n
ke
y
ma
na
ge
me
nt
sche
m
e
usi
n
g
ran
d
o
m
poly
n
o
m
i
a
l fu
nctio
n
s a
nd
a
ma
trix. T
he pr
op
osed
mech
an
i
s
m
signific
antly
in
creases stor
ag
e efficie
n
cy a
nd e
n
h
anc
es
netw
o
rk resil
i
e
n
ce a
g
a
i
nst n
ode c
aptur
e. T
h
e
effectiveness
of
the mecha
n
is
m
is
de
mo
nstrated
by s
e
curity a
n
a
l
ysi
s an
d co
mpar
isontoth
e
ex
istin
g
schem
es.
Ke
y
w
ords
: Da
ta protection; k
e
y ma
na
ge
me
nt; pr
e-distrib
u
tion; po
lyn
o
mia
l
functions
Copy
right
©
2015 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
No
wad
a
y
s
, Wirel
e
s
s
Sen
s
or
Netw
or
ks
(WSN
s
)
a
r
e being wi
dely use
d
for larg
e rang
e of
appli
c
ation
s
su
ch a
s
environm
ental m
onitorin
g
, sm
art enviro
n
m
ents an
d sci
entific exploration.
Senso
r
n
ode
s a
r
e u
s
ually
scattered
in u
nattende
d an
d adversa
rial
environ
ment
s [1]. As the d
a
ta
sen
s
e
d
by th
e ap
plication
s
of
WS
N oft
en
contai
n
sensitive i
n
formation, ad
he
ren
c
e to
se
cure
data
tran
sfer
is vital in the
s
e appli
c
atio
ns. In
WSNs, data istran
smitted wirele
ssly, whi
c
h m
a
ke
s
itvulnerabl
e to attacks, su
ch a
s
eave
s
drop
pi
ng, im
person
a
tion
and mo
difica
tion of data [2].
Hen
c
e, securi
ng the links e
s
tabli
s
he
d be
tween the
n
o
des in the n
e
twork is a
criti
c
al issu
e.
Key manag
e
m
ent is
co
rn
er
stone to
many se
cu
rit
y
servi
c
e
s
th
at can
be u
s
ed to me
et
confid
entiality, integrity an
d authe
nticat
ion re
qui
rem
ents in
se
cu
re
commu
nications [3]. T
h
e
main
goal
of
key
man
a
g
e
ment i
s
to
provide
secu
re
com
m
uni
cations bet
we
en the
no
de
s.
Existing sol
u
tionsfo
r conve
n
tional net
wo
rks, su
ch
as t
he sol
u
tion
s
based on
pub
lic key
s
, are
not
suitabl
e for u
s
e in
WSNs
due to resou
r
ce
co
nst
r
ai
nt
s, [4]. To ad
dre
ss thi
s
i
s
sue, most of t
h
e
existing sol
u
tions u
s
e ra
n
dom key pre-di
strib
u
tion
for ensu
r
in
g se
cure co
mmuni
cation
s in
WSN
s
.
Maste
r
Key
Manag
em
ent
is a basi
c
pre-di
strib
u
tion approa
ch, in whi
c
h a sin
g
l
e
key is
prelo
ade
d int
o
eve
r
y sen
s
or
nod
e b
e
fore de
ployment
. The
advant
age
s of
this schem
e
are
hi
gh
scalability and minim
a
l
storage
requirements.
Ho
wever,
it suffers from
very low network
resili
en
ceb
e
cause if an
adversa
ry ca
pture
s
a
no
de; the
se
cu
ri
ty of the entire network is
compromi
sed [5]. Localized Encr
yption
and Authenti
c
ation Protocol (LEAP) off
e
rs a
better ke
y
distrib
u
tion f
o
r la
rge
scal
e
distrib
u
ted
se
nso
r
net
works,the b
a
si
c id
ea i
s
to
erase
the m
a
ste
r
ke
y
after esta
blishing the pai
r wise
key th
at incr
ea
se
s the re
silien
c
e
,
howeve
r
, ne
wly adde
d n
ode,
whi
c
h still has the master
ke
y, can be compromised [1].
In
Pair
wis
e
K
e
y
Di
stributio
n
sch
e
me
s, p
a
irwi
se
keys
are
load
ed to
all p
o
ssibl
e
pairs o
f
sen
s
o
r
s in th
e netwo
rk. F
o
r a network with
n
sen
s
o
r
nodes, eve
r
y node will h
a
ve to store
n
-1
keys. Although this solution prov
ides good connectivity and very
good resilience against attacks,
it is impractical to store
all
the key
s
in
each
sens
or
a
nd it is
not
scalable tol
a
rg
e
r
WS
Ns [5, 6]
. In
Ran
dom
Pairwise Key Pre
-
dist
ributio
n
[7], distinct pa
irwi
se keys a
r
e pre-di
stri
b
u
ted ran
doml
y
in
the sen
s
o
r
n
ode
s befo
r
e
deployme
nt. EG schem
e [8] is aba
sic rand
om key pre-dist
ributi
o
n
scheme,
whi
c
h a
d
d
r
e
s
se
s the
red
u
n
dan
cy in
the
previo
us
scheme
s
a
nd
yet provide
s
a
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No
. 4, Decem
b
e
r
2015 : 111
3 – 1120
1114
reasonable
key resilience.
In this
schem
e
, a large pool of key
s
S
is
first ge
nerate
d
out of
which
keys are ran
domly sele
cte
d
for esta
blish
i
ng a key ring
, where
≪
and
is the total number of
keys. T
h
is
m
e
thod n
eed
s l
e
ss mem
o
ry t
o
sto
r
e the
key ring th
an
storing th
e wh
ole po
ol of ke
ys
.
Ho
wever, if node
s are p
r
o
g
re
ssively ca
ptured, t
he at
tacker can di
scover a larg
e portion of the
pool.
Another ap
proach i
s
the
P
o
lyn
o
m
i
al Ke
y Pre-distri
bu
tion
ba
sed
scheme
s
. Liu
a
nd
Ning
in [9] p
r
op
ose
d
to
use
symmetric biva
ria
t
e polyno
m
ial
s
in
the
key g
eneralization
pha
se th
at ha
ve
the pro
p
e
r
ty
f(x
,
y) = f(y
,
x)
.This
ap
proa
ch
enh
a
n
ce
s resili
en
ce a
gain
s
t n
ode
captu
r
e
by
comp
uting di
stinct secret
keys, but it incr
e
a
ses t
he memo
ry usa
ge and t
he com
putati
onal
overhe
ad.Aut
hors in [10] pr
op
osed a
novel polyno
m
ial ba
sed
Q com
p
o
s
ite
approa
che
whi
c
h
combi
n
e
s
ro
b
u
stne
ss of Q comp
osit sch
e
me with poly
nomial ba
se
d
key gene
rati
on schem
e.
Blom in [11]
prop
osed a
-se
c
ure symm
etric key
g
e
n
e
ration
sy
ste
m
that uses
a publi
c
matrix
an
d a
private
sym
m
etric
matrix
. The keys
are se
cu
re if n
o
more than
node
s are co
mpromi
se
d. Then, the ma
trix of
the pairwi
s
e key
s
of node
is
.
In [12]
a pre
-
di
strib
u
t
ion schem
e usin
g LU m
a
trix is pr
opo
sed, whi
c
h u
s
es L
U
matrix
and Polyno
mial
based key pre-di
strib
u
tion
to achiev
e hi
gh re
silien
c
e
and conn
ecti
vity.
Thework
i
n this
paper is
an extens
ion of pr
evious
work
in [13].It is
based on random
function
pre-distrib
u
tion a
nd u
s
e
s
poly
nomial fu
ncti
on an
d mat
r
ix to ensure
a better
se
cu
rity.
The m
a
in
ai
m of thi
s
wo
rk i
s
to
p
r
op
o
s
e
an
efficie
n
t
key
pre
-
di
st
ribution
sche
me for effici
e
n
tly
more
se
curity
and re
silien
c
e of the network.
2. Proposed Pre-Dis
t
rib
u
tion Key
Manageme
nt
Scheme
The whol
e ne
twork co
nsi
s
t
s
of
l
a
rge nu
mber
of
static se
nsor no
de
s di
stri
buted
randomly
in the field, cluster h
ead
s
and a si
ngle
base stati
on.
Without lo
ss
of generalit
y,
it is assumed
t
hat
the sen
s
ing field is divided into
logical
region
s, denoted by
,
1,
2,
…
,
,
(
a
s sh
ow
n in
Figure 1
)
. It follows that
there
are a
r
oun
d
nodes and one cluster he
ad in each
regio
n
.To re
d
u
ce e
nergy consumption i
n
the
netwo
rk, sen
s
o
r
no
des
comm
uni
cate with b
a
s
e
station a
nd n
ode
s in othe
r regio
n
s th
ro
ugh
clus
te
r h
ead
s, whi
c
h
have more e
nergy
resou
r
ce
s
than sen
s
o
r
n
ode
s. Once a
n
adversary capture
s
a nod
e, it can obtain all of the node’s cre
denti
a
l
informatio
n li
ke
key
s
a
nd i
dentity.The fo
llowi
ng
a
s
su
mptions have
bee
n ma
de f
o
r th
e p
r
op
osed
proto
c
ol:
Base
station
is tru
s
ted
an
d
has
a tamp
er re
sista
n
t ha
rdwa
re. It ha
s
informatio
n a
bout all th
e
keys a
nd no
d
e
s in the net
work.
Clu
s
ter h
ead
s are a
s
sum
ed to have
more
re
sou
r
ces tha
n
se
n
s
or
nod
es
a
nd the ba
se
station is a p
o
we
rful nod
e and mo
re po
werful tha
n
the clu
s
ter he
a
d
s.
Every sen
s
o
r
node
ha
s a
uniqu
e glo
bal
identity in th
e wh
ole n
e
twork an
d a lo
cal identity in
its own
clu
s
te
r.
Eac
h
mat
r
ix
is gen
erate
d
b
y
the key see
d
s of re
gion
and its cl
uste
r head.
Table 2 sum
m
ari
z
e
s
som
e
of the nece
s
sary notatio
ns in this p
a
p
e
r.
Figure 1. The
stru
cture of the network.
Table II. Notation in this
paper
Notation
Description
a, b, c, …
Cluster heads identities
Number of senso
r
nodes in the W
S
N
Number of senso
r
nodes in cluster
i
Number of
regio
n
s in the sensing field
Identit
y
of no
de
j
Random nonce g
enerated
b
y
n
o
d
e
j
Session key
bet
w
e
en node
i
an
d
j
i
t
h
ro
w
of ma
trix
One-
wa
y hash fu
nction applied to string
m
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Polynom
ial-ba
sed Pai
r
wi
se Key P
r
e-di
stributio
n and
Node Authe
n
t
ication … (F
atem
eh B.)
1115
The
pro
p
o
s
e
d
key p
r
e
-
di
stribution
an
d
node
auth
ent
ication
p
r
oto
c
ol for WS
Nsconsi
s
ts
of 3 phases a
s
follows:
2.1.
Initial Setup of S
y
stem
Theinitial setup of the network an
d the
ke
y pre-dist
ribution p
r
o
c
ess of the propo
sed
proto
c
ol is
co
mposed of 3 step
s as follo
ws.
Step I (pol
yn
om
ial pool g
eneration
)
:
At first, the
ke
y setup
se
rv
er g
ene
rate
s a large
pool
of
bivariate
t
-de
g
ree
polyno
m
ials ove
r
the f
i
nite field
with uniq
ue
Id
f
o
r e
a
ch of th
e polyno
m
ial
s
.
,
∑
,
,
1,
…
,
, where
k
i
s
the total numbe
r of po
lynomials. T
hese
polynomial
s
have a prop
erty that the
numbe
r of compromised node
s is less than
t
[14] an
d
,
,
,
,
∈
.Each cl
uste
r head
rand
o
m
ly pick
s a
sub
s
et of pol
ynomials
from the
po
ol
befo
r
e
deplo
y
ment.The di
stributio
n m
u
st be
in
such
a way that
an
y pair of
regio
n
s
can di
scover
at least one
common fun
c
ti
on.
Step II
(s
y
mmetric
matrix
formation):
In this
s
t
ep, a s
y
mmetric
mat
r
ix
Q
wit
h
a size of
1
1
is gen
erate
d
for each re
g
i
on, whe
r
e
is the total nu
mber of
sen
s
or no
de
s that are
deploye
d
in the regi
on
i
. This matrix is
calcul
ated as follow:
1.
At first, a prim numbe
r is generated for
ea
ch sen
s
or n
ode
with uniqu
e ide
n
tity
i
,
u
s
ing
Euler
’
s function
.
2.
The se
rver calcul
ates a share of
,
,
that is
,
∑
,
∈
, i, j= 1,…,
N,
whe
r
e
is th
e gen
erate
d
prime
numb
e
r
for n
ode
i
usin
g
Eule
r
’
s
function
and
is the
gene
rated p
r
i
m
e numb
e
r o
f
sensor no
de
j
.
3.
The serve
r
gene
rate
s m
a
trix
,
1
,…,
for e
a
ch
of the clu
s
ter h
ead
s, wh
ere
H(
,
is the element in the
i
th
row and
j
th
column of matrix
,
is the numbe
r of
polynomial
s
a
ssi
gne
d to ea
ch cl
uste
r he
ad and
H is a
one-way ha
sh function.
As
,
,
, the generated matri
c
e
s
are symmet
r
ic. Therefore
, where
is the eleme
n
t in the
i
th
row and
j
th
c
o
lumn of the matrix.
Step III (k
ey
pre-dis
t
ribution).
For
ea
ch
sen
s
o
r
no
de
a su
bset of t
he gen
erated
matrices fro
m
matrices
that are assig
ned
to
its
clu
s
ter
head, i
s
sel
e
cted. The
n
the
i
t
h
r
o
w
of
sel
e
ct
ed
mat
r
ix
f
o
r
node
i
, i
ndex of
matrix ro
w,
and id
e
n
tity of
matrices i
s
pre
-
loa
ded
to
it.
1
,
,
,
…
,
. The d
e
scri
p
tion can b
e
better
compl
e
ted with the
h
e
lp
of an exampl
e. Figure 2 il
lustrate
s a
n
example
of a
simple
network. Su
ppo
se
the cal
c
ulat
ed
matrices fo
r the first re
gion
are as follo
w:
5
3
7
12
3
1
4
9
7
4
2
20
12
9
20
5
1
1
0
6
17
10
3
5
2
6
5
1
9
17
2
9
7
Figure 2. An example of key
Pre-di
stri
buti
on.
9
1
2
8
1
4
7
12
2
7
10
3
8
12
3
20
4
14
3
5
14
8
2
1
1
3
2
7
2
0
5
11
20
1
2,
2
,
3
1
4
9
,
2,
5
,
103
5
2
→1
3,
5
,
65
1
9
,
3,
7
,
2
7
1
0
3
→2
4,
7
,
812
320
,
4,
8
,
511
2
0
1
→3
Suppo
se
that
functio
n
2 a
nd 5
i
s
a
s
sig
ned to
n
ode
1, 2
and
7 to
node
2
and
7 an
d
8
tonode
3. He
nce, the
seco
nd row
of mat
r
ice
s
and
are pre-lo
ade
d
to node
1, wh
ile the third
row of
, and
and forth
ro
w of
and
are p
r
e
-
lo
aded to
nod
e
2 and
nod
e
3, re
spe
c
tively.
The first row i
n
each matrix
is allocated to the clu
s
ter
head.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No
. 4, Decem
b
e
r
2015 : 111
3 – 1120
1116
2.2. Pair
w
i
se
Key
Establishment
Pairwi
se
key
establi
s
hm
e
n
t betwe
en
two sen
s
or
node
s is
do
ne a
cco
rdi
n
g
to the
f
o
llowin
g
st
ep
s.
Step I:
After sen
s
o
r
no
de
s are d
eploye
d
in the field,
they initiate the proto
c
ol
by gene
ratin
g
a
rand
om no
n
c
e
and excha
ngin
g
a HELLO m
e
ssag
e of the following fo
rmat:
→
∗
∶
,
,
,
,
_
,…,
_
. The me
ssa
ge contain
s
the identity of node
i
, the
non
ce
,
index of the matrix row
an
d the identity of matrice
s
th
at are preloa
ded to it.
Step II:
On recipie
n
t of such a messa
ge,
node
j
calcul
ates the pairwise key
that is computed
as
follow:
1. Nod
e
j
first g
enerates a
ra
ndom nu
mbe
r
. Then it cal
c
ulate
s
the m
-
dime
nsi
onal
vector
R
by combini
n
g
with the receiving
from n
ode
i
.
∥
→
,…,
2. After
obtainin
g
R
, it calcul
ates
Vir
by the pro
d
u
c
tio
n
of the two vectors
and
.
is vector of share
d
matri
c
e
s
’s valu
es b
e
twee
n two no
des.
.
,…
,
.
,…,
To obtain the
values of ve
ctor
, node
j
sho
u
ld find th
e comm
on m
a
trice
s
with n
ode
i
.
Then it refe
rs to the
th
element of stored ro
w
, for
all
1
,…,
that
k
is
th
e
s
h
ar
ed
matrices b
e
twee
n them. Let
_
,…,
_
be the identities of sha
r
ed matri
c
e
s
, then
is:
=
(
,
,…,
,
). As
,…,
are
symmetri
c
matrices, a
n
d
alway
s
ha
ve
,
,
. So, the
i
th
e
l
ement of
,
is
alway
s
equ
al
to the
j
th
element of
,
. Now, nod
e
j
resp
ond
s wi
th an ACK messag
e as sh
own in the
following:
→
∶
,
,
,
_
,…,
_
,
Step III:
Upon re
ceiving th
e messa
ge b
y
node
i
, it ca
n cal
c
ulate
having the val
ue of
. Then
node
i
obtain
s
′
by prod
uct
i
on of
and
. If
′
, then
j
is an
autho
ri
zed
nod
e
and
′
.
To illustrate how to calcul
ate
, conside
r
the p
r
e
v
ious exam
pl
e sh
own i
n
Figure 2. After se
nsor n
o
d
e
s a
r
e de
ploy
ed, t
he nod
e
s
begi
n to excha
nge
HELL
O messa
g
e
s
as
follow:
1→
∗
∶
,1
,2
,1
5
,
2
,
5
,
2→
∗
∶
,2
,3
,1
1
,
5
,
7
,
3→
∗
∶
,3
,4
,8
,7
,8
Whe
n
no
de
2
receives th
e
messag
e fro
m
node
1, it che
c
ks th
e n
u
mbe
r
of fun
c
tion
s in
comm
on with
it. In
this example the only function is
5
; therefore ve
ctor
has one element. As
the index of
node
i
in matrix
is
2
, nod
e
2
should refer to the seco
nd eleme
n
t of its
vecto
r
5
.
5
1
5∥1
1
7
5
.Node
2
se
nds
a me
ssage in
re
sp
onse to the
HELLO m
e
ssage:
2→1
∶
2
,
3,
11
,
5
,7,
75
. After this me
ssage
is re
ceived
b
y
node
,
it can
cal
c
ulate
15
∥
11
to obtain the valu
e of
, which i
s
the third
ele
m
ent of vecto
r
(
5
.As mention
e
d
previo
usly,
,…,
are
symme
tric mat
r
ice
s
and
.
5
,
′
5
1
5∥1
1
7
5
. So,
H
′
7
5
. H
is use
d
as
se
ssi
on key
for
establi
s
hi
ng a
secure
com
m
unication b
e
twee
n nod
e
and nod
e
.
Step IV:
Now, node
sho
u
ld authenti
c
ate itself to
node
j
. So, it send
s a MAC messa
ge
contai
ning its identity, a random g
ene
ra
ted key
K
an
d
encrypted
by
.
This me
ssag
e allo
w
j
to verify the validity of node
i
.
→
∶
,
,
.
2.3. Path
Ke
y
Establishment
In establi
s
h
m
ent of the p
a
i
rwi
s
e
key b
e
t
w
een
se
nsor node
s th
at are
not in th
e sa
me
clu
s
ter o
r
do
not have any sha
r
ed m
a
trix,
the following
procedu
re
s a
r
e ca
rri
ed out
:
Ca
se I: Both node
s are in the sam
e
clu
s
ter
Suppo
se that
node
in cluster
wants to sen
d
a dat
a to node
in
the same cl
uster.
Nod
e
bro
a
d
c
asts a
HELL
O messa
ge a
s
follow:
→
∗
∶
,
,
,
,
,
_
,…,
_
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Polynom
ial-ba
sed Pai
r
wi
se Key P
r
e-di
stributio
n and
Node Authe
n
t
ication … (F
atem
eh B.)
1117
After receiving the messag
e by the
node
s that has a
common mat
r
i
x
with
, it calculates
acco
rding to
the mentio
n
ed ste
p
s
i
n
section
2 an
d
respon
ds to
node
with a
messag
e a
s
s
h
ow
n
in
the fo
llo
w
i
n
g
:
→
:
,
,
.After re
ceiving
this me
ssag
e by node
, it
cal
c
ulate
s
′
and authenticates
itself by
sen
d
ing a
MAC messag
e to
:
→
∶
,
,
. Now n
ode
encrypts d
a
t
a usin
g
and se
nd
s it to
After
decrypting th
e messag
e by
it first authenticate
s
nod
e
and se
nd
s the messag
e
to it through
the followin
g
step
s:
→
∶
,
,
→
∶
,
,
,
→
:
,
,
,
,
_
,…,
_
,
,
→
∶
,
,
,
→
∶
,
,
1
,
→
∶
Thus, a p
a
th is esta
blished
betwe
en
and
through n
o
d
e
.
Case II: The nodes are not
in the sam
e
cluster
In this ca
se, after establi
s
hing a pai
rwi
s
e key betwe
en node
i
a
nd
acco
rdin
g to the
above mentio
ned ste
p
s, it
encrypts the
data with
and sen
d
s it to
.
→
∶
,
sen
d
s
to the base
statio
n and re
que
sts the
ide
n
tity of its clu
s
ter he
ad to
establi
s
h
a secu
re lin
k
with it. The ba
se station fin
d
s
the n
ode
s clu
s
t
e
r (f
or
in
st
an
ce
) and
sen
d
s th
e id
e
n
tity of its clu
s
ter
hea
d in
resp
on
se
to th
is me
ssag
e. By receivin
g i
t
s identity,
gene
rate
s and broad
ca
sts
a HELLO
message
of the
following
form:
→∗∶
,
,
,
,
_
,…,
_
. Where it contain
s
the identity of
two cluste
r
head
s, the nonce
, and the identity of the functions
that are
prelo
ade
d to it. When the
messag
e is receive
d
by
, it acts different
ly in one of two ca
se
s:
Ca
se a: It has a com
m
on function
with
. At
firs
t,
calculate
s
a sh
are of its co
mmon
function
s (
,
wit
h
. Then it
gene
rate
s a
rand
om nu
m
ber
and cal
c
ulates
th
e
m-
d
i
me
ns
io
na
l ve
c
t
o
r
R
by combi
n
ing
w
i
th the receiving
from
.
∥
→
,…,
.
Vir
is cal
c
ulat
ed as follo
w, where
is vector of sh
are
d
function’
s value
s
betwe
e
n
two cl
uste
r head
s
:
.
,…,
.
,…,
.
resp
ond
s
with an A
C
K
messag
e as
sho
w
n in the
followin
g
:
.→
.∶
,
,
_
,…,
_
,
With the
re
ceiption of thi
s
me
ssage,
can cal
c
ul
ate
′
. If
′
,
they ca
n esta
blish a
se
cure ch
ann
el for tran
smit
ting the data.
Ca
se b: It ha
s not a
com
m
on fun
c
tion
with
.
In this ca
se the t
w
o
cl
uster he
ads can e
s
tabli
s
h
a se
cure pat
h throug
h the
i
r neigh
bori
n
g clu
s
ter he
a
d
s that sh
are
a commo
n functio
n
.No
w
can forwa
r
d the encrypted
data to
usin
g
. After rece
iving the messag
e by
, it
c
an
authenti
c
ate node
and se
nd the encrypted data to it. T
he proce
s
s is done by excha
nging t
he
f
o
llowin
g
me
ss
age
s:
→
∶
,
,
. After authe
nticati
n
g
by
:
→
∶
,
.
3. Performance An
aly
s
is
3.1. Securit
y
Analy
s
is
The enviro
n
m
ent in whi
c
h sen
s
o
r
nod
es are
deploy
ed is usually hostile an
d h
a
rsh. So,
an adve
r
sary
may physi
ca
lly capture o
ne or mo
re
sensor n
ode
s.
If a node i
s
captu
r
ed
by an
adversa
ry, the crede
ntial
key info
rmati
on kept in t
he no
de mig
h
t be expo
sed
.
As
a
result,
adversa
rie
s
may com
p
ro
mise the
co
nne
ction
of
t
hese
no
de
s and some e
x
tra
co
nne
ctions
se
cured by these key
s
. The numb
e
r o
f
conne
ctio
n
s
that are affected by no
de ca
pturin
g
is
defined a
s
th
e resili
en
ce a
gain
s
t node
capture.
In the pro
p
o
s
ed
proto
c
ol,
the key ge
neratio
n serv
er rando
mly sele
cts
a su
bset of
polynomial
s
f
r
om th
e la
rg
e polyno
m
ial
pool
and
a
s
sign
s th
em t
o
cl
uste
r h
e
a
d
s. Th
en, a
prim
numbe
r is ge
nerate
d
by Euler’
s functio
n
for
each n
o
de based on i
t
s identit
y and a share of these
polynomial
s
comp
uted u
s
i
ng the
s
e n
u
m
bers for
an
y pair of no
d
e
s in
ea
ch cl
uster. F
o
r e
a
c
h
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No
. 4, Decem
b
e
r
2015 : 111
3 – 1120
1118
node a
su
bset of hash
e
d
sha
r
e
s
is
st
ored
before
deployme
nt. On the othe
r hand,
is not
dire
ctly exch
ange
d bet
we
en no
de
s cal
c
ulate
d
lo
ca
ll
y by sen
s
o
r
node
s. Hen
c
e, an adve
r
sary is
not able to listen to the traffic load an
d extract
s
the key
. Likewi
se, this p
r
oto
c
ol meet
s th
e
for
w
ar
d secrecy
. This me
ans that if an adversary m
anag
ed to re
cover a
conti
guou
s su
bset of
se
ssi
on key
s
,
no
previou
s
pairwise key can
be
retr
ie
ved. Thi
s
p
r
o
perty i
s
d
one
by h
a
shing
th
e
keys i
n
ea
ch
step. Th
eref
ore, the
pro
p
o
se
d prot
oco
l
achi
eves
a
high level
of se
curity in th
e
netwo
rk.
3.2. Analy
s
is
of Ne
t
w
o
r
k Conn
ectiv
it
y
Having d
one
calculation o
f
polynomial
s
matr
ice
s
, ev
ery nod
e picks a
su
bset of these
matrices
and
store
s
the
correspon
ding
row
of t
he
matrices.
Distribution i
s
do
ne in
su
ch a
way
that each no
d
e
ha
s at lea
s
t
a co
mmon
key to sha
r
e
with other
node
s in the
clu
s
t
e
r. On th
e ot
her
hand, two no
des th
at do
not have a
common
sh
ared key ca
n
establi
s
h
a p
a
th thro
ugh t
h
e
clu
s
ter
hea
d. Thu
s
, the p
r
obability of h
a
ving two
no
des
with
no p
a
th is
ze
ro. S
o
, the propo
sed
scheme a
c
hi
eves 100%
conne
ctivit
y.In
E- G sche
m
e, conn
ectivity computed
as follow [8, 15]:
P
1
!
!
!
, where
is the size of key pool and each nod
e
stores
k
keys
. If
the
distrib
u
tion is not uniform,
P
is obtaine
d by the
followin
g
equalit
y:
P
1
!
!
!
!
,
whe
r
e
is the numbe
r of assign
ed key
s
to the clust
e
r hea
ds. Fig
u
re 3 sho
w
s
a comp
ari
s
on
of
netwo
rk
con
n
e
ctivity in above sch
eme
s
.
Figure 3. Con
nectivity of th
e netwo
rk
3.3. Memor
y
Analy
s
is
WSN
h
a
s co
nstrai
ned sto
r
age re
sou
r
ces.
The
p
r
o
p
o
se
d protocol redu
ce
s the
stora
ge
co
st effective
l
y. The stora
ge cost of th
e pr
o
p
o
s
ed
proto
c
ol i
s
consi
dereda
s
the su
m of the
memory
usag
e in no
de
s an
d clu
s
te
r he
a
d
s. Ea
ch
sen
s
or no
de h
a
s
1
ro
ws
of
q
matrixes
. In
each row, the
r
e are
1
shares of
,
. Let
be the numbe
r of cluste
rs in the network an
d
be the
total
numbe
r of senso
r
node
s that can
be deployed in the cluste
r, the total memory
usa
ge is:
Γ
,where
Γ
is the n
u
mbe
r
of bits that are required t
o
store
a sh
are
of
,
and
is th
e avera
ge nu
mber of rows that are pre-l
oade
d to ea
ch node.
Clu
s
ter h
ead
s ne
ed to
sto
r
e
k
matrixes
,
where
is the
numbe
r of th
e functio
n
s
a
ssi
gne
d to th
at
c
l
us
ter. The
matrix has
1
1
elements
and
each of tha
t
need
s
storage
resou
r
ce. So, total memory needed i
n
clu
s
ters is:
1
Γ
.Thus
, total
memory req
u
ired i
n
the
netwo
rk i
s
:
1
Γ
.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
50
100
150
200
250
300
350
400
450
500
Co
n
n
ect
iv
ity
N
u
m
b
er
of key
s
in
each
node
EG-schem
e
Du-Schem
e
Proposed
schem
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Polynom
ial-ba
sed Pai
r
wi
se Key P
r
e-di
stributio
n and
Node Authe
n
t
ication … (F
atem
eh B.)
1119
In [8], each sensor n
ode h
a
s to sto
r
e
polynomial
s
. Ifthe sen
s
o
r
n
ode
s re
quire
≫
Γ
bits to sto
r
e
each polyno
m
ial,
the overall storage
overhe
ad i
s
. A
grap
hical co
mpari
s
o
n
of these sch
e
m
es for thei
r
stora
ge r
equi
reme
nts is
sh
own in Fig
u
re
4.
Figure 4. Effect of node nu
mber o
n
storage overhea
d
.
3.4. Resilience agai
nst Node Capture
As se
nsor n
ode
s may be
deployed int
o
hostile e
n
vironm
ent, ke
y information
may be
comp
romi
se
d
if an adversary captu
r
e
s
the node. In this protocol, whe
n
node
is ca
pture
d
, the
adversa
ry ca
nnot retri
e
ve
information
about lin
ks
with non-capt
u
r
ed n
ode
s d
ue to the use of
several polynomial
s
,
.
In other
wo
rd
s, retrievin
g
ot
her
pairwi
s
e
keys with
ou
t having
enou
gh info
rmation ab
out
key pool
s
and matri
c
e
s
is not po
ssible. As ea
ch node
hold
s
matrices, the
adversary re
trieves information about
matrices by
capturi
ng on
e node. If th
e
numbe
r of m
a
trice
s
prel
oa
ded in
one
n
ode i
s
la
rge,
the more sha
r
es of matri
c
es a
r
e
ca
ptured.
The proba
bil
i
ty of resilie
ncy agai
nst
node
captu
r
e can be
cal
c
ulate
d
a
c
cordi
ng to
. Where
is the num
be
r of
captu
r
e
d
se
nso
r
no
de
s,
is
th
e
nu
mber
o
f
se
ns
o
r
node
s which
have co
mmo
n matri
c
e
s
wi
th them, and
is the total n
u
mbe
r
of se
n
s
or
nod
es in
the network.
The p
r
ob
abilit
y of resili
en
cy again
s
t cl
u
s
ter
hea
d ca
pture i
s
cal
c
u
l
ated in th
e same
way
a
s
. Here,
is the numb
e
r of capture
d
clu
s
ter h
e
a
d
s,
is the nu
mber of
CHs that have comm
on function
with them, and
is the total num
ber of clu
s
ter head
s in the
netwo
rk.
4. Conclusio
n
Key manage
ment in wi
re
less se
nsor
netwo
rks i
s
a chall
engi
n
g
issue d
u
e
to the
limitations o
n
sen
s
o
r
nod
e
resource
s. T
h
is pa
pe
rhav
e pro
p
o
s
ed a
new d
e
si
gn o
f
matrix base
d
pairwise key
pre
-
di
stributio
n usin
g depl
o
y
ment kno
w
le
dge to add
re
ss the issue.
The
deploym
ent field
is pa
rtioned
into
e
qual-si
z
e hex
agon
s and
u
s
e
symm
etri
c matrices
for pre-di
strib
u
ting of key
s
. Any pair of node
s can
find a co
mm
on secret ke
y or path
ke
y
betwe
en the
m
selve
s
u
s
in
g the
keys
assign
ed by a
p
ool of polyn
o
m
ials
and m
a
trice
s
. Securit
y
is
improve
d
sig
n
ificantly by random
sele
ct
ion of polyno
m
ials a
nd pri
m
e numb
e
r g
eneration. Th
is
work
also a
c
hieves
a hi
gh
er d
egree
of con
n
e
c
tivity
and a
lo
wer
stora
ge
overhead
co
mpa
r
edto
existing sch
e
m
es.
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
1000
2000
3000
4000
5000
6000
7000
8000
9000
Storage overhead
N
u
m
b
er of
nodes
10
6
L
i
u-schem
e
Proposed
schem
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No
. 4, Decem
b
e
r
2015 : 111
3 – 1120
1120
Referen
ces
[1]
S Zhu, S
Setia, an
d S
Jajodia. “
L
EAP: ef
ficient s
e
curit
y
mechanisms
for
lar
ge-
scale distributed
sensor n
e
t
w
ork
s
”.
ACM T
r
ansactions o
n
Sen
s
or Netw
orks
.
200
6; 2(4): 500
–52
8.
[2]
X F
an
an
d G Gong. “LPK
M: A Light
w
e
i
ght
Pol
y
n
o
mi
a
l
-Base
d
Ke
y
Mana
geme
n
t Protocol for
Distribut
ed W
i
reless Se
nsor N
e
t
w
o
r
ks”.
LNIC
ST
. 2013; 111:
180-1
95.
[3]
W
Bechkit, Y
Chal
la
l, A Bou
abd
all
ah, V T
a
rokh. “A Hi
gh
l
y
Scala
b
l
e
Ke
y
Pre-Distrib
utio
n Schem
e fo
r
W
i
reless Se
ns
or Net
w
orks”.
IEEE Transaction on Wireless
Communic
a
tion
. 2013; 1
2
(2): 948 – 9
59.
[4]
W
Du, J Deng, YS Han, PK Varshn
e
y
, J Kat
z
and A Khali
li.
“A pair
w
i
s
e K
e
y
Pre-
distrib
u
t
i
on Sch
e
me
for W
i
reless S
ensor N
e
t
w
ork
s
”.
ACM T
r
ansaction o
n
Infor
m
ati
on a
nd Sy
stem Sec
u
rity
. 2005; 8(
2):
228-
258.
[5]
S Bala, G Sharma, and K
Verma. “Class
ificatio
n of S
y
mmetric Ke
y
Mana
geme
n
t Schemes fo
r
W
i
reless Se
ns
or Net
w
orks”.
Internati
o
n
a
l Jo
urna
l of Securi
ty and Its Appl
icatio
ns
. 201
3; 7(2): 117-
138.
[6]
A Perrig, R
Sze
w
cz
y
k
, JD T
y
gar, V Wen, DE
C
u
ll
er
. “SPINS: Securit
y
Protoco
l
s for Sens
or
Net
w
o
rks
”.
Jou
r
nal of W
i
rel
e
s
s
Netw
orks
.
2002; 8(5): 52
1 - 534.
[7]
H Cha
n
, A Pe
rrig, an
d D So
ng. “
Ra
ndo
m
key pre-
distrib
u
tion sc
he
mes
for sensor
ne
tw
orks
”. In:
Proceedings
of the IEEE S
y
m
posium on S
e
c
u
rit
y
a
nd Pr
ivac
y
,
Oakland, Calif
or
nia, USA. 2003:
197–
213
[8]
L Esch
en
auer
an
d V
D
Gli
g
or. “
A key-
ma
nag
e
m
ent
sch
eme for
distri
buted
se
nsor
netw
o
rks
”. In:
Procee
din
g
s o
f
the 9
th
ACM Confer
ence
on
Computer
an
d Commu
nicat
i
ons Sec
u
rit
y
,
W
a
shin
gto
n
DC, USA. 200
2: 41– 4
7
.
[9]
D Li
u a
n
d
P N
i
ng. “
Estab
lish
i
ng
pairw
ise
ke
ys in
distrib
u
te
d se
nsor
netw
o
rks
”. In: Proc
eed
ings
of th
e
10
th
ACM Com
puter an
d Com
m
unic
a
tions S
e
curit
y
, W
a
s
h
i
ngton D
C
, USA. 2003: 52
–6
1
.
[10]
EA Mar
y
An
ita
,
R Gee T
ha,
E Kan
nan.
"A
No
vel
H
y
br
id
Ke
y Ma
nag
em
ent Sch
e
me fo
r Establis
hi
ng
Secure
Comm
unic
a
tion
in W
i
reless S
ens
or
Net
w
orks".
W
i
reless P
e
rsonal Communications
. 20
15;
82(3): 14
19-
14
33.
[11]
R Blom. “
A
n
opti
m
a
l
cl
ass
of symmetric
key g
ener
atio
n syste
m
s
”. In
Proce
edi
ngs
of the
19
8
5
Eurocr
ypt W
o
r
kshop
Adv
anc
es Cr
ypt
o
lo
g
y
:
T
heor
y Ap
pl.
Cr
yptogr
aph
ic
T
e
chniques,
Li
nz, Austria
.
198
5: 335
–3
38
.
[12]
Z
Yu and Y Gu
an. “
A rob
u
st g
r
oup-
base
d
ke
y ma
na
ge
me
nt sche
m
e for w
i
r
eless se
nsor
netw
o
rks
”. In
Procee
din
g
s of
the 200
5 IEEE WCNC,
Ne
w
Orleans, USA. 200
5: 191
5–
19
20.
[13]
F
Banaie, SA
H Seno, R
H
Aljoufi, a
nd
R Budi
arto. “
MPKMS: A
Matrix-bas
ed
Pairwise Key
Mana
ge
me
nt S
c
he
me for W
i
r
e
less Se
nsor
Ne
tw
orks
”. In: Pro
c
eed
ings
of Int
e
rnati
ona
l C
onf
erenc
e o
n
Electrical E
ngi
neer
ing, C
o
mp
uter Scienc
e
and In
form
atic
s (EECSI 201
4), Yog
y
ak
arta
, Indones
ia.
201
4: 462-
467.
[14]
J Hua
ng, GH
Ou. “A Public
Ke
y
P
o
l
y
n
o
m
i
al
-b
ase
d
Ke
y
Pre-distrib
u
tio
n
Scheme for
Larg
e
-Scal
e
W
i
reless Se
ns
or Net
w
orks”.
Ad Hoc & Sens
or W
i
reless Ne
tw
orks Journal
.
2012; 1
6
(1-3):
45–6
4.
[15]
X
Du, Y
Xi
ao,
M Guiza
n
i, H
H
Ch
en. “An
effective ke
y
mana
geme
n
t
scheme for
he
teroge
ne
ou
s
sensor n
e
t
w
ork
”
.
Ad Hoc Netw
orks
. 2007; 5: 24-3
4
.
Evaluation Warning : The document was created with Spire.PDF for Python.