Boolean Functions and Permanents of Sylvester Hadamard Matrices

mathematics Article Boolean Functions and Permanents of Sylvester Hadamard Matrices José Andrés Armario   Citation: Armario, J.A. Boolean Functions and Permanents of Sylvester Hadamard matrices. Mathematics 2021,9, 177. https://doi.org/10.3390/ math9020177 Received: 27 November 2020 Accepted: 15 January 2021 Published: 17 January 2021 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2021 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). Departamento de Matemática Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain; [email protected] Abstract: One of the fastest known general techniques for computing permanents is Ryser’s formula. On this note, we show that this formula over Sylvester Hadamard matrices of order 2 m , Hm , can be carried out by enumerating m -variable Boolean functions with an arbitrary Walsh spectrum. As a consequence, the quotient per(Hm)/ 2 2m might be a measure of the “density” of m -variable Boolean functions with high nonlinearity. Keywords: permanent; Sylvester Hadamard matrices; Ryser’s formula; Boolean functions; Walsh spectrum; high nonlinearity MSC: 15A15; 05B20; 06E30; 65T50 1. Introduction The theory of Boolean functions is a fascinating area of research in discrete mathematics with applications to cryptography and coding theory. Claude Shannon’s properties of confusion and diffusion are fundamental concepts for achieving security in cryptosystems. The notion of diffusion is related to the degree to which the influence of a single input plaintext bit is spread throughout the resulting ciphertext, and the notion of confusion is related to the complexity of the relationship between the secret key and ciphertext. Boolean functions with high nonlinearity can be used to provide confusion in block encryption algorithms [ 1 , 2 ]. Nonlinearity is the minimum number of bits which must change in the truth table of a Boolean function to become an affine function. The Walsh transform is the most important mathematical tool for the analysis of cryptographic properties of Boolean functions. The understanding of the Walsh transform of a Boolean function uniquely determines the function; therefore, working fully with the Walsh transform is possible. Here we study a connection between the Walsh spectrum of m -variable Boolean functions and Ryser’s formula of the permanent for Sylvester Hadamard matrices of order 2m. In 1812, Cauchy and Binet independently introduced the notion of the permanent as a matrix function. Definition 1. Let N be the set { 1, . . . , n} , ( n∈Z+ ). The symmetric group Sn is the group of all n!permutations of N. The permanent of an n ×n matrix A =aijis defined by per (A) = ∑ σ∈Sn n ∏ i=1 ai,σ(i). At first glance, it seems to be a straightforward version of the determinant, but this is a misleading impression. For instance, the determinant of an arbitrary matrix can be evaluated efficiently using Gaussian elimination; however, the computation of the permanent is much more complicated. Valiant [ 3 ] proved that it belongs to the class of ] P-complete problems, which basically means that there is almost no possibility of Mathematics 2021,9, 177. https://doi.org/10.3390/math9020177 https://www.mdpi.com/journal/mathematics Mathematics 2021,9, 177 2 of 8 finding a polynomial time deterministic algorithm for computing the permanent in general. Precisely, the central problem studied in arithmetic complexity theory is the permanent versus determinant problem, which is considered the arithmetic analogue of the NP vs. P problem (see [4]). There are wide applications of the permanent of certain matrices, such as 0,1 and/or sparse matrices with special structures. Especially in combinatorial counting and graph theory [ 5 ]. For instance, if G is a balanced (the two parts have equal size) bipartite graph and MG is its adjacency matrix, the per (MG) counts perfect matchings in G . Nevertheless, as far as we know, there is not any clear combinatorial interpretation of the permanent of Hadamard matrices. Here we give some ideas towards an interpretation of the permanent of the Sylvester Hadamard matrices in terms of Boolean functions with high nonlinearity. Notation. Throughout the article, we make use of − for − 1 and 1 for + 1. We write Hmfor a Sylvester Hadamard matrix of order 2m. The cardinality of a set Sis denoted ]S. We use In for the identity matrix of order n and MT for the transpose of M . The Galois field with two elements is denoted by GF( 2 ) and the m -dimensional vector space over GF( 2 ) , equipped with the canonical basis by GF( 2 )m . hgi , gji means the usual inner product for gi,gj∈GF(2)n. 2. Preliminaries Basic concepts and results on Hadamard matrices and Boolean functions will be reviewed. We refer the reader to [ 6 ] for more details about Hadamard matrices and see [ 7 ] and the references therein for some of the theories of Boolean functions. 2.1. Hadamard Matrices AHadamard matrix H of order n is an n×n matrix with entries ± 1 and HHT=nI . If a Hadmard matrix has its first row and column all 1 s are said to be normalized. A Hadamard matrix can always be normalized by multiplying rows and columns by − 1 . It is wellknown that n can only be either 2 or a multiple of 4 and it is conjectured that Hadamard matrices exist for every n≡0 mod 4 (see [6]). It was observed by Sylvester in 1867 that, if H is a Hadamard matrix of order n , then H H H−H is a Hadamard matrix of order 2 n . Matrices of this configuration are called Sylvester Hadamard and are defined for all powers of 2. The Sylvester Hadamard matrix of order 2 is given as H1=1 1 1−. Sylvester Hadamard matrices of order 2 k , denoted by Hk , can be formed by k−copies H1×···×H1 the Kronecker product of k copies of H1 . These matrices have many interesting properties (see [8]), for instance Hm= [(−1)hgi,gji]gi,gj∈GF(2)m. Two Hadamard matrices H and H0 are said to be equivalent when one can be acquired from the other by a series of row and/or column interchanges and row and/or column negations. The question of classifying Hadamard matrices of order n≥ 36 remains unanswered and only partial results are known. We recollect that Hadamard proved that nn/2 is an upper bound for the absolute value of the determinant of an n×n matrix with entries from the unic disc, and this bound is attainable by matrices with entries ± 1 if and only if they are Hadamard. However, the permanent of a Hadamard matrix has hardly been worked on, and it is considered a very difficult problem. From what we know, the permanents for all Hadamard matrices of orders smaller or equal to 28 were calculated in [ 9 ], but for orders greater than 28 the Mathematics 2021,9, 177 3 of 8 permanent remains unknown in general. The permanent of the Sylvester Hadamard matrix of order 32 is 6829323892021002240 ([10]). 2.2. Boolean Functions ABoolean function is a mapping f:GF(2)m→GF(2). We denote by Bm the set of all m -variable Boolean functions. Since there are 2 m possible inputs of length m,]Bm=22m. Example 1. f(x) = hx , gi+c where g∈GF( 2 )m and c∈GF( 2 ) represent a Boolean function, the so-called affine function. In particular, if c= 0then f(x) is called a linear function. We denoted by Amthe set of m-variable affine functions and ]Am=2m+1. A Boolean function can be displayed in several ways. One prospect is to simply list all values in a fixed order. To this end we denote gi as the binary representation of the integer i− 1 with m bits. For instance, g1= ( 0, 0, . . . , 0 ) and g2= ( 0, . . . , 0, 1 ) , hence this list g1,g2, . . . , g2mcontains all the elements of GF(2)m. The vector [f(g1),f(g2), . . . , f(g2m)] is called the truth table (TT) of a Boolean function f . The support of f is the set Sf= {g∈GF( 2 )m:f(g) = 1 } , and the weight of f , wt(f) , is the cardinality of the support, i.e., wt(f) = ]Sf. The Hamming distance between two Boolean functions f and h on GF( 2 m) is defined as wt(f+h) . The nonlinearity of f and denoted by Nf is the minimum distance between f and the set of all affine functions. This concept has several applications in cryptography and coding theory. For instance, nonlinearity can be utilized as a measure of the strength of cryptosystems (see [ 11 ]). The Walsh-Hadamard transform is the main tool to study the nonlinearity of Boolean functions, which is defined for an m -variable Boolean function f , such as Wf(g) = ∑ x∈GF(2)m (−1)f(x)+hx,gi,g∈GF(2)m. The vector [Wf(g1) , Wf(g2) , . . . , Wf(g2n)] is called the Walsh spectrum (WS) of a Boolean function f . Each component Wf(g) of WS is called a Walsh coefficient. Its magnitude is the correlation between f and the corresponding linear function lg(x) = hx , gi for g,x∈GF(2)m. Now, we recall some results involving the Sylvester Hadamard matrix and the WS of a Boolean function. Proposition 1. Assuming that f is an m -variable Boolean function and Hm= [hi,j] is the Sylvester Hadamard matrix of order 2m. The following identities hold, 1. [F(g1) , F(g2) , . . . , F(g2m)] Hm= [Wf(g1) , Wf(g2) , . . . , Wf(g2m)] , where F(g) = (− 1 )f(g) . 2. ∑ i∈Sf hi,k=2m−1δgk g1−1 2Wf(gk),k=1, . . . , 2mwhere δgk g1is Kronecker’s symbol. Mathematics 2021,9, 177 4 of 8 Proof. The first identity follows from the fact that Hm= [(− 1 )hgi,gji]m gi,gj∈GF(2) . For the second, we have to take into account the following facts: •Wf(gk) = ∑ i∈¯ Sf hi,k−∑ i∈Sf hi,kwhere ¯ Sf={1, 2, . . . , 2m}\Sf. • 2m ∑ i=1 hi,k=2mk=0 0 0 <k≤2m 3. Ryser’s Formula for Hmand the Walsh Spectrum of Boolean Functions H.J. Ryser found the following alternative method to evaluate the permanent of a matrix A= [aij]of order n, per (A) = (−1)nn ∑ r=1 (−1)r∑ α∈Qr,n n ∏ j=1 ∑ i∈α ai,j, (1) where Qr,n denotes the set of all strictly increasing sequences of r integers taken from the set { 1, 2, . . . , n} . This is one of the fastest known general algorithms for computing a permanent.By counting multiplications it has an efficiency of O(2nn)(see pp. 31–11 [12]). Proposition 2. Assuming that Hm= [hi,j] is the Sylvester Hadamard matrix of order 2 m , f an arbitary m-variable Boolean function and Φ(f) = ∏2m j=2∑i∈Sfhi,j. Then, 1. Φ(f) = −21−2m2m ∏ j=2 Wf(gj). 2. per (Hm) = 2m ∑ r=1 (−1)rr∑ sf∈Qr,2m Φ(f). Proof. The first identity follows from Proposition 1and the second one is immediate. The following result studies some properties of the function Φthat we will use later. Lemma 1. 1. Let f be an arbitrary f∈Bm−1 and h= [f|f] be the result of concatenating the TT of f to itself. Then Φ(h) = 0. 2. Let l∈Am−1 , f∈Bm−1 and h= [f|l] . If Φ(f) = 0then Φ(h) = 0. For instance, Φ(h) = 0when wt(f) = 2or 4. 3. Let l(x) = hx,gji+c∈Am,f∈Bmand h=l+f. Then Φ(h) = (2m−2wt(f)) Wf(gj)(−1)cΦ(f). Proof. Identities 1 and 2 follow from Wh(gk) = Wf1(gk) + Wf2(gk)1≤k≤2m−1 Wf1(gk)−Wf2(gk)2m−1+1≤k≤2m for h= [f1|f2] and Wl(gk) is null for some k> 1. For identity 3, we have to take into account that Wh(gk) = (−1)cWf(gj+gk). In the sequel, we will try to extract some consequences of the Proposition 2. Firstly, it may help in finding an interpretation of the permanent of Hmin terms of nonlinearity. Since Wf(g) = 2m−2wt(f+lg), the nonlinearity of fis computed from the Walsh sprectrum by Nf=2m−1−1 2max g∈GF(2)m|Wf(g)|. Mathematics 2021,9, 177 5 of 8 If a maximum absolute value of Wf occurs at gk , then either lgk is the best linear approximation of f (when Wf(gk)> 0) or its complement, the affine function 1 +lgk , is as good as, or better than, the best linear approximation (when Wf(gk)<0). It is a simple corollary of Parseval’s identity, 2m ∑ i=1 Wf(gi)2=22m, that max i|Wf(gi)| ≥ 2m 2. (2) Therefore, for any Boolean function in mvariables, Nf≤2m−1−2m 2−1, and this bound is achieved only when mis even and |Wf(gi)|=2m 2,∀i. Hence, wt(f) = 2m−2m/2 2or 2m+2m/2 2. An m -variable Boolean function with m even and maximum nonlinearity is called bent. Furthermore, if f is bent then |Φ(f)|= 2 m2m−2 . This is the maximum of |Φ| in Bm and Φ(f)<0. The affine functions are the other extreme, with respect to the Walsh spectrum. There is only one non-null Walsh coefficient for an affine function, and its value is either 2 m , when it is linear, or −2motherwise. Therefore, Φ(lgk+c) = 0. By Parseval’s identity, if some of the Walsh coefficients are smaller than average in absolute value, especially if some are 0, then the others must be larger. Thus, if f is a Boolean function with a small Nf and wt(f) even then it can be expected that Φ(f) will be null. For wt(f) odd and after carrying out some computer searches up to m= 5, we found that Φmore often takes positive than negative values. Although the formula for nonlinearity is sign free, the quotient per(Hm) ]Bm could provide some information of the “global” nonlinearity of the whole set m -variable Boolean functions. Especially, when per(Hm) ]Bm <per(Hm0) ]Bm0 could indicate a better density of Boolean functions with high nonlinearity in Bm than in Bm0 . For m= 2 and 4, this is confirmed with the behaviour of the quotient between the number of bent functions in m variables between the number of Boolean functions (see [ 2 ], Chapter 7). Attending to our observation we also claim the following. Conjecture 1. If mis even, then 2(m−2)2m−4≤per(Hm)≤2m2m−2 and if mis odd, then 2(m−1)2m−2≤per(Hm)≤2(m+1)2m−2. Secondly, we will try to take advantage of computing the permanent of a Sylvester Hadamard matrix from partitioning Bmin classes under the affine equivalence relationship. Mathematics 2021,9, 177 6 of 8 Definition 2 ([ 2 ]) . Two m -variable Boolean functions f and h are said to be affine equivalent if there exists an invertible matrix A with entries in GF( 2 ) and a constant b∈GF( 2 )m such that for all x ∈GF(2)mit holds that f(x) = h(A(x) + b). The following Lemma studies the Walsh spectra of affine equivalent Boolean functions fand h. As immediate consequence, we have Nf=Nh. Lemma 2 ([ 13 ]) . Let f and h be two affine equivalent m -variable Boolean functions, f(x) = h(A(x) + b), then Wf(g) = (−1)hb,(A−1)T(g)iWh((A−1)T(g)). Another important consequence is, Proposition 3. If f and h are affine equivalent m-variable Boolean functions then Φ(f) = Φ(h). Proof. This follows from Proposition 2and Lemma 2. Since (A−1)T(g) runs over all the elements of GF( 2 )\{ 0 } when g runs over all the elements of GF( 2 )\{ 0 } and the number of times that hb , (A−1)T(g)i= 1 mod 2 is even for any fixed b∈GF( 2 ) when when g runs over all the elements of GF( 2 )\{ 0 } . This last statement is due to the fact that the number of elements of GF(2)mwith concrete values in certain positions divides 2m. Now, the formula for the permanent of Hm can be rewritten in terms of classes under the affine equivalence relation for the set of m-variable Boolean functions. Proposition 4. per(Hm) = 2m−1−1 ∑ r=1 (−1)r(2r−2m) ]Ωr,m ∑ i=1 ][Xr i]Φ(fXr i). (3) where Ωr,m is the set of classes under the affine equivalence for the m -variable Boolean functions of weight r, fXr iis a representative of the class Xr i∈Ωr,m, r =wt(fXr i). Proof. It is immediate from Proposition 2, Proposition 3and the fact that ∑ i∈α hi,j= −∑ i∈¯ α hi,j,j≥2; where α∪¯ α={1, 2, . . . , 2m}. Example 2. Now we are going to compute per (H3)using formula (3), H3=             11111111 1−1−1−1− 1 1 − − 1 1 − − 1− − 1 1 − − 1 1 1 1 1 − − − − 1−1− − 1−1 1 1 − − − − 1 1 1− − 1−1 1 −             . Taking into account that Φ(f) = 0for any 3-variable Boolean function with wt(f)even. Then, per (H3) = (−1)1(2−8) ]Ω1,3 ∑ i=1 ][X1 i]Φ(fX1 i) + (−1)3(6−8) ]Ω3,3 ∑ i=1 ][X3 i]Φ(fX3 i) Mathematics 2021,9, 177 7 of 8 (Using Table 1, we get) =6×(8×1) + 2×(56 ×3) = 384. Therefore, the problem of computing the permanent of a Sylvester Hadamard matrix of order 2 m can be carried out by enumerating m -variable Boolean functions with an arbitrary Walsh spectrum. This enumeration problem, although of interest in cryptography [ 14 ], requires a huge amount of computational resources. For instance, the number of bent functions (those Boolean functions with flat spectrum) so far has only been known for dimensions up to and including 8 (see [ 15 ]). Thus, Formula (3) only has a theoretical interest. Finally, we give another formula for the permanent of Hm as a straightforward consequence of some results from [ 16 , 17 ]. Let Sym(E) be the group of permutations on the set E and ε(σ) be the parity + 1 or − 1 of σ for each σ∈Sym(E) . Then, Γ(f) is defined as the set {σ∈Sym(GF(2)m):∀a∈GF(2)m,f(a+σ(a)) = 1}. Now, taking into account the following facts: 1. Theorem 1 of [ 16 ] proves that the Walsh spectrum of f coincides with the spectrum of Gf , the Cayley graph associated to f , where the vertex set of Gf is equal to GF( 2 )m , while the edge set Efis defined as follows: Ef={(gi,gj)|f(gi+gj) = 1}. This connects the problem of analyzing the spectral coefficients of Boolean functions with the framework of spectral analysis of graphs. Let us denote by wf(gi) the eigenvalues of the adjacency matrix of the Cayley graph associated to f. 2. Corollary 2 of [17] proves that the product Π2m i=1wf(gi) = ∑σ∈Γ(f)ε(σ). Therefore, the formula for the permanent of Hmgiven in Proposition 2can be rewritten as per (Hm) = 2m ∑ r=1 (−1)r+1r∑ sf∈Qr,2m ∑σ∈Γ(f)ε(σ) 22m−1wf(g1). Table 1. Number of inequivalent m -variable Boolean functions of weight r under the affine equivalence for m=3 and r=1, 3. r # Inequivalent 3-Variable Boolean Functions # Orbits 1 1 8 3 1 56 4. Conclusions The paper demonstrates a connection between two different mathematical areas: Boolean functions and permanents. Firstly, Ryser’s formula for computing the permanent of Sylvester Hadamard matrices has been rewritten in terms of the Walsh spectrum of m -variable functions. Although this formula does not represent a real shortcut for computing the permanent of Hm , it suggested the bounds given in Conjecture 1, since |∏2m j=2Wf(gj)|= 2 m2m−2 when f is bent. Secondly, we show that the quotient per(Hm)/ 2 2m provides information about the density of m -variable Boolean functions with high nonlinearity (i.e., Boolean functions with linearity close to the minimum). We have checked until m= 5 that per(Hm)/ 2 2m is a strictly increasing function and the quotient between the number of bent functions in m variables and the number Boolean functions (2 2m ) is a strictly decreasing function (up to m= 8) which means that density Boolean functions with high nonlinearity are worse when m increase. Finally, let us point out the following asymptotic result about the linearity of random Boolean functions due to Olejár and Stanek. Mathematics 2021,9, 177 8 of 8 Theorem 1 ([ 18 ]) . There is a constant c , such that if m is big enough, then for almost every Boolean function in m variables Nf≥2m−1−c√m2m/2. Funding: This research received no external funding. Institutional Review Board Statement: Not applicable. Informed Consent Statement: Not applicable. Data Availability Statement: Not applicable. Acknowledgments: The author thanks Kristeen Cheng for reading the manuscript. This work is partially supported by the Research Projects FQM-016 from Junta de Andalucí a. Conflicts of Interest: The author declare no conflict of interest. References 1. Guesmi, R.; Farah, M.A.B.; Kachouri, A.; Samet, M. Chaos-based designing of a highly nonlinear S-box using Boolean functions. In Proceedings of the 12th International Multi-Conference on Systems, Signals and Devices, SSD, Tunisia, Mahdia, 16–19 March 2015; Volume 2015, p. 7348106. 2. Tokareva, N. Bent Functions: Results and Applications to Cryptography; Elsevier Science: London, UK, 2015. 3. Valiant, L.G. The complexity of computing the permanent. Theoret. Comput. Sci. 1979,8, 189–201. [CrossRef] 4. Aaronson, S. P ? = NP Chapter 3 in Open Problems in Mathematics; Nash, J.F., Rassias, M.T., Eds.; Springer: Berlin/Heidelberg, Germany, 2016. 5. Minc, H. Permanents. In Encyclopedia of Mathematics and its Applications 6; Addison-Wesley: Reading, MA, USA, 1978. 6. Horadam, K.J. Hadamard Matrices and Their Applications; Princeton University Press: Princeton, NJ, USA, 2007. 7. Carlet, C. Boolean functions for cryptography and error correcting codes. In Boolean Models and Methods in Mathematics, Computer Science and Engineering; Crama, Y., Hammer, P.L., Eds.; Cambrige University Press: Cambridge, UK, 2010; pp. 257–397. 8. Mitrouli, M. Sylvester Hadamard matrices revisited. Spec. Matrices 2014,2, 120–124. [CrossRef] 9. Wanless, I.M. Permanents of matrices of signed ones. Linear Multilinear Algebra 2005,52, 57–63. [CrossRef] 10. Szöllósi, F. (Department of Mathematical Science, Shimane University, Matsue, Japan). Personal communication, 2014. 11. Carlet, C. On cryptographic complexity of Boolean functions. In Proceedings of the Sixth Conference on Finite Fields with Applications to Coding Theory, Cryptrography, and Related Areas, Berlin, Germany; Mullen, G.L., Stichtenoth, H., Tapia-Recillas, H., Eds.; Springer: Berlin, Germany, 2002; pp. 53–69. 12. Wanless, I.M. Permanents. In Chapter 31 in Handbook of Linear Algebra; Hogben, L., Ed.; Chapman & Hall/CRC: London, UK, 2007. 13. Preneel, B. Analysis and Design of Cryptographic Hash Functions. Ph.D. Thesis, Katholieke Universiteit Leuven, Leuven, Belgium, 1993. 14. Uyan, E.; Calik, C.; Doganaksoy, A. Counting Boolean functions with specified values in their Walsh spectrum. J. Comput. Appl. Math. 2014,259, 522–528. [CrossRef] 15. Langevin, P.; Leander, G. Counting all bent functions in dimension eight 992705892659343370305785861242880. Des. Codes Cryptogr. 2011,59, 193–205. [CrossRef] 16. Bernasconi, A.; Codenotti, B. Spectral analysis of Boolean functions as a graph eigenvalue problem IEEE Trans. Comput. 1999 , 48, 345–351. 17. Mitton, M. On the Walsh-Fourier analysis of Boolean functions. J. Discret. Math. Scien. Cryptogr. 2006,9, 429–439. [CrossRef] 18. Olejár, D.; Stanek, M. On cryptographic properties of fandom Boolean functions. J. Univers. Comput. Sci. 1998,4, 705–717.