M. Sindhu (Amrita Vishwa Vidyapeetham, India), S. Kumar Sajan (Amrita Vishwa Vidyapeetham, India) and M. Sethumadhavan (Amrita Vishwa Vidyapeetham, India)

Copyright: © 2011
|Pages: 10

DOI: 10.4018/978-1-60960-123-2.ch017

Chapter Preview

TopIn complexity measures for sequences over finite fields, such as the linear complexity and the *k* – error linear complexity is of great relevance to cryptology, in particular, to the area of stream ciphers. There are basically two types of requirements for suitability of a keystream generated by a stream cipher. One of the requirements is the keystream sequence must pass various statistical tests for randomness. This is to make it difficult to capture any information about the plaintext by an attacker from any possible statistical deficiencies in the keystream. The second is that it should be very hard to predict the entire keystream from the knowledge of a part of it. For this purpose, one is interested to know how hard a sequence might be to predict. This requirement leads to the study of several complexity measures for sequences. The most significant complexity measure is the linear complexity: length of the shortest linear recurrence relation satisfied by the sequence and related concept of *k*-error linear complexity (see Kaida, T. (1999)).

The major problem in stream cipher cryptography is generating a pseudorandom sequence of elements from a short random key. We mainly use LFSRs for the construction of stream ciphers. On the other hand, LFSRs can also be used to mount attacks on stream cipher systems. This attack is based on the Berlekamp-Massey algorithm: given a sequence S with terms in a finite field *F _{q}* of length

To take advantage of the general purpose processing units employed in the present day computers over public/private networks, we need the keystream to be a sequence of a few bytes, instead of bits. Such keystream generators are better suited for software implementation, and provide high throughput. Such ciphers are called word based (or vectorized) ciphers since they produce more than one bit per clock cycle. The theory of such stream ciphers requires the study of the complexity measures for multisequences, i.e., for parallel streams of finitely many sequences. In this direction, the joint linear complexity and the joint linear complexity profile of multisequences have been investigated. The theory of *k*-error joint linear complexity of multisequences has been investigated recently.

An *m* fold *N* periodic multisequence S can be interpreted as an *m* × *N* matrix over *F _{q}*. For defining the

**1.1 Definition:** Let *S*=(*S*^{(1)}, *S*^{(2)},…,*S*^{(}^{m}^{)}) and *T*=(*T*^{(1)}, *T*^{(2)},…,*T*^{(}^{m}^{)}) be two *m* fold *N* periodic multisequences over *F _{q}*. We define the term distance

Search this Book:

Reset