More Web Proxy on the site http://driver.im/

article

Error linear complexity measures for multisequences

Authors:

Wilfried Meidl,

Harald Niederreiter,

Ayineedi VenkateswarluAuthors Info & Claims

Journal of Complexity, Volume 23, Issue 2

Pages 169 - 192

https://doi.org/10.1016/j.jco.2006.10.005

Published: 01 April 2007 Publication History

Abstract

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.

References

[1]

Algebraic Coding Theory. 1968. McGraw-Hill, New York.

[2]

Dai, Z., Imamura, K. and Yang, J., Asymptotic behavior of normalized linear complexity of multi-sequences. In: Helleseth, T., Sarwate, D., Song, H.-Y., Yang, K. (Eds.), Sequences and Their Applications---SETA 2004, Lecture Notes in Computer Science, vol. 3486. Springer, Berlin. pp. 129-142.

[3]

Dawson, E. and Simpson, L., Analysis and design issues for synchronous stream ciphers. In: Niederreiter, H. (Ed.), Coding Theory and Cryptography, World Scientific, Singapore. pp. 49-90.

[4]

Ding, C., Lower bounds on the weight complexities of cascaded binary sequences. In: Seberry, J., Pieprzyk, J. (Eds.), Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science, vol. 453. Springer, Berlin. pp. 39-43.

Digital Library

[5]

C. Ding, G. Xiao, W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Computer Science, vol. 561, Springer, Berlin, 1991.

[6]

Feng, X. and Dai, Z., Expected value of the linear complexity of two-dimensional binary sequences. In: Helleseth, T., Sarwate, D., Song, H.-Y., Yang, K. (Eds.), Sequences and Their Applications---SETA 2004, Lecture Notes in Computer Science, vol. 3486. Springer, Berlin. pp. 113-128.

[7]

Fu, F.-W., Niederreiter, H. and Su, M., The expectation and variance of the joint linear complexity of random periodic multisequences. J. Complexity. v21. 804-822.

[8]

P. Hawkes, M. Paddon, G.G. Rose, M. Wiggers de Vries, SSS, ECRYPT candidate, <http://www.ecrypt.eu.org/stream/ciphers/sss/sss.pdf>.

[9]

P. Hawkes, M. Paddon, G.G. Rose, M. Wiggers de Vries, NLS, ECRYPT candidate, <http://www.ecrypt.eu.org/stream/ciphers/nls/nls.pdf>.

[10]

Hawkes, P. and Rose, G.G., Exploiting multiples of the connection polynomial in word-oriented stream ciphers. In: Okamoto, T. (Ed.), Advances in Cryptology---ASIACRYPT 2000, Lecture Notes in Computer Science, vol. 1976. Springer, Berlin. pp. 303-316.

Digital Library

[11]

van Lint, J.H., Introduction to Coding Theory. 1982. Springer, New York.

Digital Library

[12]

Meidl, W. and Niederreiter, H., Counting functions and expected values for the k-error linear complexity. Finite Fields Appl. v8. 142-154.

[13]

Meidl, W. and Niederreiter, H., Linear complexity, k-error linear complexity, and the discrete Fourier transform. J. Complexity. v18. 87-103.

Digital Library

[14]

Meidl, W. and Niederreiter, H., The expected value of the joint linear complexity of periodic multisequences. J. Complexity. v19. 61-72.

Digital Library

[15]

Niederreiter, H., Linear complexity and related complexity measures for sequences. In: Johansson, T., Maitra, S. (Eds.), Progress in Cryptology---INDOCRYPT 2003, Lecture Notes in Computer Science, vol. 2904. Springer, Berlin. pp. 1-17.

[16]

Niederreiter, H., The probabilistic theory of the joint linear complexity of multisequences. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (Eds.), Sequences and Their Applications---SETA 2006, Lecture Notes in Computer Science, vol. 4086. Springer, Berlin. pp. 5-16.

Digital Library

[17]

Niederreiter, H. and Paschinger, H., Counting functions and expected values in the stability theory of stream ciphers. In: Ding, C., Helleseth, T., Niederreiter, H. (Eds.), Sequences and Their Applications, Springer, London. pp. 318-329.

[18]

Niederreiter, H. and Wang, L.-P., Proof of a conjecture on the joint linear complexity profile of multisequences. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (Eds.), Progress in Cryptology---INDOCRYPT 2005, Lecture Notes in Computer Science, vol. 3797. Springer, Berlin. pp. 13-22.

Digital Library

[19]

H. Niederreiter, L.-P. Wang, The asymptotic behavior of the joint linear complexity profile of multisequences, Monatsh. Math., to appear.

[20]

Rueppel, R.A., Analysis and Design of Stream Ciphers. 1986. Springer, Berlin.

Digital Library

[21]

Sakata, S., Extension of the Berlekamp--Massey algorithm to N dimensions. Inf. Comput. v84. 207-239.

Digital Library

[22]

B. Smeets, The linear complexity profile and experimental results on a randomness test of sequences over the field Fq, Technical Report, University of Lund, 1988.

[23]

Stamp, M. and Martin, C.F., An algorithm for the k-error linear complexity of binary sequences with period 2n. IEEE Trans. Inf. Theory. v39. 1398-1401.

[24]

Wang, L.-P. and Niederreiter, H., Enumeration results on the joint linear complexity of multisequences. Finite Fields Appl. v12. 613-637.

[25]

Wang, L.-P., Zhu, Y.-F. and Pei, D.-Y., On the lattice basis reduction multisequence synthesis algorithm. IEEE Trans. Inf. Theory. v50. 2905-2910.

Cited By

Gao ZFu F(2019)The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequenceTheoretical Computer Science10.5555/2912583.2912677411:44(3883-3893)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2912583.2912677
Xing CDing Y(2019)Multisequences with large linear and k-error linear complexity from Hermitian function fieldsIEEE Transactions on Information Theory10.1109/TIT.2009.202371455:8(3858-3863)Online publication date: 21-Nov-2019
https://dl.acm.org/doi/10.1109/TIT.2009.2023714
Hu HGong GFeng D(2009)New results on periodic sequences with large k-error linear complexityIEEE Transactions on Information Theory10.1109/TIT.2009.202756655:10(4687-4694)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TIT.2009.2027566
Show More Cited By

Index Terms

Error linear complexity measures for multisequences

Recommendations

Periodic multisequences with large error linear complexity

Generalizing the theory of k -error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23 (2), 169---192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A ...
Improved results on periodic multisequences with large error linear complexity

For multisequences there are various possibilities of defining analogs of the k-error linear complexity of single sequences. We consider the k-error joint linear complexity, the k-error F"q-linear complexity, and the k->-error joint linear complexity. ...
The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Complexity

Journal of Complexity Volume 23, Issue 2

April, 2007

147 pages

ISSN:0885-064X

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2007.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gao ZFu F(2019)The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequenceTheoretical Computer Science10.5555/2912583.2912677411:44(3883-3893)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2912583.2912677
Xing CDing Y(2019)Multisequences with large linear and k-error linear complexity from Hermitian function fieldsIEEE Transactions on Information Theory10.1109/TIT.2009.202371455:8(3858-3863)Online publication date: 21-Nov-2019
https://dl.acm.org/doi/10.1109/TIT.2009.2023714
Hu HGong GFeng D(2009)New results on periodic sequences with large k-error linear complexityIEEE Transactions on Information Theory10.1109/TIT.2009.202756655:10(4687-4694)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TIT.2009.2027566
Niederreiter HVenkateswarlu A(2008)Periodic multisequences with large error linear complexityDesigns, Codes and Cryptography10.1007/s10623-008-9174-x49:1-3(33-45)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1007/s10623-008-9174-x

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents