Theory and Application of Algebraic Feedback Shift Registers

A Project Summary This is an interdisciplinary project involving a collaboration between a computer scientist, A. Klapper and a pure mathematician, M. Goresky. Its goal is the development of theoretical tools for the design and generation of pseudorandom sequences for a variety of applications in communications and computation. A major portion of the funding is directed towards the education and training of graduate students in Kentucky. Broader impact. Pseudorandom sequences are an essential part of the infrastructure on which digital communications and information technology is built. Pseudorandom sequences are used as randomizing keys in stream cipher cryptosystems to mask communications from eavesdroppers. They are used as spreading codes in spread spectrum systems such as digital cellular telephones, GPS signals, and satellite communications. They are used for frequency-hopping in radar and radio systems for protection against jamming. They are used as codewords in error-correcting codes, essential for compact disks, DVD players, and other forms of communication between digital devices. Pseudorandom sequences of large numbers are key ingredients in large simulations and other quasi-Monte Carlo (QMC) applications such as reactor design, oil well exploration, radiation cancer therapy, traffic flow, pricing of financial instruments, and VLSI design. In each of these cases, a particular pseudorandom sequence with particular properties must be chosen or custom designed for the application. Yet only a few general methods for fast, efficient generation of pseudorandom sequences are currently known, most of which are not very secure. The research proposed here is directed towards the development and analysis of a large supply of pseudorandom sequences for a variety of applications in cryptography, coding theory, and simulations. The Principal Investigator is the only university faculty member in Kentucky actively involved in cryptographic research. This grant will help support the education of young researchers in this vital field, including graduate students from the underrepresented state of Kentucky. This proposal will also support the writing of a textbook on algebraically defined pseudo-random sequences. Technical description Because they are fast and easily implemented in hardware, linear feedback shift registers (LFSR) have traditionally been used for pseudorandom sequence generation. However, it is difficult to guarantee the security of these systems. Despite forty years of research, only minimal progress has been made in understanding other architectures such as nonlinear feedback shift registers. During the period 1993-97 the Principal Investigator and M. Goresky proposed a new architecture, the "feedback-with-carry shift register" (FCSR) which is also easily implemented in hardware and which may be used to rapidly generate pseudorandom sequences with many desirable properties. A similar construction, the "multiply-with-carry" generator (MWC), was independently discovered by Marsaglia, Couture and L'Ecuyer for use in QMC. Thanks, in part, to NSF funding, many basic properties of FCSR sequences have been determined, and a huge class of pseudorandom sequence generators, algebraic feedback shift registers (AFSRs), has been discovered, which promise to vastly increase our supply of pseudorandom sequence. Their analysis depends on sophisticated modern mathematical techniques. This project will address issues concerning FCSR and AFSR sequences including (1) design of FCSR-MWC generators for fast and efficient generation of pseudorandom numbers with good statistical properties for use in QMC, (2) design of "combiners", "feedforward functions", and clock-controlled circuits for the generation of cryptographically secure sequences, (3) analysis and design of new AFSR generators with applications to stream ciphers and QMC, (4) development of new families of error correcting block and convolutional codes based on AFSR sequences, and (5) the further investigation of theoretical issues related to FCSRs and AFSRs. 1