Mandal, Bimal

It is known that the smaller the values of Gowers U2 and U3 norms of a Boolean function, the greater its strength against linear and quadratic approximations. This article gives recursive relation between the Gowers U2 and U3 norms of Boolean functions and their restriction to hyperplanes. These results will help analyze the second and third-order Gowers norms of Boolean functions in a higher number of variables.

The th order Gowers norm of a Boolean function is a measure of its resistance to rth order approximations. Gowers, Green, and Tao presented the connection between Gowers uniformity norm of a function and its correlation with polynomials of a certain degree. Gowers and norms measure the resistance of a Boolean function against linear and quadratic approximations, respectively. This paper presents computational results on the Gowers norms of some known 4, 5, and 6-bit S-Boxes used in the present-day block ciphers. It is observed that there are S-Boxes having the same algebraic degree, differential uniformity, and linearity, but their Gowers norms values are different. Equivalently, they possess different strengths against linear and quadratic cryptanalysis.

Balanced Boolean functions with high nonlinearity are considered as major cryptographic primitives in the design of symmetric key cryptosystems. Dobbertin, in early nineties, gave an explicit construction for balanced functions on (even) n variables, with nonlinearity 2n-1-2n2+nlb(n2), where nlb(t) is the maximum nonlinearity of a balanced Boolean functions in t variables and conjectured that nlb(n)≤2n-1-2n2+nlb(n2). This bound still holds. In this paper we revisit the problem. First we present a detailed combinatorial analysis related to highly nonlinear balanced functions exploiting the inter-related properties like weight, nonlinearity, and Walsh–Hadamard spectrum. Our results provide a general framework to cover the works of Sarkar-Maitra (Crypto 2000), Maity-Johansson (Indocrypt 2002), and Maity-Maitra (FSE 2004) as special cases. In this regard, we revisit the well-known construction methods through modification of bent functions and provide supporting examples for 8, 10, 12, and 14 variables. We believe these results will advance the understanding related to highly nonlinear balanced Boolean functions on even numbers of variables as well as the Dobbertin’s conjecture.