Image Processing Reference
In-Depth Information
no more than λ nodes are compromised, the information obtained from these nodes cannot be used
to compute keys to be used between pairs of uncompromised nodes. The scheme first constructs a
(
,where
N
is the size of the network. The matrix
G
is assumed to be known to all nodes (actually, each node needs to know one column of G). To save
memory,thematrixcanbeconstructedinaspecialwaysothatnodescancomputeitfromasmall
set of parameters and do not need to store it [MS]. Let
q
be the smallest prime that is larger than
keylength
. The construction supports networks up to size
q
,asithastobeensuredthat
N
λ
+
)×
N
matrix
G
over a finite field
GF
(
q
)
<
q
.Let
that is by computing
s
i
for all
i
between and
s
be a “generator” of the group
GF
(
q
)
∣
GF
(
q
)∣
the
whole group
GF
(
q
)
can be enumerated. he matrix
G
canbecomputedaccordingtothefollowing
equation:
⎛
⎜
⎝
⎞
⎟
⎠
s
s
s
N
s
s
s
s
s
N
G
=
(
)
(
)
(
)
...
...
...
...
s
λ
s
λ
s
λ
s
N
λ
(
)
(
)
(
)
s
j
.
G
is thus a Vandermonde matrix
with
s
,
s
,...,
s
N
being all distinct. It has been shown that under these conditions the matrix has
maximum rank and any λ
s
i
As
s
is a generator of
GF
(
q
)
,itholdsthat
i
≠
j
⇒
≠
columns are linearly independent. For the purposes of Blom's key pre-
distribution scheme, it is sufficient that each node knows one column of this matrix, so that a node
k
only needs to store
s
k
to be able to compute the column of interest to it.
To set up the scheme, a random
+
(
λ
+
)×(
λ
+
)
symmetric matrix
D
over
GF
(
q
)
is constructed
T
with
T
being the transpose of matrix
and used to compute the
N
×(
λ
+
)
matrix
A
∶=(
D
⋅
G
)
(
D
⋅
G
)
(
.hematrix
D
is to be kept secret from all adversaries and sensor nodes. Each sensor node
will only learn one row of matrix
A
. Due to the fact that
D
is symmetric,
A
D
⋅
G
)
⋅
G
also is a symmetric
matrix as
T
G
T
D
T
G
T
G
T
A
T
T
A
⋅
G
=(
D
⋅
G
)
⋅
G
=
⋅
⋅
G
=
⋅
D
⋅
G
=
⋅
=(
A
⋅
G
)
Let
K
K
j
,
i
.hevaluesofthis
matrix represent the keys to be used between node
i
and node
j
.Tobeabletogeneratekeyswith
arbitrary peer nodes, node
k
stores the
k
th row of matrix
A
and the
k
th column of matrix
G
or
s
k
,
respectively. When two nodes
i
and
j
want to establish a pairwise secret key, they exchange their
values
s
i
and
s
j
,respectively,andusethereceivedcolumnofmatrix
G
together with their own row
of matrix
A
to compute the element
K
i
,
j
∶=
A
⋅
G
be the resulting symmetric matrix, so we know that
K
i
,
j
=
=
K
j
,
i
of matrix
A
⋅
G
. his scheme is secure as long as any
λ
columnsofmatrix
G
are linearly independent and no more than λ rows of matrix
A
are known
to the attacker [Blo].
Du et al. have proposed a scheme in [DDHVa] that combines Blom's scheme with the proba-
bilistic key distribution idea of Eschenauer and Gligor. Instead of generating one random symmetric
matrix
D
, they propose to generate ω matrices
D
,
D
,...,
D
ω
and to randomly select τ matrices
for each node and store one row of the corresponding matrices
+
T
in the node. If two nodes
i
and
j
want to establish a pairwise key, they first exchange the indices of the matrices from which
they have stored one row each. If they find a common index, they share a common key space and can
establish a pairwise key according to Blom's scheme. As compromise of a sensor node only reveals
one row of each matrix, an attacker first needs to compromise enough sensor nodes to obtain at least
λ
(
D
l
⋅
G
)
rows from one key space before he can calculate other keys from this key space.
The probability that an attacker succeeds in compromising one key space depends on the parame-
ters ω and τ, and Du et al. give an analysis for this in [DDHVa]. As in the original scheme, pairwise
keys are suggested to be set up between neighboring nodes, however, ω and τ have to be chosen so
+
