Degree optimized resilient Boolean functions from Maiorana-McFarland class


Enes Pasalic
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Enes.Pasalic@inria.fr

To appear in the Proceedings of "IMA conference of Coding and Cryptography", Cirencester, England, December 2003.

Abstract

In this paper we present a construction method of degree optimized resilient Boolean functions with very high nonlinearity. We present a general construction method valid for any n greater than 4 and for order of resiliency less than or equal to n-3. The construction is based on the modification of the famous Marioana-McFarland class in a controlled manner such that the resulting functions will contain some extra terms of high algebraic degree in its ANF including one term of highest algebraic degree. Hence, the linear complexity is increased, the functions obtained reach the Siegentheler's bound and furthermore the nonlinearity of such a function in many cases is superior to all previously known construction methods. This construction method is then generalized to the case of vectorial resilient functions, that is for mappings with n input and m output. This provides functions of very high algebraic degree almost reaching the Siegenthaler's upper bound.

Keywords

Boolean Function, Resiliency, Nonlinearity, Algebraic Degree.