Paper 2004/202

Covering Radius of the $(n-3)$-rd Order Reed-Muller Code in the Set of Resilient Functions

Yuri Borissov, An Braeken, and Svetla Nikova

Abstract

In this paper, we continue the study of the covering radius in the set of resilient functions, which has been defined by Kurosawa. This new concept is meaningful to cryptography especially in the context of the new class of algebraic attacks on stream ciphers proposed by Courtois and Meier at Eurocrypt 2003 and Courtois at Crypto 2003. In order to resist such attacks the combining Boolean function should be at high distance from lower degree functions. Using a result from coding theory on the covering radius of $(n-3)$-rd Reed-Muller codes, we establish exact values of the the covering radius of $RM(n-3,n)$ in the set of $1$-resilient Boolean functions of $n$ variables, when $\lfloor n/2 \rfloor = 1 \mod\;2$. We also improve the lower bounds for covering radius of the Reed-Muller codes $RM(r,n)$ in the set of $t$-resilient functions, where $\lceil r/2 \rceil = 0 \mod\;2$, $t \leq n-r-2$ and $n\geq r+3$.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. published at the the 25th Symposium on Information Theory in the Benelux
Keywords
covering radiusresilient functions
Contact author(s)
svetla nikova @ esat kuleuven ac be
History
2004-08-18: received
Short URL
https://ia.cr/2004/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/202,
      author = {Yuri Borissov and An Braeken and Svetla Nikova},
      title = {Covering Radius of the $(n-3)$-rd Order Reed-Muller Code in the Set of Resilient Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2004/202},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/202}},
      url = {https://eprint.iacr.org/2004/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.