Theory and Application of Algebraic Feedback Shift Registers

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

Theory and Application of Algebraic Feedback Shift Registers Principal Investigator: Andrew Klapper, University of Kentucky Pseudorandom sequences essential for digital communications and information technology. They are used in stream cipher cryptosystems; in spread spectrum systems in cellular telephones, GPS systems, and satellite communications; and as codewords in error-correcting codes for digital communication. Pseudorandom sequences of large numbers are used in large simulations for such applications as weather prediction, reactor design, oil well exploration, radiation cancer therapy, traffic flow, and pricing of financial instruments. In each case sequences with particular properties are needed. Yet few general methods for efficient generation of pseudorandom sequences are known. This research involves the development and analysis of a large supply of pseudorandom sequences for a variety of applications in cryptography, coding theory, and simulations. In 1994 A. Klapper and M. Goresky proposed "feedback-with-carry shift registers" (FCSRs), a class of pseudorandom generators which are easily implemented and which rapidly generate pseudorandom sequences with many desirable properties. These were later generalized to algebraic feedback shift registers (AFSRs). Many basic properties of FCSRs and AFSRs have been determined. This project addresses issues concerning FCSR and AFSR sequences including (1) design of "combiners", "feedforward functions", and clock-controlled circuits for the generation of cryptographically secure sequences, (2) design of fast and efficient FCSRs with good statistical properties for use in quasi-Monte Carlo (QMC), (3) analysis and design of several new AFSR generators with applications to stream ciphers and QMC, (4) solution of the register synthesis problem for AFSRs, and (5) development of new families of error correcting block and convolutional codes based on AFSR sequences.