The Multicovering Radii of Codes

这项拨款的目的是支持与纠错码和流密码相关的新概念的研究。伪随机二进制序列通过在消息中引入冗余来纠正存在噪声的错误，并通过在消息中引入伪随机噪声来保证安全性。本研究涉及伪随机序列和使它们对编码和密码学有用的基本性质。码的覆盖半径是最小的半径，使得给定长度的每个向量都包含在以码字为中心的该半径的至少一个球体中。它是一项基本的法典措施，与许多其他措施密切相关。覆盖半径已被广泛研究了约25年。多重覆盖半径通过要求多个向量同时被码字覆盖来推广覆盖半径。这个新概念源于对流密码存在的调查，这些流密码可以抵抗所有可能的一般类型的密码分析攻击。主要研究者将研究码的多重覆盖半径的基本性质，如特定码的多重覆盖半径和具有各种性质的码的界。本研究计划的结果将是对伪随机序列的性质有一个更好的基本理解，使它们适合用于加密流密码。它还将提高我们对纠错码的基本理解，并可能改进此类码的设计和分析。

The purpose of this grant is to support research on a new concept related to error correcting codes and stream ciphers. Pseudorandom binary sequences are used for error correction in the presence of noise by introducing redundancy to messages and for security by introducing pseudorandom noise to messages. This research concerns pseudorandom sequences and the fundamental properties that make them useful for coding and cryptography. The covering radius of a code is the smallest radius such that every vector of the given length is contained in at least one sphere of that radius centered at a codeword. It is a fundamental measure of codes, closely related to many other measures. Covering radii have been extensively studied for some 25 years. The multicovering radii generalize covering radii by asking that several vectors be covered simultaneously by codewords. This new concept arose from an investigation of the existence of stream ciphers that resist all possible cryptanalytic attacks of a very general type. The principal investigator will study basic properties of multicovering radii of codes such as the multicovering radii of specific codes and bounds on codes with various properties. The result of this research program will be a better fundamental understanding of pseudorandom sequences with respect to properties that make them suitable for use in cryptographic stream ciphers. It will also lead to improvements in our fundamental understanding of error correcting codes and perhaps to improved design and analysis of such codes.