Bounds for the multicovering radii of Reed-Muller codes with applications to stream ciphers (Q5937081)

The \(m\)-covering radius of a code \(C\) is the smallest integer \(t\) such that, for every \(m\) vectors of the ambient space, there is a ball of radius \(t\) centred at a codeword of \(C\) containing all of them. Bounds are found for the multicovering radii of first-order Reed-Muller codes \(\text{RM}(1,r)\). In particular, it is shown that if \(m= 2^{2t+1}\), then for all \(s\geq t\geq 0\), the \(m\)-covering radius of \(\text{RM}(1,2s)\) equals \(2^{2s-1}+ 2^{s+t-1}\); and that if \(m= 2^{2t}\), \(t> 0\), and \(s\geq t-1\), then the \(m\)-covering radius of \(\text{RM}(1,2s+ 1)\) equals \(2^{2s}+ 2^{s+ t-1}\). The results of the paper are used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that led to the invention of the notion of multicovering radii.