AN ALGORITHM FOR THE K-ERROR LINEAR COMPLEXITY OF BINARY SEQUENCES WITH PERIOD-2(N)

被引：123
作者：
STAMP, M [1 ]
MARTIN, CF [1 ]
机构：
[1] TEXAS TECH UNIV,DEPT MATH,LUBBOCK,TX 79409
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 1993年 / 39卷 / 04期
基金：
美国国家科学基金会; 美国国家航空航天局;
关键词：
LINEAR COMPLEXITY; K-ERROR LINEAR COMPLEXITY; ALGORITHM;
D O I：
10.1109/18.243455
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Certain applications require pseudo-random sequences which are unpredictable in the sense that recovering more of the sequence from a short segment must be computationally infeasible. It is shown that linear complexity is useful in determining such sequences. A generalized linear complexity which has application to the security of stream ciphers is proposed and an efficient algorithm is given for the case where the sequence is binary with period 2n. This new algorithm generalizes an algorithm due to Games and Chan.
引用
收藏
页码：1398 / 1401
页数：4
相关论文
共 13 条
[1]   HOW TO GENERATE CRYPTOGRAPHICALLY STRONG SEQUENCES OF PSEUDO-RANDOM BITS [J].
BLUM, M ;
MICALI, S .
SIAM JOURNAL ON COMPUTING, 1984, 13 (04) :850-864
[2]  
DAWSON E, 1990, LONDON MATHH SOC LEC, V154, P106
[3]   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
[4]  
GOLOMB SW, 1987, SHIFT REGISTER SEQUE
[5]   GENERATION OF BINARY SEQUENCES WITH CONTROLLABLE COMPLEXITY [J].
GROTH, EJ .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1971, 17 (03) :288-+
[6]   ANALYSIS OF STRUCTURE AND COMPLEXITY OF NONLINEAR BINARY SEQUENCE GENERATORS [J].
KEY, EL .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :732-736
[7]  
MASSEY JL, 1969, IEEE T INFORM THEORY, V15, P122, DOI 10.1109/TIT.1969.1054260
[8]  
McEliece R.J., 1987, FINITE FIELDS COMPUT, V1st, DOI [10.1007/978-1-4613-1983-2, DOI 10.1007/978-1-4613-1983-2]
[9]  
RUEPPEL RA, 1986, ANAL DESIGN STREAM C
[10]  
SAFAVINAINI RS, 1990, LONDON MATH SOC LECT, V154, P129
12