Determining the k-error joint linear complexity spectrum for a binary multisequence with period pn

被引：0

作者：

Li, Fulin ^{[1
]}

Zhu, Shixin ^{[1
]}

Hu, Honggang ^{[2
]}

Jiang, Ting ^{[1
]}

机构：

[1] Hefei Univ Technol, Dept Appl Math, Hefei 230009, Anhui, Peoples R China

[2] Univ Sci & Technol China, Sch Informat Sci & Technol, Hefei 230027, Anhui, Peoples R China

来源：

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES | 2016年 / 8卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Stream ciphers; Multisequence; Algorithm; Error joint linear complexity spectrum; FAST ALGORITHM; SEQUENCE;

D O I：

10.1007/s12095-015-0157-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Recent developments in word-based stream ciphers present the study on multi-sequences. The joint linear complexity and k-error joint linear complexity are fundamental concepts for the assessment of multisequences. The k-error joint linear complexity spectrum contains all the information about how the joint linear complexity of a multisequence decreases as the number k of allowed bit changes increases. In this paper, we present an efficient algorithm by which the k-error joint linear complexity spectrum for a t-fold p(n)-periodic binary multisequence can be entirely determined using O(tp(n) log p) bit operations, where p is an odd prime, 2 is a primitive root modulo p(2) and n is a positive integer.

引用

页码：513 / 523

页数：11

共 17 条

[1]

[Anonymous], 1991, LECT NOTES COMPUTER

[2]

Berlekamp E.R., 2015, ALGEBRAIC CODING THE

[3]

DING CS, 1990, LECT NOTES COMPUT SC, V453, P39

[4] A FAST ALGORITHM FOR DETERMINING THE COMPLEXITY OF A BINARY SEQUENCE WITH PERIOD 2N [J].

GAMES, RA ;

CHAN, AH .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, 29 (01) :144-146

[5] Computing the error linear complexity spectrum of a binary sequence of period 2n [J].

Lauder, AGB ;

Paterson, KG .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (01) :273-280

[6]

Li Fu-lin, 2013, Journal of China Universities of Posts and Telecommunications, V20, P96, DOI 10.1016/S1005-8885(13)60114-4

[7]

MASSEY JL, 1969, IEEE T INFORM THEORY, V15, P122, DOI 10.1109/TIT.1969.1054260

[8] How many bits have to be changed to decrease the linear complexity? [J].

Meidl, W .

DESIGNS CODES AND CRYPTOGRAPHY, 2004, 33 (02) :109-122

[9] Error linear complexity measures for multisequences [J].

Meidl, Wilfried ;

Niederreiter, Harald ;

Venkateswarlu, Ayineedi .

JOURNAL OF COMPLEXITY, 2007, 23 (02) :169-192

[10] Periodic sequences with large k-error linear complexity [J].

Niederreiter, H .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (02) :501-505

← 1 2 →