Construction of Transition Matrices for Ternary Ring Feedback With Carry Shift Registers

Since the linear structure of linear feedback shift registers (LFSRs) has a drawback that may lead to attacks against LFSR-based stream ciphers, feedback with carry shift registers (FCSRs) have been proposed as an alternative to LFSRs for the design of stream ciphers. However, some weaknesses in stream ciphers based on Fibonacci or Galois FCSRs have been exposed. Then, a new ring FCSRs has been proposed which is based on a matrix definition. This new approach generalizes Galois and Fibonacci FCSRs, and circumvents some of their severe weaknesses. In this paper, we give an affirmative answer to the following conjecture: for any given connection integer there exists a ternary transition matrix with a critical path of length 1 and fan-out of 2. We also give an algorithm to construct such transition matrices with given connection integer.