Linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs) can be used in cryptography, communications and circuit testings. In 2014, Gu and Klapper investigated the imbalance properties of FCSR sequences and gave two bounds for the one symbol and two consecutive symbol cases, which were then improved in 2015. In 2016, the imbalance properties of LFSR subsequences were studied and an upper bound was deduced. In this paper, we revisit the imbalance properties of the above sequences and improve upon their bounds.

Boolean functions play an important role in symmetric ciphers. Various cryptographic criteria such as nonlinearity, balancedness, correlation immunity and transparency order are closely related to the Walsh support of a Boolean function. However, we did not know more about the possible structure of Walsh supports of Boolean functions until Carlet and Mesnager conducted an in-depth study of Walsh supports for Boolean functions in 2005, proposing a class of n-variable balanced Boolean functions with Walsh support$\mathbb{F}_{2}^{n}\backslash \{0\}$, for$n\geq 10$. For$n\leq 6$, it can be verified using the computer that there is no Boolean function with the Walsh Support$\mathbb{F}_{2}^{n}\backslash \{0\}$. Nevertheless, for$n=7,8,9$, whether there is an n-variable Boolean function whose Walsh support is$\mathbb{F}_{2}^{n}\backslash \{0\}$has been an open problem for many years. In this paper, we aim to solve this problem. For$n=7$, based on the technique of concatenation, we obtain a 7-variable function with Walsh support$\mathbb{F}_{2}^{n}\backslash \{a\}$through finding two 6-variable Boolean functions whose Walsh spectra are equal or opposite numbers to each other at only one point. Then, using the linear transformation, we naturally get a 7 -variable balanced Boolean function with Walsh support$\mathbb{F}_{2}^{n}\backslash \{0\}$. For$n=8,9$, we construct mathematically a balanced Boolean function whose Walsh support is$\mathbb{F}_{2}^{n}\backslash \{0\}$respectively. Therefore, we solve the above open problem completely.

We prove the covering radius of the third-order Reed-Muller code$\mathrm {RM}(3,7)$is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of$\mathrm {RM}(3,7)$is the maximum third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of$\mathrm {RM}(6,6)/\mathrm {RM}(3,6)$, we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6, 10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the third-order nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.

Transparency order, proposed by Prouff in 2005 and redefined by Chakraborty et al. in 2017, is a property to assess the resistance of a Boolean function or an S-box to Differential Power Analysis (DPA) attacks. In this paper, we develop an efficient algorithm based on the Gradient Descent algorithm, and search for balanced functions with good transparency order and high nonlinearity in the rotation symmetric Boolean functions (RSBFs) class. As a result, we find some cryptographically significant Boolean functions whose resistance to DPA attacks is much better than others obtained previously.

Feedback with carry shift registers (FCSRs) were introduced by Klapper and Goresky in 1994, and they can be used to design stream ciphers. In 2011, Lee and Park [10] put forward a software implementation for word-based FCSRs, and the sequences generated by those FCSRs are half-l-sequences. In SETA 2014, Gu and Klapper [7] investigated the imbalance properties of half-l-sequences and gave two bounds for the one symbol and two consecutive symbol cases. In this paper, we revisit the imbalance properties of half-l-sequences and deduce two new bounds which improve upon the bounds given by Gu and Klapper largely.

To resist those known attacks, Boolean functions used in stream ciphers should have large input size (e.g. 32-variable). However, up to now, for n > 20, very few n-variable Boolean function with good cryptographic properties can be implemented efficiently. This paper tries to solve this problem, and puts forward a method to construct cryptographically significant Boolean functions with large input size. The functions constructed by us have good cryptographic properties, and thus can resist all the main attacks. Moreover, they can be implemented efficiently. Hence, they can be used to design the real-life cipher.

In this study, the authors investigate the resistance of Boolean functions against fast algebraic attacks and deduce a bound between fast algebraic immunity and higher-order non-linearity (it is the first time that a bound between these two cryptographic criteria is given). The authors then show that the fast algebraic immunity of the following two classes of Boolean functions is not good: (a) The repaired functions of the Tu–Deng function proposed by Carlet. The Tu–Deng function has optimum algebraic degree, optimum algebraic immunity and a very good non-linearity. However, it is weak against fast algebraic attacks. Carlet found this weakness and also tried to repair it. (b) An infinite class of balanced functions proposed by Tang et al., having optimum algebraic degree, optimum algebraic immunity and a very high non-linearity.

It is known that Boolean functions used in stream and block ciphers should have good cryptographic properties to resist algebraic attacks. Up until now, there have been several constructions of Boolean functions achieving optimum algebraic immunity. However, most of their nonlinearities are very low. Carlet and Feng studied a class of Boolean functions with optimum algebraic immunity and deduced the lower bound of its nonlinearity, which is good, but not very high. Moreover, the main practical problem with this construction is that it cannot be implemented efficiently. In this paper, we put forward a new method to construct cryptographically significant Boolean functions by using primitive polynomials, and construct three infinite classes of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity, and a high nonlinearity.