Constructing S-boxes that are inherently resistant against side-channel attacks is an important problem in cryptography. By using an optimal distinguisher under an additive Gaussian noise assumption, we clarify how a defender (resp., an attacker) can make side-channel attacks as difficult (resp., easy) as possible, in relation with the auto-correlation spectrum of Boolean functions. We then construct balanced Boolean functions that are optimal for each of these two scenarios. Generalizing the objectives for an S-box, we analyze the auto-correlation spectra of some well-known S-box constructions in dimensions at most 8 and compare their intrinsic resiliency against side-channel attacks. Finally, we perform several simulations of side-channel attacks against the aforementioned constructions, which confirm our theoretical approach.

Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [ IEEE Trans. Inform. Theory, 64 (2018), pp. 393--402] by modifying the $\mathcal{PS}_{ap}$ class of bent functions. The basic ideas used in Tang--Maitra construction were derived from a modification of a subclass of bent functions which is defined over the finite field, and a concern was raised in the same paper whether the implementation of such functions will be as efficient as that of Maiorana--McFarland type bent functions. In this paper, we look at the concrete realization of such functions over a vector space and answer the question positively. The first part of this paper investigates how the finite field implementation of the functions can be viewed as simple truth tables. Next, we present a completely new construction that itself starts from Maiorana--McFarland bent functions which are straightforward concatenations of linear functions.

Construction of Boolean functions on an odd number of variables with nonlinearity exceeding the bent concatenation bound is one of the most difficult combinatorial problems within the domain of Boolean functions. This problem also has deep implications in coding theory and cryptology. Patterson and Wiedemann demonstrated instances of such functions back in 1983. For more than three decades efforts have been channeled into obtaining such instances. For the first time, in this paper we explore nontrivial upper bounds on nonlinearity for such classes of functions that are invariant not only under several group actions but also for larger sets of functions than what have been considered so far. Further, we present tight upper bounds on the nonlinearity in several cases. To support our claims, we present computational results for functions on $n$ variables, where $n$ is an odd composite integer in the interval [9, 39]. In particular, our results for $n = 15$ and 21 are of immediate interest given recent research results in this domain. In addition to the upper bounds, we also discover the nonlinearities that can actually be achieved above the bent concatenation bound for such a class of functions. Finally, we obtain all possible values in the absolute Walsh spectra of the functions considered.

Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on 5 × 3 = 15 variables that are invariant under the actions of the cyclic group GF(25)*· GF(23)* as well as the group of Frobenius automorphisms. Some of these Boolean functions possess nonlinearity greater than the bent concatenation bound. The next possible option for exploring such functions is on 7 × 3 = 21 variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for the first time.

For the first time Boolean functions on 9 variables having nonlinearity$241$are discovered, that remained as an open question in literature for almost three decades. Such functions are found by heuristic search in the space of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on$n$(odd) variables having nonlinearity$> 2^{n-1} - 2^{{ n-1}\over { 2}}$if and only if$n > 7$. Using similar search technique, balanced Boolean functions on 9, 10, and 11 variables are attained having autocorrelation spectra with maximum absolute value$< 2^{\lceil {{ n}\over { 2}}\rceil }$. On odd number of variables, earlier such functions were known for 15, 21 variables; there was no evidence of such functions at all on even number of variables. In certain cases, our functions can be affinely transformed to obtain first-order resiliency or first-order propagation characteristics. Moreover, 10 variable functions having first-order resiliency and nonlinearity$492$are presented that had been posed as an open question at Crypto 2000. The functions reported in this paper are discovered using a suitably modified steepest descent based iterative heuristic search in the RSBF class along with proper affine transformations. It seems elusive to get a construction technique to match such functions.