Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction

Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for the design of stream ciphers. In this paper, we solve the FCSR synthesis problem for multi-sequences by two rational approximation algorithms using lattice theory. One is based on the lattice reduction greedy algorithm proposed by Nguyen and Stehle (ACM Trans Algorithms (TALG) 5(4):46, 2009). The other is based on the LLL algorithm which is a polynomial time lattice reduction algorithm. Both of these rational approximation algorithms can find the smallest common FCSR for a given multi-sequence but with different numbers of known terms. When the number of sequences within the multi-sequence is less than or equal to 3, the former is suggested because it has better time complexity and fewer terms are needed. Otherwise, the latter will have better time complexity.