Algebraic Feedback Shift Registers

Theoretical Computer Science 226 (1999) 61-93.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
Jinzhong Xu, University of Kentucky

Abstract A general framework for the design of feedback registers based on algebra over complete rings is described. These registers generalize linear feedback shift registers and feedback with carry shift registers. Basic properties of the output sequences are studied: relations to the algebra of the underlying ring; synthesis of the register from the sequence (which has implications for cryptanalysis); and basic statistical properties. These considerations lead to security measures for stream ciphers, analogous to the notion of linear complexity that arises from linear feedback shift registers. We also show that when the underlying ring is a polynomial ring over a finite field, the new registers can be simulated by linear feedback shift registers with small nonlinear filters.

Index Terms -- cryptography; feedback shift register; complete ring; stream cipher; pseudo-random number generator.