Linear Complexity of Hidden Weighted Bit Functions

doi:10.3778/j.issn.1673-9418.2203038

Abstract

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]-错线性复杂度

CHEN Zhiru, FENG Ligang, ZHU Youwen. Linear Complexity of Hidden Weighted Bit Functions[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(8): 1974-1980.

陈芷如, 冯立刚, 朱友文. 隐性权位比特函数的线性复杂度[J]. 计算机科学与探索, 2023, 17(8): 1974-1980.

References

[1] DING C, XIAO G, SHAN W. The stability theory of stream ciphers[M]. Berlin, Heidelberg: Springer, 1991.
[2] 张斌, 徐超, 冯登国. 流密码的设计与分析: 回顾、现在与展望[J]. 密码学报，2016, 3(6): 527-545.
ZHANG B, XU C, FENG D G. Design and analysis of stream ciphers: past, present and future directions[J]. Journal of Cryptologic Research, 2016, 3(6): 527-545.
[3] KRAUSE M. BDD-based cryptanalysis of keystream generators[C]//LNCS 2332: Proceedings of the 2002 International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, Apr 28-May 2, 2002. Berlin, Heidelberg: Springer, 2002: 222-237.
[4] BRYANT R E. On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication[J]. IEEE Transactions on Computers, 1991, 40(2): 205-213.
[5] WANG Q, CARLET C, STANICA P, et al. Cryptographic properties of the hidden weighted bit function[J]. Discrete Applied Mathematics, 2014, 174: 1-10.
[6] WANG Q, TAN C. On the second-order nonlinearity of the hidden weighted bit function[J]. Discrete Applied Mathematics, 2016, 215: 197-202.
[7] WANG Q,?TAN C, FOO T. A family of cryptographically significant Boolean functions based on the hidden weighted bit function[C]//LNCS 8565: Proceedings of the 16th Inter-national Conference on Information Security and Cryptology, Seoul, Nov 27-29, 2013. Cham: Springer, 2014: 311-322.
[8] WANG Q,?TAN C, STANICA P. Concatenations of the hidden weighted bit function and their cryptographic properties[J].?Advances in Mathematics of Communications, 2014,?8(2):?153-165.
[9] SALAGEAN A. On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two[J]. IEEE Transactions on Information Theory, 2005, 51(3): 1145-1150.
[10] MASSEY J. Shift-register synthesis and BCH decoding[J]. IEEE Transactions on Information Theory, 1969, 15(1): 122-127.
[11] GAMES R, CHAN A. A fast algorithm for determining the complexity of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory, 1983, 29(1): 144-146.
[12] STAMP M, MARTIN C F. An algorithm for the k-error linear complexity of binary sequences with period 2n[J]. IEEE Transactions on Information Theory, 1993, 39(4): 1398-1401.
[13] ZHU F, QI W. The 2-error linear complexity of 2n-periodic binary sequences with linear complexity 2n-1[J]. Journal of Electronics, 2007, 24(3): 390-395.
[14] 王喜凤, 张伟, 周建钦. 具有第二下降点6错线性复杂度的2n-周期序列[J]. 计算机科学与探索, 2016, 10(6): 838-846.
WANG X F, ZHANG W, ZHOU J Q. 2n-periodic binary sequences with 6-error linear complexity as the second descent point[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(6): 838-846.
[15] 周建钦. 2n周期平衡二元序列的2错线性复杂度[J]. 苏州科技学院学报(自然科学版), 2013, 30(4): 1-7.
ZHOU J Q. On the 2-error linear complexity of 2n-periodic balanced binary sequences[J]. Journal of Suzhou University of Science and Technology (Natural Science), 2013, 30(4): 1-7.
[16] ZHOU J, LIU W. The k-error linear complexity distribution for 2n-periodic binary sequences[J]. Designs, Codes and Cryptography, 2014, 73(1): 55-75.
[17] CHANG Z, KE P. On the error linear complexity spectrum of binary sequences with period of power of two[J]. Chinese Journal of Electronics, 2015, 24(2): 366-372.
[18] PAN W, BAO Z, LIN D, et al. The linear complexity and 2-error linear complexity distribution of 2n-periodic binary sequences with fixed Hamming weight[C]//LNCS 9977: Proceedings of the 2016 International Conference on Infor-mation and Communications Security, Singapore, Nov 29-Dec 2,?2016. Cham: Springer, 2016: 107-123.
[19] HASSE H. Theorie der h?heren differentiale in einem algebraischen funktionenk?rper mit vollkommenem kons-tantenk?rper bei beliebiger charakteristik[J]. Journal Fur Die Reine Und Angewandte Mathematik, 1936, 175: 50-54.
[20] NIEDERREITER H, WINTERHOF A. Applied number theory[M]. Berlin, Heidelberg: Springer, 2015.
[21] SUN Y, WANG Q, YAN T. The exact autocorrelation distribution and 2-adic complexity of a class of binary sequ-ences with almost optimal autocorrelation[J]. Cryptography Communications, 2018, 10(3): 467-477.