CIF: Small: RUI: Highly Nonlinear and Pseudorandom Structures for Communications and Sensing

The University Corporation, Northridge, Northridge CA

Investigators

Abstract

This project considers the creation and analysis of structures that are of fundamental and wide importance in information theory, including communications, sensing, and information security. Protocols for communications networks and ranging systems (radar, sonar, and navigation) require families of sequences, which are typically words composed of the symbols 0 and 1, and which must be as uncorrelated as possible. That is, the sequences should not resemble time-delayed versions of each other, nor even of themselves. Lack of resemblance between a sequence and delayed versions of itself aids in synchronization and timing, which is useful in ranging. Lack of resemblance between two different sequences (and their time-delayed versions) prevents confusion between different users in communications networks. Random sequences are difficult to use and have occasional coincidental resemblances, so it is better to use sequences that appear random but actually have a deep underlying structure. These are called pseudorandom sequences, and many of them are related to other objects, called Boolean functions, that are significant in cryptography. Here the deep structure allows efficient encryption and decryption, but the apparent randomness avoids easily detectable patterns that could be exploited to break the code. These pseudorandom structures find further applications in error-correcting codes, antenna arrays, scientific instrumentation, and acoustic design, so understanding them is of scientific and technological importance. This project is an investigation into these sequences and functions and, at the same time, an opportunity for students to participate in research that will prepare them for further studies and work in computing, engineering, scientific, and mathematical fields. The goal of this project is to discover and investigate sequences, Boolean functions, and related mathematical structures of significance in information theory. This project will investigate correlation spectra of families of sequences, especially with regard to properties that determine how well they can perform in communications and remote sensing applications. This project will also study Boolean functions and their relatives, especially the simplest ones like finite field power maps, which are often employed as cryptographic primitives. Special attention will be paid to Walsh spectra, which determine the nonlinearity of Boolean functions, and thus their resilience to linear cryptanalytic attack. This will be augmented by a study of the differential spectra of Boolean functions, which determine their resistance to differential cryptanalysis. In each case, the goal is to understand better the sequences and Boolean functions that are already known, and to guide the search for new examples with superior performance. The project will involve both empirical investigation (calculation of correlation, Walsh, and differential spectra to determine performance) and theoretical analysis, which in turn provides guidance for where to look next. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.