International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Highly Nonlinear Balanced Boolean Functions with very good Autocorrelation Property

Authors:
Subhamoy Maitra
Download:
URL: http://eprint.iacr.org/2000/047
Search ePrint
Search Google
Abstract: Constructing highly nonlinear balanced Boolean functions with very good autocorrelation property is an interesting open question. In this direction we use the measure $\Delta_f$ for a function $f$ proposed by Zhang and Zheng (1995). We provide balanced functions $f$ with currently best known nonlinearity and $\Delta_f$ values together. Our results for 15-variable functions disprove the conjecture proposed by Zhang and Zheng (1995), where our constructions are based on modifications of Patterson-Wiedemann (1983) functions. Also we propose a simple bent based construction technique to get functions with very good $\Delta_f$ values for odd number of variables. This construction has a root in Kerdock Codes. Moreover, our construction on even number of variables is a recursive one and we conjecture (similar to Dobbertin's conjecture (1994) with respect to nonlinearity) that this provides minimum possible value of $\Delta_f$ for a function $f$ on even number of variables.
BibTeX
@misc{eprint-2000-11391,
  title={Highly Nonlinear Balanced Boolean Functions with very good Autocorrelation Property},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / boolean function},
  url={http://eprint.iacr.org/2000/047},
  note={ subho@isical.ac.in 11479 5 Jun 2001},
  author={Subhamoy Maitra},
  year=2000
}