Volume 85, Numbers 1-2, 37-55, DOI: 10.1007/s00607-009-0041-z

On affine (non)equivalence of Boolean functions

Sugata Gangopadhyay, Deepmala Sharma, Sumanta Sarkar and Subhamoy Maitra

From the issue entitled "Special Issue on the occasion of the 8th Central European Conference on Cryptography"

View Related Documents

Abstract

In this paper we construct a multiset S(f) of a Boolean function f consisting of the weights of the second derivatives of the function f with respect to all distinct two-dimensional subspaces of the domain. We refer to S(f) as the second derivative spectrum of f. The frequency distribution of the weights of these second derivatives is referred to as the weight distribution of the second derivative spectrum. It is demonstrated in this paper that this weight distribution can be used to distinguish affine nonequivalent Boolean functions. Given a Boolean function f on n variables we present an efficient algorithm having O(n22n ) time complexity to compute S(f). Using this weight distribution we show that all the 6-variable affine nonequivalent bents can be distinguished. We study the subclass of partial-spreads type bent functions known as PS ap type bents. Six different weight distributions are obtained from the set of PS ap bents on 8-variables. Using the second derivative spectrum we show that there exist 6 and 8 variable bent functions which are not affine equivalent to rotation symmetric bent functions. Lastly we prove that no non-quadratic Kasami bent function is affine equivalent to Maiorana–MacFarland type bent functions.

Keywords  Bent functions - Affine equivalence - Nonlinearity

Mathematics Subject Classification (2000)  94A60 - 94C10 - 06E30


This paper is based on [12] and [13].

Fulltext Preview

Image of the first page of the fulltext document