Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (8): 1974-1980.DOI: 10.3778/j.issn.1673-9418.2203038

• Network·Security • Previous Articles     Next Articles

Linear Complexity of Hidden Weighted Bit Functions

CHEN Zhiru, FENG Ligang, ZHU Youwen   

  1. School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211100, China
  • Online:2023-08-01 Published:2023-08-01

隐性权位比特函数的线性复杂度

陈芷如,冯立刚,朱友文   

  1. 南京航空航天大学 计算机科学与技术学院,南京 211100

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.

Key words: stream cipher, pseudorandom sequences, binary sequences, hidden weighted bit function, linear complexity, [k-]error linear complexity

摘要: 布尔函数既是分组密码的关键部件,也是设计序列的重要方式,在对称密码的设计与分析中起着重要的作用,关于布尔函数的密码学性质研究一直是密码界研究的热点。隐性权位比特函数(HWBF)因具有平衡性、高非线性度等诸多“好”的密码学特性而备受关注,而它的线性复杂度指标在文献中尚无相关结论。因此,讨论了采用[n]-元HWBF函数构造周期为[2n]的二元伪随机序列,从数学理论的角度证明该序列是具有最大线性复杂度的平衡序列。同时,应用数论中的Hasse导数和Lucas同余式,计算出该序列的2-错线性复杂度的取值,其中当[n(mod4)∈{0,1,3}]时,该序列的2-错线性复杂度达到最大值。结果表明,该序列是一类具备多种密码学指标的优质序列。

关键词: 序列密码, 伪随机序列, 二元序列, 隐性权位比特函数, 线性复杂度, [k]-错线性复杂度