Searching Short Recurrences of Nonlinear Shift Registers via Directed Acyclic Graphs

详细信息    查看全文

• 作者：Lin Wang (18)
  Bing Shen (18)
  TongXu Qiao (19)
  
• 关键词：nonlinear feedback shift register ; directed acyclic graph ; topological ordering ; dependence graph ; feedback graph
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7537
• 期：1
• 页码：57-76
• 全文大小：240KB
• 参考文献：1. Adriansyah, A., van Dongen, B.F., van der Aalst, W.M.P.: Towards Robust Conformance Checking. In: zur Muehlen, M., Su, J. (eds.) BPM 2010 Workshops. LNBIP, vol.聽66, pp. 122鈥?33. Springer, Heidelberg (2011) CrossRef
  2. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer (2008)
  3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)
  4. De Canni猫re, C., Preneel, B.: Trivium: a Stream Cipher Construction Inspired by Block Cipher Design Principles. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/021, http://www.ecrypt.eu.org/stream/papersdir/2006/021
  5. De Canni猫re, C., Preneel, B.: Trivium . In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol.聽4986, pp. 244鈥?66. Springer, Heidelberg (2008) CrossRef
  6. Chabloz, J., Mansouri, S.S., Dubrova, E.: An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence. In: Carlet, C., Pott, A. (eds.) SETA 2010. LNCS, vol.聽6338, pp. 41鈥?4. Springer, Heidelberg (2010) CrossRef
  7. Daemen, J., Rijmen, V.: The Design of Rijindael: AES - the Advanced Encryption Standard. Springer (2001)
  8. Dubrova, E.: A Transformation from the Fibonacci to the Galois NLFSRs. IEEE Transactions on Information Theory聽55(11), 5263鈥?271 (2009) CrossRef
  9. Foulds, L.R.: Graph Theory Applications. Springer (1992)
  10. Goli膰, J.D.: Modes of Operation of Stream Ciphers. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol.聽2012, pp. 233鈥?47. Springer, Heidelberg (2001) CrossRef
  11. Golomb, S.: Shift Register Sequences. Aegean Park Press, Walnut Creek (1982)
  12. Russell, S.J., Norvis, P.: Artificial Intelligence: a Modern Approach. Prentice Hall, Inc. (1995)
  13. Wan, Z.X., Dai, Z.D., Liu, M.L., Feng, X.N.: Nonlinear Shift Registers. Science Press (1978) (in Chinese)
  14. Wan, Z.X.: Algebra and Codes. Science Press (1980) (in Chinese)
  15. Data Assurance & Communication Security Center, Chinese Science Academy, 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3, http://zucalg.forumotion.net/
  
• 作者单位：Lin Wang (18)
  Bing Shen (18)
  TongXu Qiao (19)
  
  18. Science and Technology on Communication Security Laboratory, Chengdu, 610041, Sichuan, P.R. China
  19. No.30 Institute of CETC, Chengdu, 610041, Sichuan, P.R. China
  
• ISSN：1611-3349

文摘

Finding a recurrence of a shift register gives its equivalent shift register in Fibonacci configuration and hence helps to decide whether different nonlinear shift registers are equivalent, i.e., whether they generate the same set of output sequences. We define a dependence graph of a shift register and it is a directed acyclic graph related to the shift register. We show that existence of a dependence graph with a special property of a nonlinear shift register ensures existence of a short recurrence of the sequence generated by the nonlinear shift register. We also present an algorithm to search dependence graphs of a nonlinear shift register.