A Note on the Confusion Coefficient of Boolean Functions ZHOU, Yu; HU, Jianyong; MIAO, Xudong ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
12/2023, Volume:
E106.A, Issue:
12
Journal Article
Peer reviewed
Open access
Low confusion coefficient values can make side-channel attacks harder for vector Boolean functions in Block cipher. In this paper, we give new results of confusion coefficient for f ⊞ g, f ⊡ g, f ⊕ g ...and fg for different Boolean functions f and g, respectively. And we deduce a relationship on the sum-of-squares of the confusion coefficient between one n-variable function and two (n - 1)-variable decomposition functions. Finally, we find that the confusion coefficient of vector Boolean functions is affine invariant.
In this paper, we present two new kinds of theoretical construction of rotation symmetric Boolean functions with optimal algebraic immunity both on odd variables and on even variables based on ...ordered integer partitions. Our rotation symmetric Boolean functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degrees and the fast algebraic immunities of our rotation symmetric Boolean functions are also high enough in some cases.
In this paper, the weighted l1-gain analysis and l1 model reduction problem for Boolean control networks are proposed and investigated via semi-tensor product method. First, the input energy and ...output energy are described by pseudo-Boolean functions, based on which the definition of the weighted l1-gain is introduced. By constructing a co-positive Lyapunov function, a sufficient condition is established to ensure that a Boolean control network is not only internally asymptotically stable, but also has an l1-gain no more than a given scalar. Along this line, by virtue of the properties of semi-tensor product, the l1 model reduction problem of a Boolean control network is defined and converted to the l1-gain problem of another Boolean control network with more nodes. A sufficient condition for the l1 model reduction problem is then derived immediately, and an algorithm is presented to compute the matrices in the reduced order model. Finally, two examples, including the Boolean model for biochemical oscillators in the cell cycle, are displayed to show the feasibility of the theoretical results.
Cryptographic Boolean functions play an important role in the design of symmetric ciphers. Many cryptographic criteria such as balancedness, nonlinearity, correlation immunity and transparency order ...are connected with the Walsh support of a Boolean function. However, we still know little about the possible structure of the Walsh supports of Boolean functions. In 2005, Carlet and Mesnager studied the Walsh supports of Boolean functions and constructed a class of n-variable Boolean functions whose Walsh support is F2n∖{0}, for n≥10. For n≤6, it can be verified using the computer that there is no Boolean function with the Walsh Support F2n∖{0}. However, concerning the values of n=7,8,9, it has been an open problem for many years. In this paper, we construct two classes of balanced Boolean functions with the maximum possible Walsh support F2n∖{0}, and partially solve this problem. The first class of functions are of odd variables with n≥9, and the second class of functions are constructed based on the Maiorana–McFarland bent functions, which are of even variables with n≥8. As a result, the above open problem has been settled for n=8,9, and the only unsolved case is n=7.
Complete complementary codes (CCCs) have found a number of practical applications in wireless communications owing to their perfect aperiodic auto-correlation and cross-correlation properties. In ...particular, an important application of CCCs is in interference-free multi-carrier code-division multiple-access (MC-CDMA) systems. The available number of complementary codes determines the system capacity. To enlarge the system capacity, this paper focuses on constructing multiple CCCs with inter-set zero cross-correlation zone (ZCCZ) property based on generalized Boolean functions (GBFs). To the best of our knowledge, such multiple CCCs have not been reported in the literature. The obtained multiple CCCs can provide advantages in applications to MC-CDMA systems with multiple cells. As a byproduct, optimal aperiodic Z-complementary code sets (ZCCSs) with low peak-to-mean envelope power ratio (PMEPR) can be derived by combining these CCCs.
In this paper, we study the properties of the sum-of-squares indicator of vectorial Boolean functions. Firstly, we give the upper bound of $\sum_{u\in \mathbb{F}_2^n,v\in ...\mathbb{F}_2^m}\mathcal{W}_F^3(u,v)$. Secondly, based on the Walsh-Hadamard transform, we give a secondary construction of vectorial bent functions. Further, three kinds of sum-of-squares indicators of vectorial Boolean functions are defined by autocorrelation function and the lower and upper bounds of the sum-of-squares indicators are derived. Finally, we study the sum-of-squares indicators with respect to several equivalence relations, and get the sum-of-squares indicator which have the best cryptographic properties.
Let <inline-formula> <tex-math notation="LaTeX">{R}_{q}({r},{n}) </tex-math></inline-formula> be the <inline-formula> <tex-math notation="LaTeX">{r} </tex-math></inline-formula>th order ...<inline-formula> <tex-math notation="LaTeX">{q} </tex-math></inline-formula>-ary Reed-Muller code of length <inline-formula> <tex-math notation="LaTeX">{q}^{n} </tex-math></inline-formula>, which is the set of functions from <inline-formula> <tex-math notation="LaTeX">{\mathbb {F}}_{q}^{n} </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">{\mathbb {F}}_{q} </tex-math></inline-formula> represented by polynomials of degree <inline-formula> <tex-math notation="LaTeX">\le {r} </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">{\mathbb {F}}_{q}{X}_{1}, {\dots },{X}_{n} </tex-math></inline-formula>. The affine linear group <inline-formula> <tex-math notation="LaTeX">AGL({n},{\mathbb {F}}_{q}) </tex-math></inline-formula> acts naturally on <inline-formula> <tex-math notation="LaTeX">{R}_{q}({r},{n}) </tex-math></inline-formula>. We derive two formulas concerning the number of orbits of this action: (i) an explicit formula for the number of AGL orbits of <inline-formula> <tex-math notation="LaTeX">{R}_{q}({n}({q}-1),{n}) </tex-math></inline-formula>, and (ii) an asymptotic formula for the number of AGL orbits of <inline-formula> <tex-math notation="LaTeX">{R}_{2}({n},{n})/{R}_{2}(1,{n}) </tex-math></inline-formula>. The number of AGL orbits of <inline-formula> <tex-math notation="LaTeX">{R}_{2}({n},{n}) </tex-math></inline-formula> has been numerically computed by several authors for <inline-formula> <tex-math notation="LaTeX">{n}\le 31 </tex-math></inline-formula>; the binary case of result (i) is a theoretic solution to the question. Result (ii) answers a question by MacWilliams and Sloane.
Linear codes with a few-weight have important applications in combinatorial design, strongly regular graphs and cryptography. In this paper, we first construct a class of Boolean functions with at ...most five-valued Walsh spectra, and determine their spectrum distribution. Then, we derive two classes of linear codes with at most six-weight from the new functions. Meanwhile, the length, dimension and weight distributions of the codes are obtained. Results show that both of the new codes are minimal and among them, one is wide minimal code and the other is a narrow minimal code and thus can be used to design secret sharing scheme with good access structures. Finally, some Magma programs are used to verify the correctness of our results.
Let <inline-formula> <tex-math notation="LaTeX">f_{n}(x_{1}, x_{2}, \ldots, x_{n}) </tex-math></inline-formula> denote the algebraic normal form (polynomial form) of a rotation symmetric Boolean ...function of degree <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">n \geq d </tex-math></inline-formula> variables and let <inline-formula> <tex-math notation="LaTeX">wt(f_{n}) </tex-math></inline-formula> denote the Hamming weight of this function. Let <inline-formula> <tex-math notation="LaTeX">(1, a_{2}, \ldots, a_{d})_{n} </tex-math></inline-formula> denote the function <inline-formula> <tex-math notation="LaTeX">f_{n} </tex-math></inline-formula> of degree <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> variables generated by the monomial <inline-formula> <tex-math notation="LaTeX">x_{1}x_{a_{2}} \ldots x_{a_{d}} </tex-math></inline-formula>. Such a function <inline-formula> <tex-math notation="LaTeX">f_{n} </tex-math></inline-formula> is called monomial rotation symmetric (MRS). It was proved in a 2012 paper that for any MRS <inline-formula> <tex-math notation="LaTeX">f_{n} </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">d=3 </tex-math></inline-formula>, the sequence of weights <inline-formula> <tex-math notation="LaTeX">\{w_{k} = wt(f_{k}):\,\,k = 3, 4, \ldots \} </tex-math></inline-formula> satisfies a homogeneous linear recursion with integer coefficients. In this paper, it is proved that such recursions exist for any rotation symmetric function <inline-formula> <tex-math notation="LaTeX">f_{n} </tex-math></inline-formula>; such a function is generated by some sum of <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula> monomials of various degrees. A Mathematica program is available on arxiv.org which explicitly computes the homogeneous linear recursion for the weights, given any rotation symmetric <inline-formula> <tex-math notation="LaTeX">f_{n} </tex-math></inline-formula>. The reader who is only interested in finding some recursions can use the program and not be concerned with the details of the rather complicated proofs in this paper.
We consider classes of Boolean functions stable under compositions both from the right and from the left with clones. Motivated by the question how many properties of Boolean functions can be defined ...by means of linear equations, we focus on stability under compositions with the clone of linear idempotent functions. It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related with the theory of function minors, stable classes, clonoids, and hereditary classes, topics that have been widely investigated in recent years by several authors including Maurice Pouzet and his coauthors.