Linear Complexity of Hidden Weighted Bit Functions

Abstract

Boolean functions are crucial primitive in block cipher and are also used to design pseudorandom sequences. They play a crucial role in the design of symmetric cryptography and its analysis, and the study on the cryptographic properties of Boolean functions is a hotspot in cryptography. The hidden weighted bit functions (HWBF) are paid attention since they have many “good” cryptographic measures. However, there are no results on their linear complexity in the literature. Therefore, this paper discusses a family of binary sequences of period [2n]built by using [n-]variable HWBF (hidden weighted bit functions). It is proven that such sequences are balanced with maximal linear complexity using mathematical method. The 2-error linear complexity of the sequences is also determined in terms of the Hasse derivative and Lucas congruence. When [n(mod4)∈{0,1,3}], the values of the 2-error linear complexity are maximal. Results indicate that such sequences are of “good” cryptographic measures.

Keywords

• stream cipher; pseudorandom sequences; binary sequences; hidden weighted bit function; linear complexity; [k-]error linear complexity