Information Technology Reference
In-Depth Information
messages are guaranteed to be received in order (i.e. if there is a direct radio
link from sender to receiver), and if we assume that no more than 2
k
consecutive
messages will ever be lost, then it is only necessary to transmit the
k
low-order
bits of
i
.
Of course it is not enough to simply require that each message appears
q
times. We are assuming a very low-power network with no acknowledgement or
retransmission protocol, no error-correction mechanism, and occasional loss of
connectivity. Thus we must expect that some messages will be lost, and if
m
j
is
lost, all tags
a
i
such that
j
S
i
will be useless. Therefore every message must
becontainedinmorethan
q
sets, to provide robustness against the expected
missing messages. The question then becomes, what conditions must we impose
on the sets
S
i
, and what is the optimal way to achieve those conditions?
We first consider the following requirement (more general requirements are
considered in Sect. 4): if any one message is lost, this must not prevent full
authentication of any other message. This means that for any pair of messages
m
i
,m
j
,wemusthaveatleast
q
sets which contain
m
i
but not
m
j
.Thusif
m
j
is
lost, we still have enough good tags to authenticate
m
i
with the desired degree
of security.
This “set-cover” approach requires the sender to remember many old mes-
sages. If a node can remember at most
v
old messages, then we must have
S
i
⊂
∈
v, i
] for all
i
. Memory is presumably quite limited since we are dealing
with very low-power nodes. Note that
v
is also the maximum delay before a
message finally achieves full authentication, which is another reason to limit
v
.
Thus we have the following problem: Given memory bound
v
, find sets
S
i
that
maximize
q
where
[
i
−
-
For each
i
∈
N
,
S
i
⊂
[
i
−
v, i
].
-
For each
i
=
j
there are at least
q
sets
S
with
i
∈
S
,
j
∈
S
.
Given a collection of sets
S
, define the
strength
of the collection as
Definition 1
μ
(
S
)=min
i,j
{
t
|
i
∈
S
t
,j
∈
S
t
}
#
(here #
A
denotes the size of a set
A
). We have defined
S
as an infinite collection;
such a collection would of course be specified either by rotating through a finite
collection of given sets, or more generally by specifying a way to generate
S
i
as a function of
i
. To get the process started, we can implicitly have dummy
messages
m
−v
,
···
m
−
1
,m
0
=0.
3 Sliding-Window Construction
We first consider the special case in which each set
S
i
is defined by a “sliding
window”; we select a set of distances
δ
=
{
δ
1
<
···
δ
k
≤
v
}
and let each
S
i
=
{
i
−
δ
1
,
···
i
−
δ
k
}
. Without loss of generality we can assume
δ
1
=0and
δ
k
=
v
.
