Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

Designs, Codes, and Cryptography 23 (2001) 131-145.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
Iiro Honkala, University of Turku

Abstract The multicovering radii of a code are recent generalizations of the covering radius of a code. For positive m, the m-covering radius of C is the least radius t such that every m-tuple of vectors is contained in at least one ball of radius t centered at some codeword. In this paper upper bounds are found for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classical covering radii of first order Reed-Muller codes. They are exact in some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study of multicovering radii of codes.

Index Terms -- Error correcting code, stream cipher, covering radius, Reed-Muller code.