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

该项目考虑在信息理论中具有基础和广泛重要性的结构的创建和分析，包括通信，传感和信息安全。 通信网络和测距系统（雷达、声纳和导航）的协议需要序列族，这些序列族通常是由符号0和1组成的字，并且必须尽可能不相关。 也就是说，这些序列不应该像彼此的延时版本，甚至也不应该像它们自己的延时版本。 序列和其自身的延迟版本之间缺乏相似性有助于同步和定时，这在测距中是有用的。 两个不同的序列（以及它们的时间延迟版本）之间缺乏相似性可以防止通信网络中不同用户之间的混淆。 随机序列很难使用，并且偶尔会有巧合的相似性，所以最好使用看似随机但实际上具有深层结构的序列。 这些被称为伪随机序列，其中许多与其他对象有关，称为布尔函数，在密码学中很重要。 在这里，深层结构允许有效的加密和解密，但明显的随机性避免了容易检测到的模式，可以利用这些模式来破解代码。 这些伪随机结构在纠错码、天线阵列、科学仪器和声学设计中有进一步的应用，因此理解它们具有科学和技术的重要性。 本项目是对这些序列和函数的研究，同时也是学生参与研究的机会，这将为他们在计算、工程、科学和数学领域的进一步学习和工作做好准备。本项目的目标是发现和研究序列、布尔函数和相关的数学结构，这些结构在信息论中具有重要意义。 该项目将研究序列族的相关谱，特别是关于决定它们在通信和遥感应用中的性能的特性。 本项目还将研究布尔函数及其相关函数，特别是最简单的函数，如有限域幂映射，它们通常用作加密原语。特别注意将支付给沃尔什频谱，这决定了布尔函数的非线性，从而他们的弹性线性密码分析攻击。 这将通过对布尔函数的微分谱的研究来增强，这决定了它们对微分密码分析的抵抗力。 在每种情况下，目标都是更好地理解已知的序列和布尔函数，并指导搜索具有上级性能的新示例。 该项目将包括经验调查（计算相关性、沃尔什和差分光谱以确定性能）和理论分析，这反过来又为下一步的研究提供指导。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.