1998 Summer Program: Coding and Cryptography Week 1: Codes, Design, and Cryptography

Keyed permutation generators are essential components in many information integrity protocols. The generator described in this paper is the simplest instance in a family of such devices which lend themselves to simple high speed VLSI implementation.

Differentiation of n-bit binary sequences defines a family of digraphs in which the vertices are labeled with the sequences in a natural way. When n is a prime, the even Hamming weight sequences are all labels for vertices in simple cycles and the odd weight sequences are labels for vertices in isomorphic trees rooted on these cycles. The digraphs for composite n are easily derived from the digraphs for the prime factors of n. A simple alteration of the differentiation operation preserves the digraph structure but interchanges - and permutes - the odd and even labels. The 2-graph which results from combining these two digraphs is a surprisingly familiar structure in which every k-bit sequence can be caused to define a permutation on the n-bit sequences; i.e. the k-bit sequences "key" the generation of the permutations. The operation is invertible in the sense that given the key and an input sequence, the output sequence can be easily calculated, or given the key and the output sequence, the input sequence can be equally easily recovered.

The cycle structure for this keyed generation of permutations is shown to be isomorphic to the cycle structure for the iterative parity encoding of binary sequences -- a result that is both counterintuitive and the key to the analysis of the generators.

Following are the slides used during the presentation.

Slide 1

To view the rest of the slides click on the following:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40	41	42	43	44	45

• Press here to view or print a complete version
• Back to Workshop Schedule
• Institute for Mathematics and Its Applications home page