Periodic sequences with maximal linear complexity and large \(k\)-error linear complexity (Q1422205): Difference between revisions

It is well known that sequences to be used as keystreams in stream ciphers should possess a large linear complexity. For cryptographic purposes, however, it is also required that altering a few terms of such a sequence should not cause a significant decrease in its linear complexity. This leads to the concept of \(k\)-error linear complexity. This concept has been studied previously, and it has been shown that under certain conditions there exist \(N\)-periodic sequences with maximal linear complexity and large \(k\)-error linear complexity. For practical purposes however, the existence of such sequences is not enough as these are useful only if a large number of sequences actually satisfy the conditions. In the paper a lower bound on the number of \(N\)-periodic sequences with maximal linear complexity and \(k\)-error linear complexity close to \(N\) is given. Also conditions under which the overwhelming majority of all \(N\)-periodic sequences with linear complexity \(N\) have a \(k\)-error linear complexity close to \(N\) for relatively large values of \(k\) are shown.