logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 3: 032107(2016) https://doi.org/10.1007/s11432-015-5302-1

On the matrix feedback shift register synthesis for matrix sequences

More info
  • ReceivedDec 8, 2014
  • AcceptedJan 4, 2015
  • PublishedNov 11, 2015

Abstract

in this paper, a generalization of the linear feedback shift register synthesis problem is presented for synthesizing minimum-length matrix feedback shift registers (MFSRs for short) to generate prescribed matrix sequences and so a new complexity measure, that is, matrix complexity, is introduced. This problem is closely related to the minimal partial realization in linear systems and so can be solved through any minimal partial realization algorithm. All minimum-length MFSRs capable of generating a given matrix sequence with finite length are characterized and a necessary and sufficient condition for the uniqueness issue is obtained. furthermore, the asymptotic behavior of the matrix complexity profile of random vector sequences is determined.


Funded by

National Natural Science Foundation of China(61003291)

national Basic Research Program of China(973 Program)

"source" : null , "contract" : "2013CB834203"

National Natural Science Foundation of China(61170289)


References

[1] Dawson E, Simpson L. Analysis and design issues for synchronous stream ciphers. In: Niederreiter H, ed. Coding Theory and Cryptology. Singapore: World Scientific, 2002. 49--90. Google Scholar

[2] Ekdahl P, Johansson T. A new version of the stream ciphers SNOW. In: Proceedings of 9th Annual International Workshop on Selected Areas in Cryptography, Newfoundland, 2002. 47--61. Google Scholar

[3] Hawkes P, Rose G G. Exploiting multiples of the connection polynomial in word-oriented stream ciphers. In: Proceedings of 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, 2000. 303--316. Google Scholar

[4] Niederreiter H. Linear Alg Appl, 1993, 192: 301-328 CrossRef Google Scholar

[5] Tsaban B, Vishne U. Finite Fields Appl, 2002, 8: 256-267 CrossRef Google Scholar

[6] Zeng G, Han W, He K. High efficiency feedback shift register: $\sigma$-LFSR. Cryptology ePrint Archive, Report 2007/114, 2007. Google Scholar

[7] Zeng G, He K, Han W. Sci China Ser-F: Inf Sci, 2007, 50: 359-372 Google Scholar

[8] Zeng G, Yang Y, Han W , et al. Word oriented cascade jump $\sigma$-LFSR. In: Proceedings of 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Tarragona, 2009. 127--136. Google Scholar

[9] Berlekamp E R. Algebraic Coding Theory. New York: McGraw-Hill, 1968. Google Scholar

[10] Massey J L. IEEE Trans Inform Theory, 1969, 15: 122-127 CrossRef Google Scholar

[11] Dai Z D, Wang K P, Ye D F. Adv Math, 2004, 33: 246-248 Google Scholar

[12] Dai Z D, Wang K P, Ye D F. Acta Arithmet, 2006, 122: 1-16 CrossRef Google Scholar

[13] Dai Z D, Yang J H. Finite Fields Appl, 2006, 12: 379-402 CrossRef Google Scholar

[14] Ding C S. Proof of Massey's conjectured algorithm. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Davos, 1988. 345--349. Google Scholar

[15] Feng G L, Tzeng K K. IEEE Trans Inform Theory, 1991, 37: 1274-1287 CrossRef Google Scholar

[16] Wang L P, Zhu Y F, Pei D Y. IEEE Trans Inform Theory, 2004, 50: 2905-2910 CrossRef Google Scholar

[17] Kaltofen F, Yuhasz G. ACM Trans Algorithm, 2013, 9: 33-2910 Google Scholar

[18] Kaltofen F, Yuhasz G. Linear Alg Appl, 2013, 439: 2515-2526 CrossRef Google Scholar

[19] Antoulas A C. IEEE Trans Automat Control, 1985, 31: 1121-1135 Google Scholar

[20] Dickinson B W, Morf M, Kailath D. IEEE Trans Automat Control, 1974, 19: 31-38 CrossRef Google Scholar

[21] Gragg W B, Lindquist A. Linear Alg Appl, 1983, 50: 277-319 CrossRef Google Scholar

[22] Kuijper M. Syst Contr Lett, 1997, 31: 225-233 CrossRef Google Scholar

[23] van Barel M, Bultheel M A. Linear Alg Appl, 1997, 254: 527-551 CrossRef Google Scholar

[24] Wang L P. A lattice-based minimal partial realization algorithm. In: Proceedings of 5th International Conference on Sequences and Their Applications, Lexington, 2008. 278--289. Google Scholar

[25] Wang L P. Cryptogr Commun, 2011, 3: 29-42 CrossRef Google Scholar

[26] Wang L P. Lagrange interpolation polynomials and generalized Reed-Solomon codes over rings of matrices. In: Proceedings of IEEE International Symposium on Information Theory, Cambridge, 2012. 3098--3100. Google Scholar

[27] Quintin G, Barbier M, Chabot C. IEEE Trans Inform Theory, 2013, 59: 5882-5897 CrossRef Google Scholar

[28] Dai Z D, Imamura K, Yang J H. Asymptotic behavior of normalized linear complexity of multi-sequences. In: Proceeding of 3rd International Conference on Sequences and Their Applications, Seoul, 2004. 126--142. Google Scholar

[29] Niederreiter H, Wang L P. Proof of a conjecture on the joint linear complexity profile of multisequences. In: Proceeding of 6th International Conference on Cryptology in India, Bangalore, 2005. 13--22. Google Scholar

[30] Niederreiter H, Wang L P. Monatsh Math, 2007, 150: 141-155 CrossRef Google Scholar

[31] Niederreiter H, Vielhaber M, Wang L P. Sci China Inf Sci, 2012, 55: 165-170 CrossRef Google Scholar

[32] Wang L P, Niederreiter H. Finite Fields Appl, 2006, 12: 613-637 CrossRef Google Scholar

[33] Mahler K. Ann Math, 1941, 42: 488-522 CrossRef Google Scholar

[34] Couture R, L'Ecuyer P. Math Comput, 2000, 69: 757-765 Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1