The Multicovering Radii of Codes

点击翻译按钮获取中文摘要

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.