Construction of resilient Boolean functions in odd variables having strictly almost optimal (SAO) nonlinearity appears to be a rather difficult task in stream cipher and coding theory. In this paper, based on the modified High-Meets-Low technique, a general construction to obtain odd-variable SAO resilient Boolean functions without directly using PW functions or KY functions is presented. It is shown that the new class of functions possess higher resiliency order than the known functions while keeping higher SAO nonlinearity, and in addition the resiliency order increases rapidly with the variable number n.

The notion of the signal-to-noise ratio (SNR), proposed by Guilley, et al. in 2004, is a property that attempts to characterize the resilience of (n, m)-functions F=(f1,...,fm) (cryptographic S-boxes) against differential power analysis. But how to study the signal-to-noise ratio for a Boolean function still appears to be an important direction. In this paper, we give a tight upper and tight lower bounds on SNR for any (balanced) Boolean function. We also deduce some tight upper bounds on SNR for balanced Boolean function satisfying propagation criterion. Moreover, we obtain a SNR relationship between an n-variable Boolean function and two (n-1)-variable decomposition functions. Meanwhile, we give SNR(f⊞g) and SNR(f⊡g) for any balanced Boolean functions f, g. Finally, we give a lower bound on SNR(F), which determined by SNR(fi) (1≤i≤m), for (n, m)-function F=(f1,f2,…,fm).

Semi-bent functions have important applications in cryptography and coding theory. 2-rotation symmetric semi-bent functions are a class of semi-bent functions with the simplicity for efficient computation because of their invariance under 2-cyclic shift. However, no construction of 2-rotation symmetric semi-bent functions with algebraic degree bigger than 2 has been presented in the literature. In this paper, we introduce four classes of 2m-variable 2-rotation symmetric semi-bent functions including balanced ones. Two classes of 2-rotation symmetric semi-bent functions have algebraic degree from 3 to m for odd m≥3, and the other two classes have algebraic degree from 3 to m/2 for even m≥6 with m/2 being odd.

Boolean functions and vectorial Boolean functions are the most important components of stream ciphers. Their cryptographic properties are crucial to the security of the underlying ciphers. And how to construct such functions with good cryptographic properties is a nice problem that worth to be investigated. In this paper, using two small nonlinear functions with t-1 resiliency, we provide a method on constructing t-resilient n variables Boolean functions with strictly almost optimal nonlinearity >2n-1-2n/2 and optimal algebraic degree n-t-1. Based on the method, we give another construction so that a large class of resilient vectorial Boolean functions can be obtained. It is shown that the vectorial Boolean functions also have strictly almost optimal nonlinearity and optimal algebraic degree.

It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. In this letter, we determine all unknown values of the minimum Hamming weights of d-CI Boolean functions in n variables, for d ≤ 5 and n ≤ 13.

We present an explicit construction of a MAJn-2 °MAJn-2 circuit computing MAJn for every odd n≥7. This gives a partial solution to an open problem by Kulikov and Podolskii (Proc. of STACS 2017, Article No.49).

As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1n of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1n. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).

Since 2008, three different classes of Boolean functions with optimal algebraic immunity have been proposed by Carlet and Feng [2], Wang et al.[8] and Chen et al.[3]. We call them C-F functions, W-P-K-X functions and C-T-Q functions for short. In this paper, we propose three affine equivalent classes of Boolean functions containing C-F functions, W-P-K-X functions and C-T-Q functions as a subclass, respectively. Based on the affine equivalence relation, we construct more classes of Boolean functions with optimal algebraic immunity. Moreover, we deduce a new lower bound on the nonlinearity of C-F functions, which is better than all the known ones.

Rotation symmetric Boolean functions (RSBFs) that are invariant under circular translation of indices have been used as components of different cryptosystems. In this paper, odd-variable balanced RSBFs with maximum algebraic immunity (AI) are investigated. We provide a construction of n-variable (n=2k+1 odd and n ≥ 13) RSBFs with maximum AI and nonlinearity ≥ 2n-1-¥binom{n-1}{k}+2k+2k-2-k, which have nonlinearities significantly higher than the previous nonlinearity of RSBFs with maximum AI.

The global avalanche characteristics measure the overall avalanche properties of Boolean functions, an n-variable balanced Boolean function of the sum-of-square indicator reaching σƒ=22n+2n+3 is an open problem. In this paper, we prove that there does not exist a balanced Boolean function with σƒ=22n+2n+3 for n≥4, if the hamming weight of one decomposition function belongs to the interval Q*. Some upper bounds on the order of propagation criterion of balanced Boolean functions with n (3≤n≤100) variables are given, if the number of vectors of propagation criterion is equal and less than 7·2n-3-1. Two lower bounds on the sum-of-square indicator for balanced Boolean functions with optimal autocorrelation distribution are obtained. Furthermore, the relationship between the sum-of-squares indicator and nonlinearity of balanced Boolean functions is deduced, the new nonlinearity improves the previously known nonlinearity.

In this paper, we present an average-case efficient algorithm to resolve the problem of determining whether two Boolean functions in trace representation are identical. Firstly, we introduce a necessary and sufficient condition for null Boolean functions in trace representation, which can be viewed as a generalization of the well-known additive Hilbert-90 theorem. Based on this condition, we propose an algorithmic method with preprocessing to address the original problem. The worst-case complexity of the algorithm is still exponential; its average-case performance, however, can be improved. We prove that the expected complexity of the refined procedure is O(n), if the coefficients of input functions are chosen i.i.d. according to the uniform distribution over F2n; therefore, it performs well in practice.

In this paper, we give some results towards the conjecture that σ2t+1l-1,2t are the only nonlinear balanced elementary symmetric Boolean functions where t and l are positive integers. At first, a unified and simple proof of some earlier results is shown. Then a property of balanced elementary symmetric Boolean functions is presented. With this property, we prove that the conjecture is true for n=2m+2t-1 where m,t (m>t) are two non-negative integers, which verified the conjecture for a large infinite class of integer n.

Constructing APN or 4-differentially uniform permutations achieving all the necessary criteria is an open problem, and the research on it progresses slowly. In ACISP 2011, Carlet put forth an idea for constructing differentially uniform permutations using extension fields, which was illustrated with a construction of a 4-differentially uniform (n,n)-permutation. The permutation has optimum algebraic degree and very good nonlinearity. However, it was proved to be a permutation only for n odd. In this note, we investigate further the construction of differentially uniform permutations using extension fields, and construct a 4-differentially uniform (n,n)-permutation for any n. These permutations also have optimum algebraic degree and very good nonlinearity. Moreover, we consider a more general type of construction, and illustrate it with an example of a 4-differentially uniform (n,n)-permutation with good cryptographic properties.

Multicarrier communications including orthogonal frequency-division multiplexing (OFDM) is a technique which has been adopted for various wireless applications. However, a major drawback to the widespread acceptance of OFDM is the high peak-to-mean envelope power ratio (PMEPR) of uncoded OFDM signals. Finding methods for construction of sequences with low PMEPR is an active research area. In this paper, by employing some new shortened and extended Golay complementary pairs as the seeds, we enlarge the family size of near-complementary sequences given by Yu and Gong. We also show that the new set of sequences we obtained is just a reversal of the original set. Numerical results show that the enlarged family size is almost twice of the original one. Besides, the Hamming distances of the binary near-complementary sequences are also analyzed.

Based on Tu-Deng's conjecture and the Tu-Deng function, in 2010, X. Tang et al. proposed a class of Boolean functions in even variables with optimal algebraic degree, very high nonlinearity and optimal algebraic immunity. In this corresponding, we consider the concatenation of Tang's function and another Boolean function, and study its cryptographic properties. With this idea, we propose a class of 1-resilient Boolean functions in odd variables with optimal algebraic degree, good nonlinearity and suboptimal algebraic immunity based on Tu-Deng's conjecture.

In this note, we go further on the “basis exchange” idea presented in [2] by using Mobious inversion. We show that the matrix S1(f)S0(f)-1 has a nice form when f is chosen to be the majority function, where S1(f) is the matrix with row vectors υk(α) for all α ∈ 1f and S0(f)=S1(f ⊕ 1). And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.

In this paper, we explicitly construct a large class of symmetric Boolean functions on 2k variables with algebraic immunity not less than d, where integer k is given arbitrarily and d is a given suffix of k in binary representation. If let d = k, our constructed functions achieve the maximum algebraic immunity. Remarkably, 2⌊ log2k ⌋ + 2 symmetric Boolean functions on 2k variables with maximum algebraic immunity are constructed, which are much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than d is derived, which is 2⌊ log2d ⌋ + 2(k-d+1). As far as we know, this is the first lower bound of this kind.

A method to construct Boolean functions with maximum algebraic immunity have been proposed in . Based on that method, we propose a different method to construct Boolean functions on even variables with maximum algebraic immunity in this letter. By counting on our construction, a lower bound of the number of such Boolean functions is derived, which is the best among all the existing lower bounds.

It is known that Boolean functions used in stream ciphers should have good cryptographic properties to resist fast algebraic attacks. In this paper, we study a new class of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity and a high nonlinearity.

Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.