Distance-Avoiding Sequences for Extremely Low-Bandwidth Authentication - Sequences and Their Applications-SETA 2008 - page 236

3.2 Optimal Sequences for Small Memory Bounds

For small values of v , optimal sequences can be found by exhaustive search; re-
sults are summarized in Table 1. Only “critical” values are shown, i.e. v at which
the maximum μ ( b ) changes. These results show that the bound of Theorem 1
can be attained for small v . For all lengths except v = 35, the table gives the
lexicographically smallest vector attaining max μ ( b ). Exhaustive search was not
completed for v = 35, but μ ( b ) = 11 is still known to be optimal; if we had b of
length 35 attaining μ ( b ) = 12, we could remove one bit to obtain μ ( b ) = 11 at
length 34, which has been ruled out by exhaustive search.
Note that most of these optimal values cannot be attained by the difference-
set constructions of Sect. 3.1. For example, a difference set of size 31 would give
μ ( b ) 9. Furthermore, a sequence attaining μ ( b )=10with v =31couldnot

be obtained by truncating a block of consecutive zeros from a larger difference
set; the larger difference set would have

≤

v +1
4

=10thus v = 39, but no cyclic

difference set of that size exists.
As a secondary objective, we could seek to minimize the Hamming weight
of b : this weight is the number of messages that must be combined to compute
each authentication tag, so reducing this weight may reduce the amount of work
needed to compute a i . For all v in this table (except v = 21 and possibly v = 35)
exhaustive search confirms that there are no optimal vectors with weight less
than

v
2 .

3.3 Iterative Improvement of Windows

Starting with a random binary vector b 0 , we can attempt to maximize q by
iterative local improvement. At each step, we change one bit of the current
solution b i . If we can attain μ ( b i +1 ) >μ ( b i ) by flipping a single bit, we do this
(note that a single bit change cannot increase the strength of the vector by
more than 1, since it cannot change any μ d by more than 1). If such immediate
improvement is not possible, we consider the set of distances d which are tight,
i.e. which have μ d = μ ( b i ). The local optimization criteria is to reduce the size

Table 1. Optimal windows for small v

v max µ ( b ) an optimal vector

4 2 1101

7 3 1100101

10 4 1101010011

14 5 11100101011001

17 6 11100101100110101

21 7 111000101011010011001

24 8 111000101101001100110101

27 9 111001010101100101100011011

31 10 1111000110101001100110100110101

35 11 11010100100111100110001011001010111