Joint linear complexity of multisequences consisting of linear recurring sequences


Fu F., Niederreiter H., Ozbudak F.

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, cilt.1, ss.3-29, 2009 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 1 Konu: 1
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1007/s12095-007-0001-4
  • Dergi Adı: CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES
  • Sayfa Sayıları: ss.3-29

Özet

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. In this paper, we study the joint linear complexity of multisequences consisting of linear recurring sequences. The expectation and variance of the joint linear complexity of random multisequences consisting of linear recurring sequences are determined. These results extend the corresponding results on the expectation and variance of the joint linear complexity of random periodic multisequences. Then we enumerate the multisequences consisting of linear recurring sequences with fixed joint linear complexity. A general formula for the appropriate counting function is derived. Some convenient closed-form expressions for the counting function are determined in special cases. Furthermore, we derive tight upper and lower bounds on the counting function in general. Some interesting relationships among the counting functions of certain cases are established. The generating polynomial for the distribution of joint linear complexities is determined. The proofs use new methods that enable us to obtain results of great generality.