On the calculation of the linear equivalence bias of jump controlled linear finite state machines

Abstract

Jump controlled linear ¯nite state machines were introduced sev-
eral years ago as building blocks for stream ciphers that can e±ciently be imple-
mented in hardware and have intrinsically good side channel resistance. These
constructions have found their way in concrete stream cipher designs. The bias in
the distribution of linear relations of low degree in the key stream is important for
the cryptographic strength of these stream ciphers. Recently, an algorithm was
presented by the author to determine this bias. In this paper a new algorithm is
introduced, that makes use of the properties of jump registers and has sub ex-
ponential order in the degree of the characteristic polynomial of the linear ¯nite
state machine.