Analogously to de Bruijn sequences, orientable sequences have application in automatic position-location applications and, until recently, studies of these sequences focused on the binary case. In recent work by Alhakim et al., a range of methods of construction were described for orientable sequences over arbitrary finite alphabets; some of these methods involve using negative orientable sequences as a building block. In this paper we describe three techniques for generating such negative orientable sequences, as well as upper bounds on their period. We then go on to show how these negative orientable sequences can be used to generate orientable sequences for every non-binary alphabet size and for every tuple length. In doing so we use two closely related approaches described by Alhakim et al. The periods of both negative orientable and orientable sequences that we construct are of the same order of magnitude as the upper bounds.

This paper describes new, simple, recursive methods of construction fororientable sequences, i.e. periodic binary sequences in which any$n$-tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine$n$consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Daiet al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences.

Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper, we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.

We consider unconditionally secure authentication codes where the adversary has access to a verification oracle that when presented with a message query gives a response of 1 or 0 if the query corresponds to an authenticated message or not, respectively.We define two types of attack, offline and online, and their two corresponding games. We define the advantage of the adversary in each game and obtain a lower bound on the maximum advantage when the adversary plays his optimal strategy. For each game, authentication codes that satisfy the lower bounds with equality are said to provide perfect protection and guarantee the minimum success chance for the attacker in the corresponding game. We prove that an optimal code for the offline attack is also an optimal code for the online attack. In both cases, we prove that perfect protection of order i implies perfect protection of order j for j < i and derive a lower bound on the number of keys for an optimal code. Finally we show that the encoding matrix of codes with perfect protection of order i and minimum number of keys correspond to a Steiner system.

A key assignment scheme is a cryptographic technique for implementing an information flow policy, sometimes known as hierarchical access control. All the research to date on key assignment schemes has focused on particular encryption techniques rather than an analysis of what features are required of such a scheme. To remedy this we propose a family of generic key assignment schemes and compare their respective advantages. We note that every scheme in the literature is simply an instance of one of our generic schemes. We then conduct an analysis of the Aki-Taylor scheme and propose a number of improvements. We also demonstrate that many of the criticisms that have been made of this scheme in respect of key updates are unfounded, finally, exploiting the deeper understanding we have acquired of key assignment schemes, we introduce a technique for exploiting the respective advantages of different schemes.

The purpose of this paper is to prove the equivalence of perfect authentication schemes and maximum distance separable codes.

Switching networks consisting of subscriber lines and crosswires connected by switches are considered. A connection between two subscribers is made along one crosswire via two switches. The minimum number of switches necessary for such a switching network to be rearrangeably nonblocking is determined and a switching arrangement which achieves this minimum for any (even) number of subscriber lines is constructed. Two procedures for assignment of crosswires to subscriber line pairs are described. One makes the correct choice of connection route without backtracking provided all connections are known beforehand; the other determines a rearrangement of existing assignments when a new connection is required. The switching networks which have the minimum number of switches for networks with up to eight subscriber lines and give nonisomorphic solutions for larger networks are characterized.>