Title :
The linear complexity of the self-shrinking generator
Author :
Blackburn, Simon R.
Author_Institution :
Dept. of Math., London Univ., UK
fDate :
9/1/1999 12:00:00 AM
Abstract :
The self-shrinking generator, a stream cipher due to Meier and Staffelbach (see Advances in Cryptology-EUROCRYPT´94, Berlin, Germany, p.205-14, 1995 and Lecture Notes in Computer Science, vol.950), uses the output of a primitive binary linear-feedback shift register (LFSR) of length n to generate a keystream sequence of period dividing 2n-1 . The article proves that the linear complexity of the keystream is at most 2n-1-(n-2). This confirms the surprising experimental observations of Meier and Staffelbach
Keywords :
binary sequences; circuit feedback; computational complexity; cryptography; LFSR; binary linear-feedback shift register; experimental observations; finite field theory; keystream sequence; linear complexity; self-shrinking generator; stream cipher; Binary sequences; Complexity theory; Cryptography; Galois fields; Mathematics; Security; Shift registers; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
