## Grants and Contracts Details

### Description

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.

Status | Finished |
---|---|

Effective start/end date | 7/1/09 → 6/30/13 |

## Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.