Abstract
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 Stehlé (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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ajtai M.: The shortest vector problem in \( L^2\) is NP-hard for randomized reductions. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing STOC 98, pp. 10–19. ACM, New York (1998)
Arnault F., Berger T.P., Necer A.: Feedback with carry shift registers synthesis with the Euclidean algorithm. IEEE Trans. Inf. Theory 50(5), 910–917 (2004).
Dwork C.: Lattices and their application to cryptography. Stanford University, Lecture Notes (1998).
Feng G., Tzeng K.: A generalized Euclidean algorithm for multisequence shift-register synthesis. IEEE Trans. Inf. Theory 35(3), 584–594 (1989).
Goresky M., Klapper A.: Algebraic Shift Register Sequences. Cambridge University Press, Cambridge (2012).
Hu H., Hu L., Feng D.: On the expected value of the joint 2-adic complexity of periodic binary multisequences. In: Gong G., Helleseth T., Song H., Yang K. (eds.) Sequences and Their Applications—SETA 2006, pp. 199–208. Springer, Berlin (2006).
Klapper A., Goresky M.: Cryptanalysis based on 2-adic rational approximation. In: Coppersmith D. (ed.) Advances in Cryptology—CRYPTO’95, pp. 262–273. Springer, Berlin (1995).
Klapper A., Goresky M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10(2), 111–147 (1997).
Klapper A., Xu J.: Register synthesis for algebraic feedback shift registers based on non-primes. Des. Codes Cryptogr. 31(3), 227–250 (2004).
Lenstra A., Lenstra H., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).
Massey J.L.: Shift register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969).
Nguyen P.Q., Stehlé D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009).
Nguyen Phong Q., Stehlé D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorithms (TALG) 5(4), 46 (2009).
Sakata S.: Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array. J. Symb. Comput. 5(3), 321–337 (1988).
Schmidt G., Sidorenko V.R.: Multi-sequence linear shift-register synthesis: the varying length case. In: 2006 IEEE International Symposium on Information Theory, pp. 1738–1742 (2006).
Wang L., Zhu Y.: \(f [x]\)-lattice basis reduction algorithm and multisequence synthesis. Sci. China Ser. Inf. Sci. 44(5), 321–328 (2001).
Yang M., Lin D., Xuan G.: Generalized Fourier transform and the joint \(N\)-adic complexity of a multisequence. IEICE Trans. Fundam. Electron. Comput. Sci. E97.A(9), 1982–1986 (2014).
Zhao L., Wen Q.: On the joint 2-adic complexity of binary multisequences. RAIRO Theor. Inf. Appl. 46(03), 401–412 (2012).
Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant No. CNS-1420227. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation. Zhixiong Chen was partially supported by the National Natural Science Foundation of China under Grant No. 61373140 and China Scholarship Council.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by L. Perret.
Rights and permissions
About this article
Cite this article
Liu, W., Klapper, A. & Chen, Z. Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction. Des. Codes Cryptogr. 86, 1023–1038 (2018). https://doi.org/10.1007/s10623-017-0375-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-017-0375-z