An error correcting code of length n is a set C of vectors in n -dimensional space over GF(2) . The covering radius of a code C is the smallest integer r such that every vector in GF(2)^n is within distance r of at least one code word in C. This notion plays a crucial role in coding theory and has been the subject of hundreds of papers over the past two decades (The notion of covering radius also arises in horserace betting pools. Some of the earliest results in the area were found by nonmathematicians and published in betting pool magazines!.) A critical step in the proof of one of the existence theorems in my paper On the Existence of Secure Keystream Generators requires the existence of a code with small covering radius each of whose code words can be generated by a fast feedback register. The Reed-Muller codes satisfy these requirements. This gives a result that says there exists a family of sequences that resists all attacks of the type studied, in the sense that each attack is wrong on close to half the bits for infinitely many sequences in the family.
A stronger result would say that every attack fails on all but finitely many of the sequences. It would then be possible for a cryptographer to choose a sequence that resists any given finite set of attacks. To prove such a result one needs a code with small {\em multicovering radius}. If m is a positive integer, then the m-covering radius of C is the smallest integer r such that for every set {v1,...,vm} in GF(2)^n , there is a vector c in C such that the distance from every vi to c is at most r . Surprisingly, this is a new concept, previously unstudied by coding theorists. In the paper The Multicovering Radii of Codes I have initiated its study. This paper describes the basic properties of multicovering radii and gives several lower and upper bounds. A natural question is, for a given r , m , and n , what is the smallest code whose m -covering radius is at most r ? As it turns out, there may be no such code. For example, if m\ge 2 , it is necessary that r be at least n/2 . In fact, the minimal r for which such a code exists is the m-covering radius of C=GF(2)^n . I have derived tight asymptotic bounds on these radii. I also derived tight asymptotic bounds on the m-covering radii of Hamming codes.