Cryptology ePrint Archive: Report 2000/047

Highly Nonlinear Balanced Boolean Functions with very good Autocorrelation Property

Subhamoy Maitra

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.

Category / Keywords: secret-key cryptography / boolean function

Date: 5 Jun 2001

Contact author: subho at isical ac in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20051128:071013 (All versions of this report)

Short URL: ia.cr/2000/047

Discussion forum: Show discussion | Start new discussion