The covering radius of an error correcting code C is the smallest integer r such that every vector is within Hamming distance   r of at least one codeword. This concept is closely related to various basic properties of codes. It has been extensively studied for decades by coding theorists.

This talk will concern a new generalization, the multicovering radius. For any integer m, the m-covering radius is the smallest integer r such that every set v₁ ,..., v_m of m vectors is within Hamming distance rof a single codeword. That is, for all v₁, ... , v_m, there exists a u in C such that for each i, dist(v_i,u) is at most r. When m is 1, this is the ordinary covering radius. This concept arose in a recent study of the existence of secure cryptosystems of a certain type. It was shown that cryptosystems of this type that resist a very general type of cryptanalytic attack exist if there is a code with small multicovering radius whose codewords can be efficiently generated.

We describe the basic properties of the multicovering radii of codes, including a variety of general upper and lower bounds. We derive bounds on the multi-covering radii of Reed-Muller codes that can be used to solve the cryptanalytic question mentioned above. In particular we show that there exist families of sequence B¹, B², ... that is secure against every cryptanalytic algorithm that attempts to predict p + p^e bits of a sequence ( e > 1/2) given a short prefix.

Some of this work is joint with Iiro Honkala.

Back to Workshop Schedule