Information Technology Reference
In-Depth Information
Table 2.
Best known
µ
(
b
)forlarge
v
v
max known
µ
(
b
) Min weight attaining max
µ
(
b
)
40
12
19
60
18
30
100
28
48
200
55
100
300
81
150
of this set as much as possible, subject to the condition that strength does not
decrease (i.e. that there is no
d
for which
μ
d
decreases to
μ
(
b
i
)
−
1). If local
improvement is impossible, we flip two bits at random.
In order to implement this search, note that it is not necessary to recompute
q
from scratch for every vector at Hamming distance 1 from
b
i
.Instead,foreach
bit position
i
and for each tight distance
d
, we can compute in constant time
the effect on
μ
d
of flipping bit
i
. Table 2 gives the strengths of the best vectors
found in this manner.
4 More General Independence Conditions
More generally we may consider conditions of the following form: for parameters
(
r, r
), require that loss of any
r
messages does not prevent authentication of
more than
r
remaining messages. The problem considered above is the special
case
r
=1
,r
= 0. In the general case we have the following: for any set
A
with
#
A
=
r
, there can be no more than
r
indices
i
∈
A
such that
#
{
j
|
i
∈
S
j
,A
∩
S
j
=
∅}
<q.
This is a dicult condition to deal with in general, so we still consider some
special cases, and still consider only the sliding-window approach. If we have
r
= 1 but
r
>
0, then we no are no longer maximizing the minimum value of
μ
d
; instead we seek to maximize the (
r
+1)
th
smallest value. The
r
smallest
values correspond to the
r
messages for which we are allowed to loose full
authentication.
If we have
r>
1and
r
= 0, then we require that the loss of any set of
r
messages does not prevent authentication of any other message. For this case we
define
μ
(
d
1
,d
2
,···d
r
)
as the number of indices
j
where
b
j
=1
,b
j
+
d
1
=
=
b
j
+
d
r
=
0, and maximize
q
r
(
b
)=min
μ
d
over all vectors
d
, where we may assume
i<j
implies
d
i
<d
j
since order does not matter. Note that the
d
i
may be negative.
Trivialy we have
···
v
+
r
r
+1
q
r
(
b
)
≤
(14)
since every realization of
d
=(1
,
2
,
r
) (except at
b
v−
1
= 1) consists of a 1
followed by
r
zeros, and these cannot overlap. Table 3 gives the best known
values of
q
2
for various memory bounds
v
; in general these can be attained while
simultaneously coming close to the best known
q
=
q
1
.
···
