CIF: Small: Primitives for Cryptography and Communication

This is an interdisciplinary collaboration between a computer scientist, A. Klapper, and a mathematician, M. Goresky. Its goal is the development of tools for the design and analysis of highly nonlinear functions and pseudorandom sequence generators for use in cryptographic systems (block and stream ciphers) and other areas of communications and computing. A major portion of the funding is directed towards the education and training of graduate students in Kentucky. Broader Impact. Stream ciphers and block ciphers are essential tools for sending all but the smallest amounts of data securely. They are used for very high volumes of data, such as video on (kmawl and di!-';ital tdephony, as well as moderate volumes of data such as JPEG files on the internet. In both stream and block ciphers, linear components such as linear feedback shift registers and bit permutations are used because they are extremely fast and can be made to produce excellent randomness properties. Yet these components are vulnerable to attacks that exploit the linearity. To foil the:;e attacks, highly nonlinear Boolean function:; are u:;ed as filters in various ways. The purpose of this grant is to study highly nonlinear functions and pseudorandom sequence generators for use in cryptography. There is a long cycle of cryptographers inventing new cryptosystems that foil all previous attacks, and cryptanalysts finding new attacks on the new systems. Whatever system we use with confidence now will need to be replaced eventually. It is essential that we be ready when the time comes with the tools for designing new systems. This grant will help develop those tools and will help provide a work force that has the knowledge to use them. Pseudorandom sequence generators are used in other areas, for example as spreading codes in spread spectrum systems, for frequency-hopping in radar and radio systems for protection against jamming, as codewords in error-correcting codes, in large simulations and other quasi-Monte Carlo applications. The research proposed here will have an impact in these areas as well as cryptography. 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. Intellectual Merit In a typical stream cipher very fast pseudorandom sequence generators are used. Their outputs and states are taken as inputs to a highly nonlinear combining function whose output is used as a keystream. The keystream is then added symbol by symbol to the message to produce the cipher. A receiver with an identical, synchronized sequence generator is able to recover the message. The statistical randomness of the keystream protects against attacks based on statistical bias, and the complexity of the combining function, as measured by various nonlinearity measures, protects against various known attacks. In a block cipher, the input is modified through a series of rounds. Each round commonly consists of linear mixing operations plus some highly nonlinear function applied to small blocks of input symbols. Again, nonlinearity properties of the functions lead to resistance to various attacks. We propose to (1) develop new nonlinear functions that have desirable cryptographic properties (bentness, resilience, correlation immunity, algebraic immunity, etc.); (2) develop new methods of analysis of nonlinear functions based on with-carry analogs of older methods (e.g., an arithmetic Walsh transform); (3) continue our study of algebraic methods of sequence generation - e.g., find conditions on algebraic feedback shift registers that guarantee a high degree of randomness; and (4) develop new stream ciphers based on algebraic feedback shift registers. Keywords: Cryptography; Pseudorandom sequences; Stream cipher; Shift registers; Boolean functions.