Minimum Distance between Bent and 1-resilient Boolean Functions

Soumen Maity; Subhamoy Maitra

Paper 2003/133

Minimum Distance between Bent and 1-resilient Boolean Functions

Soumen Maity and Subhamoy Maitra

Abstract

In this paper we study the minimum distance between the set of bent functions and the set of 1-resilient Boolean functions and present a lower bound on that. The bound is proved to be tight for functions up to $10$ input variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of $1$ -resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied upto $12$ -variable functions and we show that the construction provides a large class of $1$ -resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of $8$ -variable, $1$ -resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from variables and above, where we need to go for complicated combinatorial analysis with trial and error using computational facility.

Note: Some proofs are now written more carefully after getting the review comments from FSE 2004.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Accepted in FSE 2004
Keywords: Boolean Functions
Contact author(s): subho @ isical ac in
History: 2004-01-24: last of 2 revisions; 2003-07-17: received; See all versions
Short URL: https://ia.cr/2003/133
License: CC BY

BibTeX

@misc{cryptoeprint:2003/133,
      author = {Soumen Maity and Subhamoy Maitra},
      title = {Minimum Distance between Bent and 1-resilient Boolean Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/133},
      year = {2003},
      url = {https://eprint.iacr.org/2003/133}
}