Principal Investigator: Andrew Klapper, University of Kentucky
Pseudorandom sequences and highly nonlinear functions are essential for digital communications and information technology. They are used in stream cipher cryptosystems, spread spectrum systems in cellular telephones, GPS systems, satellite communications, error-correcting codes for digital communication, and 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 or nonlinear functions with particular properties are needed. Yet few general constructions of high quality pseudorandom sequences and highly nonlinear functions are known. This research involves the development and analysis of a large supply of these tools for a variety of applications in cryptography, coding theory, and simulations.
In 1994 Klapper and Goresky proposed "feedback-with-carry shift registers" (FCSRs), pseudorandom generators which are easily implemented and which rapidly generate sequences with many desirable properties. These generalize to algebraic feedback shift registers (AFSRs). Many basic properties of FCSRs and AFSRs have been determined and they have been used in stream ciphers and quasi-Monte Carlo. This project addresses issues concerning FCSR and AFSR sequences including (1) The development of new classes of highly nonlinear functions for use in block ciphers and stream ciphers, (2) the development of new tools for the analysis of nonlinear functions based on the "with-carry" paradigm, (3) the solution of the "register synthesis problem" for AFSRs, (4) the identification of new classes of AFSR sequences with good randomness properties, and (5) the extension of various ideas and methods in cryptography to vector valued functions and sequence generators.
