Improved cryptographic properties of Boolean functions obtained from the neighbourhood of Patterson-Wiedemann functions

Abstract

More than a decade ago, the balanced and 1-resilient Boolean functions on 15 variables with the best known nonlinearities 16272 and 16264, respectively, were identified by interpreting the Patterson-Wiedemann (PW) functions as rotation-symmetric Boolean functions (RSBFs) and performing a deterministic search in their neighbourhood. We here perform an efficient exhaustive search for all the RSBFs belonging to that neighbourhood and enumerate those with the best cryptographic properties, which yields some improvements in terms of algebraic degree, algebraic immunity, and absolute indicator. In the process, by considering the PW functions as 3-RSBFs, we attain balanced Boolean functions with nonlinearity 16268 and absolute indicator 192, which improve the previously best known result in terms of nonlinearity.

1 Introduction

The best known nonlinearity (16272) for balanced 15-variable Boolean functions was achieved in [1] by performing a deterministic search of the RSBFs, having zeros in their Walsh-Hadamard spectra, in the neighbourhood of the unbalanced PW functions [2] with nonlinearity 16276. Therefore, it is possible to construct balanced Boolean functions with nonlinearity $2^{n-1}-2^{\frac {n-1}{2}} +16\cdot 2^{\frac {n-15}{2}}$ for odd n ≥ 15, which is currently the best known for n ≤ 27 [3]. For n = 9 and 11, no balanced Boolean function with nonlinearity greater than the bent concatenation bound is known in the literature. For n = 13, modifying the truth table of an unbalanced Boolean function with nonlinearity 4040 (which is obtained using one of the 9-variable Boolean functions with nonlinearity 242 in [4]) by a heuristic search, the balanced nonlinearity 4036 was reached [5, 6]. Thus, one can construct balanced Boolean functions with nonlinearity $2^{n-1}-2^{\frac {n-1}{2}} +4\cdot 2^{\frac {n-13}{2}}$ for odd n ≥ 13; however, this nonlinearity is less than the one obtained in [1] for n ≥ 15. As evident from the mentioned results, transforming an unbalanced Boolean function (with no zero in the Walsh-Hadamard spectrum) to meet the balancedness property generally results in a decrease in its nonlinearity. One may expect a further decrease when it comes to constructing a resilient Boolean function, since we then need more zeros to introduce in the Walsh-Hadamard spectrum. Confirming this, a 1-resilient Boolean function with nonlinearity 16264 was demonstrated in [1] using a neighbour of the PW functions (i.e., an RSBF in their neighbourhood). This leads to the construction of 1-resilient Boolean functions with nonlinearity $2^{n-1}-2^{\frac {n-1}{2}}+8\cdot 2^{\frac {n-15}{2}}$, giving the highest known nonlinearity for n = 15, 17, and 19 [3]. Recall that for a t-resilient function, nonlinearity must be divisible by 2^t+ 1 [7], and thus it is theoretically possible to obtain 1-resilient Boolean functions with nonlinearity greater than 16264, but no such function is known in the literature. The existence of (any) resilient functions with nonlinearity greater than the bent concatenation bound is also unknown for odd n ≤ 13.

In this paper, we present the complete search results for the neighbourhood considered in [1] and obtain new Boolean functions having improved algebraic degree and absolute indicator properties than those of the previously demonstrated functions in [1]. Among them, we show the existence of 1-resilient Boolean functions with nonlinearity 16264 for which both the algebraic immunity and algebraic degree properties are optimal. Further, we improve the cryptographic properties of the balanced Boolean function with nonlinearity 16264 and the best known absolute indicator value 192 reported in [1]; most notably, its nonlinearity is improved to 16268 by interpreting the PW functions as 3-RSBFs. Table 1 shows the summary of our best achieved results compared with those of [1], where the quintuplet (NL,Δ,d,AI,t) indicates the profile of a Boolean function with nonlinearity NL, absolute indicator Δ, algebraic degree d, algebraic immunity AI, and resiliency order t (which takes zero for a balanced but not resilient Boolean function). The truth tables of all the Boolean functions found by our search can be obtained from [8].

Table 1 Comparison of our results with those of [1]

For the background on Boolean functions and their cryptographic properties, we like to refer the reader to [9]. In addition, the definitions related to the PW functions and (k −)RSBFs can be found in [1, 4, 10]. We mainly follow the notation in [1] with the difference that for the case of n-variable k −RSBFs, we use a superscript k for the orbits (${G_{n}^{k}}(\cdot )$), the number (${g_{n}^{k}}$) of orbits, the i-th orbit representative (${\Lambda }_{n,i}^{k}$), and the matrix ($_{n}\mathcal {A}^{k}$) of size ${g_{n}^{k}}\times {g_{n}^{k}}$, i.e., the superscript drops for the case of RSBFs.

2 Search method

Considering the PW functions as RSBFs, there are g₁₅ = 2192 orbits. Among them, the number of orbits of sizes 15, 5, 3, and 1 are 2182, 6, 2, and 2, respectively. The best known results are found in [1] by applying some specific four-orbit combinations, which raises a natural question: what are the best cryptographic properties for all possible four-orbit combinations? To answer this question, we here perform an efficient exhaustive search given by Algorithm 1. In the rest of this paper, we realize the PW functions as mappings $\mathbb {F}_{2}^{15}\rightarrow \mathbb {F}_{2}$ using the primitive polynomial p(β) = β¹⁵ + β + 1 over $\mathbb {F}_{2}$ and the normal basis $\{\alpha ^{29}, \alpha ^{2\cdot 29}, \ldots , \alpha ^{2^{14}\cdot 29}\}$, where α is a root of p(β).

Algorithm 1

Exhaustive search for the neighbourhood of the PW functions.

The inputs of the algorithm are one (f ) of the PW functions and its Walsh-Hadamard spectrum value (V_W) which is to be made zero. Clearly, the entries of the matrix $_{15}\mathcal {A}$ can take the values ± 1,± 3,…,± 15, because of the fact that the orbit size is an odd integer less than or equal to 15. Further, since the Walsh-Hadamard spectrum of each of the PW functions consists of the distinct values {− 216,− 88,40,168}, only the values 40 or − 88 can be made 0 by toggling four orbits, i.e., V_W can be either 40 or − 88. For instance, suppose W_f(Λ_15,j) = 40, 0 ≤ j < g₁₅, and

$$\begin{array}{@{}rcl@{}} (-1)^{f({\Lambda}_{15,i_{1}})}{{~}_{15}\mathcal{A}}_{i_{1}, j} + (-1)^{f({\Lambda}_{15,i_{2}})}{{~}_{15}\mathcal{A}}_{i_{2}, j} &&+ (-1)^{f({\Lambda}_{15,i_{3}})}{{~}_{15}\mathcal{A}}_{i_{3}, j} \\ &&+ (-1)^{f({\Lambda}_{15,i_{4}})}{{~}_{15}\mathcal{A}}_{i_{4}, j} =20 \end{array}$$

(1)

for the PW function f and some distinct orbit representatives ${\Lambda }_{15, i_{1}},\ldots , {\Lambda }_{15, i_{4}}$. Then, toggling f(x) for all $x\in G_{15}({\Lambda }_{15, i_{1}})\cup \ldots \cup G_{15}({\Lambda }_{15, i_{4}})$ makes W_f(Λ_15,j) = 0, which can also be deduced from Theorem 1 in [1]. Thus, we start by computing all possible combinations of the mentioned matrix entries making those two values zero and find that there are 73 and 15 such combinations for the values 40 and − 88, respectively, which are given by Table 2, where x^(y) denotes there are y entries with value x. In the algorithm, those combinations, each denoted by (i₀,…,i₁₅), are put into the array R for the given input V_W, where i_s represents the number of entries equal to v_s for all s ∈{0,1,…,15}, and (v₀,v₁,…,v₁₅) = (− 15,− 13,…,15). As an example, the combination (− 15⁽¹⁾,13⁽²⁾,9⁽¹⁾) corresponds to the element (1,0,0,0,0,0,0,0,0,0,0,0,1,0,2,0) of R. Note that the sum of any four entries of $_{15}\mathcal {A}$ can be at most 60 in absolute value, and thus it is required to toggle more orbits to convert the other values 168 and − 216 to 0, which, however, gives rise to a huge increase of the search space.

Table 2 All possible four-entry combinations of $_{15}\mathcal {A}$ whose sum is (a) 20 and (b) − 44

Let the matrix ${\mathcal{B}}=[{\mathcal{B}}_{i,j}]$ of size g₁₅ × g₁₅ be formed by ${\mathcal{B}}_{i,j} = (-1)^{f({\Lambda }_{15,i})}{{~}_{15}\mathcal {A}_{i,j}}$ as given in the algorithm. We then consider the orbit representatives at which the Walsh-Hadamard spectrum values are equal to V_W and for each of them, say Λ_15,i, we find the number t_s of the entries which are equal to v_s in the respective i th column of ${\mathcal{B}}$. The indexes of these columns of ${\mathcal{B}}$ and the vector (t₀,…,t₁₅) of the corresponding numbers for each of them are put into the arrays I and C, respectively. Note that a combination (i₀,…,i₁₅) (that is, an element of R) should be consistent with at least one element (t₀,…,t₁₅) of C, i.e., the condition i_s ≤ t_s for all s ∈{0,1,…,15} should be satisfied; otherwise, there is no column of ${\mathcal{B}}$ having the entries corresponding to that combination (which then cannot be exploited). Therefore, for each pair of (i₀,…,i₁₅) and (t₀,…,t₁₅) satisfying the above condition, we get ${\prod }_{s=0}^{15}{t_{s} \choose i_{s}}$ different choices of four orbits which are stored in the array D as their corresponding orbit representatives. This leads to the fact that toggling the outputs of the PW function f corresponding to any one of these choices makes the Walsh-Hadamard spectrum value V_W zero at one or more orbits. In other words, if (t₀,…,t₁₅) is the i th element of C satisfying i_s ≤ t_s, s ∈{0,1,…,15}, for an element (i₀,…,i₁₅) of R, then we get W_h(Λ_15,I[i]) = 0 after complementing the outputs of f corresponding to any four-orbit combination given by the array D; in addition, there is the possibility to get more zeros corresponding to some other orbits in the Walsh-Hadamard spectrum resulting from the same complementation. The algorithm generates all the RSBFs having zeros in their Walsh-Hadamard spectra by determining all possible pairs obtained from the arrays R & C, and checks whether the candidate function h can be used to obtain any one of the desired cryptographic properties (i.e., resiliency, nonlinearity, or absolute indicator) by an affine transformation. If one of them is achieved, then it is stored in the array STORE that is the output of the algorithm.

It can be computationally found that that for both of the PW functions, the number of combinations (shown by the superscript ^∗ in Table 2), which can be used to convert the Walsh-Hadamard spectrum value 40 (resp., − 88) to zero is 58 out of all 73 (resp., 5 out of all 15) combinations, which provides a reduction of around 24% of the search space (i.e., it reduces from ${2192 \choose 4} \approx 2^{39.8}$ to approximately 2^39.4).

3 Results

We have implemented Algorithm 1 on a workstation with two Intel Xeon CPU E5-2620v3 (2.40 GHz, 15MB cache, 6 cores) processors under Windows 8.1 Pro 64-bit operating system, which took one and a half days by exploiting all the cores. For the case of 3-RSBFs, with the same computer system, it takes two weeks to complete the search performed by suitably modifying the algorithm.

3.1 Balanced functions with nonlinearity 16272

Let $f_{PW_{1}}$ and $f_{PW_{2}}$ be the PW functions with algebraic degrees 8 and 9, respectively, and h represent the RSBF obtained by toggling the outputs of one of the PW functions corresponding to a combination of four orbits. Implementing our search algorithm for both $f_{PW_{1}}$ and $f_{PW_{2}},$ we find that no RSBF h with nonlinearity 16272 containing any zero in its Walsh-Hadamard spectrum can be obtained by dropping the Walsh-Hadamard spectrum value 40 to zero; however, converting the other Walsh-Hadamard spectrum value − 88 to zero yields such RSBFs. Specifically, in the latter case, we find that the number of RSBFs which can be affinely transformed to balanced Boolean functions is 44 (resp., 6) for the PW function $f_{PW_{1}}$ (resp., $f_{PW_{2}}$). We observe that some of these RSBFs are the same due to the fact that a single four-orbit combination can convert the value − 88 to zero at more than one different points in the Walsh-Hadamard spectrum, leading to recounting the same RSBF more than once. Hence, after removing them, those numbers reduce to 15 and 2 for $f_{PW_{1}}$ and $f_{PW_{2}},$ respectively. In Table 3, we present the cryptographic propeties (Δ_h,d_h) of these distinct functions h and the corresponding four-orbit combinations (together with their orbit sizes) to obtain them, where, taking the left-most bit as the most significant bit, an orbit representative is denoted by the decimal number equivalent to the binary representation and the subscript denotes the size of the corresponding orbit. We have checked that the number of zeros in the Walsh-Hadamard spectrum is 7 for all of them except the one with (Δ_h,d_h) = (224,13) for which it is 6. Note that, since it is necessary (but not sufficient) to have at least n + 1 zeros in the Walsh-Hadamard spectrum to affinely transform an unbalanced n-variable Boolean function to a 1-resilient Boolean function, none of the Boolean functions obtained using the combinations in Table 3 can be made 1-resilient.

Table 3 Combinations and the respective cryptographic properties for (a) $f_{PW_{1}}$ (b) $f_{PW_{2}}$

In Table 3 (a), the combination of the orbit representatives (0₍₁₎,315₍₁₅₎, 2275₍₁₅₎, 8183₍₁₅₎) was given in [1], from which a balanced Boolean function with nonlinearity 16272, absolute indicator 248, algebraic degree 11, and algebraic immunity 8 (i.e., optimal algebraic immunity) could be obtained by an affine transformation. However, from Table 3, it is seen that there exist better achievable cryptographic properties. For instance, consider the function h for which the combination is (0₍₁₎,621₍₁₅₎,657₍₁₅₎,1611₍₁₅₎) and (Δ_h,d_h) = (232,11). It can be computationally found that one of the zeroes in its Walsh-Hadamard spectrum occurs at ω = (0,0,1,0,0,1,0,0,1,0,0,1,0,0,1) i.e., W_h(ω) = 0. Then, the Boolean function g = h ⊕ l_ω is balanced with (NL_g,Δ_g,d_g) = (16272,232,11), where l_ω = ω ⋅ x, for all $x\in \mathbb {F}_{2}^{15}$, is the linear function selected by ω. We have also found that g has optimal algebraic immunity. Further, as can be seen from Table 3, both absolute indicator and algebraic degree can be improved as 224 and 13, respectively, using the combination (621₍₁₅₎,657₍₁₅₎,1611₍₁₅₎,14043₍₃₎) for $f_{PW_{1}},$ and the absolute indicator can be as low as 216 using either (0₍₁₎,1661₍₁₅₎,3231₍₁₅₎,5483₍₁₅₎) for $f_{PW_{1}}$ or (0₍₁₎,1661₍₁₅₎,3231₍₁₅₎,5483₍₁₅₎) for $f_{PW_{2}}$. We have checked that the algebraic immunities of the balanced Boolean functions that are obtained from the latter three combinations are 7, 7, and 6, respectively.

3.2 1-resilient functions with nonlinearity 16264

Let g be an n-variable Boolean function and $Z_{g}=\{{\omega \in \mathbb {F}_{2}^{n}} \mid W_{g}(\omega )=0\}$ such that there exist n linearly independent vectors in Z_g. Then the Boolean function f(x) = g(A^− 1x), for all $x{\in \mathbb {F}_{2}^{n}}$, is correlation immune of order 1, where A is an n × n matrix with full rank whose rows are the vectors from Z_g. Both f and g have the same nonlinearity, absolute indicator, and algebraic degree, as those cryptographic properties are invariant under affine transformations. Further, if g is balanced, then f is 1-resilient.

Following this well-known technique, we find whether an unbalanced RSBF h (with NL_h ≥ 16264, obtained by Algorithm 1) is affinely transformable to a 1-resilient Boolean function as follows. Let $Z_{h}=\{\omega \in \mathbb {F}_{2}^{15} \mid W_{h}(\omega )=0\}$ be the corresponding set of zeros in its Walsh-Hadamard spectrum. We then check if there exist any ν ∈ Z_h for which the set Z_g = {ω ⊕ ν∣ω ∈ Z_h} (which is the set of zeros in the Walsh-Hadamard spectrum of the balanced Boolean function g = h ⊕ l_ν) is of rank 15, in order to determine whether the RSBF h is affinely transformable to a 1-resililent Boolean function. Implementing our search algorithm accordingly, we find 39418 (resp., 38336) RSBFs, each satisfying the condition for the mentioned affine transformation, by converting the Walsh-Hadamard spectrum value 40 to zero for $f_{PW_{1}}$(resp., $f_{PW_{2}}$). On the other hand, when we convert the other Walsh-Hadamard spectrum value − 88 to zero, we find that the number of such RSBFs is 562 for $f_{PW_{1}}$ and 810 for $f_{PW_{2}}$. After removing the same RSBFs among all (79126) of them, we get 28282 (out of which 14307 are from $f_{PW_{1}}$ and 13975 are from $f_{PW_{1}}$) distinct RSBFs such that each is affinely transformable to a 1-resilient Boolean function with nonlinearity 16264. In Table 4, these Boolean functions are classified in terms of their absolute indicator and algebraic degree parameters.

Table 4 The classification of the 28282 1-resilient Boolean functions

We note that the 1-resilient Boolean function with nonlinearity 16264, absolute indicator 232, algebraic degree 12, and algebraic immunity 7 was obtained in [1] from $f_{PW_{1}}$ using the combination (935₍₁₅₎, 1971₍₁₅₎, 6895₍₁₅₎, 11627₍₅₎). From Table 4, it is seen that there exist RSBFs with better absolute indicator and optimum algebraic degree (as for 1-resilient n-variable Boolean functions, the algebraic degree can be at most n − 2) properties. As an example, consider the RSBF h with profile (Δ_h,d_h) = (208,13), which is obtained from $f_{PW_{1}}$ using the combination (1173₍₁₅₎,5285₍₅₎,6877₍₁₅₎,14043₍₃₎) (which changes the Walsh-Hadamard spectrum value 40 to 0). To make h balanced we take ν = (0,0,0,0,0,0,0,1,1,0,1,0,1,1,1) for which W_h(ν) = 0, and hence g = h ⊕ l_ν is balanced. Then as aforementioned, we find 15 linearly independent vectors from the set Z_g = {ω ⊕ ν∣W_h(ω) = 0} (with ∣Z_g∣ = 30) to form the matrix A. Thus the Boolean function f(x) = g(A^− 1x), for all $x\in \mathbb {F}_{2}^{15}$, is 1-resilient with nonlinearity 16264, absolute indicator 208, and algebraic degree 13. We have checked that the algebraic immunity of this Boolean function is 8. This is the first time a 1-resilient Boolean function exceeding the bent concatenation bound in nonlinearity is demonstrated with optimal algebraic immunity and algebraic degree. Further, as can be seen from Table 4, the absolute indicator can be improved to 200 while keeping the algebraic degree optimal, and there is only one such RSBF, which is obtained from $f_{PW_{2}}$ using the combination (4681₍₃₎,5293₍₁₅₎,2489₍₁₅₎,7399₍₅₎). We find that all the 1-resilient Boolean functions provided by this RSBF have algebraic immunity 7.

3.3 Balanced functions with absolute indicator 192

In [1], using the combination (1057₍₅₎,1843₍₁₅₎) for $f_{PW_{1}},$ a balanced Boolean function with nonlinearity 16264 and absolute indicator 192 was found, which improved the previous results in [11, 12] in terms of nonlinearity and absolute indicator. It is stated in [1] that, for both of the PW functions, the maximum balanced nonlinearity achieved by toggling the outputs corresponding to one orbit with size 5 and another orbit with size 15 (i.e., by dropping the Walsh-Hadamard spectrum value 40 to zero) is 16264. However, implementing the same technique, we find that there are 75 RSBFs, each can be affinely transformed to a balanced Boolean function, with nonlinearity 16266 which is the maximum and all of them are obtained from $f_{PW_{1}}$. Further, among them there exist three RSBFs with absolute indicator 192 for which the corresponding combinations are (1057₍₅₎,3279₍₁₅₎),(1965₍₁₅₎,11627₍₅₎), and (1457₍₁₅₎,7399₍₅₎). We have checked that all of them have algebraic degree 14, while the Boolean function given in [1] has algebraic degree 13. For instance, using the combination (1057₍₅₎,3279₍₁₅₎) for $f_{PW_{1}}$ we get an RSBF h with 15 zeros in its Walsh-Hadamard spectrum. Then, choosing one of these zeros arbitrarily, e.g., ω = (0,0,0,0,1,1,1,0,1,1,0,0,1,0,1), the balanced Boolean function g = h ⊕ l_ω with (NL_g,Δ_g,d_g,AI_g) = (16266,192,14,8) is obtained. We also note that the algebraic immunity of g improves that of the Boolean function given in [1] for which we find that it is 7.

Next, we achieve a further improvement of nonlinearity by interpreting the PW functions as 3-RSBFs. In this case, there are g_15,3 = 6560 orbits, among which 8 of them are of size 1 and the rest are of size 5. We consider all possible four-orbit combinations dropping the Walsh-Hadamard spectrum value 40 to zero. Noting then that there is only one possible combination (5⁽⁴⁾), i.e., four entries with value 5, of the matrix $_{15}\mathcal {A}^{3}$ entries and modifying Algorithm 1 accordingly, it can be computed that the search space is of size ≈ 2^36.4. We find in this neighbourhood that there are 252 distinct 3-RSBFs with nonlinearity 16268 and absolute indicator 192, each containing zeros in its Walsh-Hadamard spectrum, such that 168 (resp., 84) of them are obtained from $f_{PW_{1}}$ (resp., $f_{PW_{2}}$). In addition, all of them have algebraic degree 13. As an example, using the combination (5555₍₅₎,6931₍₅₎,7918₍₅₎,14749₍₅₎) for $f_{PW_{1}}$, we get a 3-RSBF h with 10 zeroes in its Walsh-Hadamard spectrum. Taking one of these zeros, e.g., ω = (0,0,0,0,0,0,1,0,1,1,1,1,0,0,1), we get the balanced Boolean function g = h ⊕ l_ω with (NL_g,Δ_g,d_g,AI_g) = (16268,192,13,8). We also observe that in the neighbourhood that we consider, there is no 3-RSBF which can be affinely transformed to a balanced Boolean function with nonlinearity 16272 or a 1-resilient Boolean function with nonlinearity 16268.

It should be pointed out that the search space becomes huge when we consider the case for 5-RSBFs, since we need to use the combinations of at least 8 orbits due to the fact that the entries of the corresponding matrix $_{15}\mathcal {A}^{5}$ can take only the values ± 1,± 3.

Remark 1

We note that there is the possibility to apply the search method for similar questions in different dimensions, too. For instance, for n = 9, 11, and 13, one can try to look into the neighbourhood of n-variable unbalanced functions with nonlinearity $2^{n-1}-2^{\frac {n-1}{2}} +2\cdot 2^{\frac {n-9}{2}}$ [4] to find improved cryptographic properties. In this case, the search method can be a suitable candidate, since the nonlinearities of those functions can be computed by exploiting the matrix $_{9}\mathcal {A}^{3}$. Similarly, with sufficient computation power, the search method can be applied for the neighbourhood of 21-variable unbalanced function with nonlinearity $2^{21-1}-2^{\frac {21-2}{2}}+61$ [13].

The more important work on this topic is to find 15-variable Boolean functions with nonlinearity greater than 16276, balanced functions with nonlinearity greater than 16272 or 1-resilient functions with nonlinearity greater than 16264. Our results indicate that there is no such functions within the neighbourhood of the PW functions formed by up to four-orbit combinations; however, due to the large search spaces, one can perform heuristic search techniques for higher number of orbit combinations to achieve those improvements.