×

Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform. (English) Zbl 1004.68066

Summary: Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences \(S\) with given prime period length \(N\) and linear complexity \(L_{N,0}(S)= c\) as well as the expected value of the linear complexity of \(N\)-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the \(k\)-error linear complexity \(L_{N,k}(S)\) of sequences \(S\) with period length \(N\). For some \(k\) and \(c\) we determine the number of periodic sequences \(S\) with given period length \(N\) and \(L_{N,k}(S)=c\). For prime \(N\) we establish a lower bound on the expected value of the \(k\)-error linear complexity.

MSC:

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
11Y16 Number-theoretic algorithms; complexity
65T50 Numerical methods for discrete and fast Fourier transforms
68W40 Analysis of algorithms
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blahut, R. E., Theory and Practice of Error Control Codes (1983), Addison-Wesley: Addison-Wesley Reading · Zbl 0577.94013
[2] Jungnickel, D., Finite Fields: Structure and Arithmetics (1993), Bibliographisches Institut: Bibliographisches Institut Mannheim · Zbl 0779.11058
[3] Kaida, T.; Uehara, S.; Imamura, K., A new algorithm for the \(k\)-error linear complexity of sequences over \(GF (p^m )\) with period \(p^n\), (Ding, C.; Helleseth, T.; Niederreiter, H., Sequences and Their Applications (1999), Springer: Springer London), 284-296 · Zbl 1007.11082
[4] Lidl, R.; Niederreiter, H., Introduction to Finite Fields and Their Applications (1994), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0820.11072
[5] Massey, J. L., Review of R. E. Blahut, Theory and Practice of Error Control Codes, IEEE Trans. Inform. Theory, 31, 553 (1985)
[6] Massey, J. L.; Serconek, S., A Fourier transform approach to the linear complexity of nonlinearly filtered sequences, (Desmedt, Y. G., Advances in Cryptology—Crypto ’94. Advances in Cryptology—Crypto ’94, Lecture Notes in Computer Science, 839 (1994), Springer: Springer Berlin), 332-340 · Zbl 0939.94562
[7] Niederreiter, H.; Paschinger, H., Counting functions and expected values in the stability theory of stream ciphers, (Ding, C.; Helleseth, T.; Niederreiter, H., Sequences and Their Applications (1999), Springer: Springer London), 318-329 · Zbl 1015.94536
[8] Pless, V., Introduction to the Theory of Error-Correcting Codes (1989), Wiley-Interscience: Wiley-Interscience New York · Zbl 0698.94007
[9] Rueppel, R. A., Analysis and Design of Stream Ciphers (1986), Springer: Springer Berlin · Zbl 0654.68044
[10] Rueppel, R. A., Stream ciphers, (Simmons, G. J., Contemporary Cryptology: The Science of Information Integrity (1992), IEEE Press: IEEE Press New York), 65-134
[11] Stamp, M.; Martin, C. F., An algorithm for the \(k\)-error linear complexity of binary sequences with period \(2^n\), IEEE Trans. Inform. Theory, 39, 1398-1401 (1993) · Zbl 0801.94009
[12] van Tilborg, H. C.A., An Introduction to Cryptology (1988), Kluwer Academic: Kluwer Academic Boston · Zbl 0699.94005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.