COMBINING AND FILTERING FUNCTIONS IN THE FRAMEWORK OF NONLINEAR-FEEDBACK SHIFT REGISTER
DOI:
https://doi.org/10.47839/ijc.19.2.1768Keywords:
stream ciphers, generators of the pseudorandom sequence, NLFSR, nonlinear feedback shift register, filtering function, combining function, cryptanalysis, nonlinear polynomials.Abstract
Strong cryptography of stream ciphers is determined according to the ability of the generated pseudorandom sequence to resist analytical attacks. One of the main components of the pseudorandom stream cipher sequence generating algorithm is Boolean functions for combining and filtering. The paper considers the possibility of applying nonlinear-feedback shift registers that generate a maximum length sequence as a combining or filtering function. The main indicators of cryptographic strength of such functions as: balance, the prohibitions presence, correlation immunity and nonlinearity are examined in this work. The study analyzes and demonstrates correlation immunity and nonlinearity experimental values for all nonlinear feedback shift registers that generate a maximum length sequence, for register sizes up to 6 cells inclusively, and register sizes up to 9 cells inclusively with algebraic degree of the polynomial under 2. The possibility of optimizing the process of selecting Boolean functions according to the criteria of maximum correlation immunity and nonlinearity with various algebraic degrees and minimization of the number of monomials in the polynomial is studied.References
D. Tang, W.G. Zhang, C. Carlet, X.H. Tang, “Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties,” Des. Codes Crypt., vol. 67, issue 1, pp. 77-91, 2013.
С. Carlet, “Boolean functions for cryptography and error correcting codes,” Ch.8 of the Monograph “Boolean Methods and Models in Mathematics, Computer Science, and Engineering”, Cambridge Univ. Press, 2010. pp. 257–397.
A. A. Kuznetsov, A. V. Potii, N. A. Poluyanenko, I. V. Stelnik, “Nonlinear functions of complication for symmetric stream ciphers,” Telecommunications and Radio Engineering, vol. 78, issue 9, pp. 743-458, 2019. DOI: 10.1615/TelecomRadEng.v78.i9.10
A. A. Kuznetsov, A. V. Potii, N. A. Poluyanenko, S. G. Vdovenko, “Combining and filtering functions based on the nonlinear feedback shift registers,” Telecommunications and Radio Engineering, vol. 78, issue 10, pp. 853-868. 2019. DOI: 10.1615/TelecomRadEng.v78.i10.20
A. Kuznetsov, O. Potii, N. Poluyanenko, S. Ihnatenko, I. Stelnyk, D. Mialkovsky, “Opportunities to minimize hardware and software costs for implementing Boolean functions in stream ciphers,” International Journal of Computing, vol. 18, issue 4, pp. 443-452, 2019. http://computingonline.net/computing/article/view/1614.
J. Sawada, A. Williams, D. Wong, “A surprisingly simple de Bruijn sequence construction,” Discrete Math., vol. 339, pp. 127–131, 2016.
D. Knuth, The Art of Computer Programming. Vol. II. Seminumerical Algorithms. USA, Commonwealth of Massachusetts: Addison-Wesley, 1969, 634 p.
S. Mesnager, Bent Functions: Fundamentals and Results, New York, NY, USA, Springer-Verlag, 2015, 544 p.
S.V. Smyshlyaev, “On the cryptographic weaknesses of some classes of transformations of binary sequences,” Applied Discrete Mathematics, vol. 1, pp. 5–15, 2010. (in Russian)
C. Carlet, “Open problems on binary bent functions,” Lecture Notes in Computer Science, Springer, pp. 203-241, 2014.
N. Tokareva, Bent Functions, Results and Applications to Cryptography, Academic Press, San Diego, CA, 2015, 220 p.
S. Mesnager, “On semi-bent functions and related plateaued functions over the Galois field F2n,” Proceedings “Open Problems in Mathematics and Computational Science”, Lecture Notes in Computer Science, Springer, pp. 243–273, 2014.
Yu.V. Tarannikov, “On the correlation-immune and stable Boolean functions,” Mathematical Issues of Cybernetics, Fizmatlit, vol. 11, pp. 91–148, 2002. (in Russian)
Y. Izbenko, V. Kovtun and A. Kuznetsov, "The design of boolean functions by modified hill climbing method,” Proceedings of the 2009 Sixth International Conference on Information Technology: New Generations, Las Vegas, NV, 2009, pp. 356-361.
J. Seberry, X.-M. Zhang and Y.Zheng. “Nonlinearity and propagation characteristics of balanced Boolean functions,” Information and Computation, vol. 119, no. 1, pp. 1-13, 1995.
Y. Zheng and X. M. Zhang, “Improved upper bound on the nonlinearity of high order correlation immune functions,” Selected Areas in Cryptography-SAC 2000, Lecture Notes in Computer Science, Springer Verlag, vol. 2012, pp. 264–274, 2000.
S. Ronjom, C. Cid, “Nonlinear equivalence of stream ciphers,” Proceedings of the 17th International Workshop on Fast Software Encryption, FSE’2010, Seoul, Korea, Lecture Notes in Computer Science, Vol. 6147, Springer-Verlag, 2010, pp. 40-54.
M. Soriano, “Stream ciphers based on NLFSR,” Proceedings of the SBT/IEEE International Telecommunications Symposium ITS'98, Sao Paulo, Brazil, 1998, vol. 2, pp. 528-533.
J. Szmidt, “Nonlinear feedback shift registers and Zech’s logarithms,” Proceedings of the 2019 International Conference on Military Communications and Information Systems (ICMCIS), Budva, Montenegro, 2019, pp. 1-4. DOI: 10.1109/ICMCIS.2019.8842713
N. Krishna, V. Murugappan, R. Harish, M. Midhun and E. Prabhu, “Design of a novel reversible NLFSR,” Proceedings of the 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, 2017, pp. 2279-2283.
O. Kuznetsov, O. Potii, A. Perepelitsyn, D. Ivanenko, N. Poluyanenko, “Lightweight stream ciphers for green IT engineering,” in: Kharchenko V., Kondratenko Y., Kacprzyk J. (eds) Green IT Engineering: Social, Business and Industrial Applications. Studies in Systems, Decision and Control, vol. 171, Springer, Cham, 2019, pp. 113-137.
S. B. Sadkhan and D. M. Reza, “Investigation of the best structure for the nonlinear combining function,” Proceedings of the 2017 Annual Conference on New Trends in Information & Communications Technology Applications (NTICT), Baghdad, 2017, pp. 180-185.
N. Maeda and A. Tsuneda, “Markov binary sequences generated by post-processing based on feedback shift registers,” Proceedings of the 2019 International Conference on Information and Communication Technology Convergence (ICTC), Jeju Island, Korea, 2019, pp. 147-149. DOI: 10.1109/ICTC46691.2019.8939599
L. Zhiqiang, “The transformation from the Galois NLFSR to the Fibonacci configuration,” Proceedings of the 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies, Xi'an, 2013, pp. 335-339.
B. M. Gammel, R. Gottfert and O. Kniffler, “An NLFSR-based stream cipher,” Proceedings of the 2006 IEEE International Symposium on Circuits and Systems, Island of Kos, 2006, pp. 4 pp.-2920.
A. A. Zadeh and H. M. Heys, “Simple power analysis applied to nonlinear feedback shift registers,” IET Information Security, vol. 8, no. 3, pp. 188-198, May 2014.
Y. Watanabe, Y. Todo and M. Morii, “New conditional differential cryptanalysis for NLFSR-based stream ciphers and application to grain v1,” Proceedings of the 2016 11th Asia Joint Conference on Information Security (AsiaJCIS), Fukuoka, 2016, pp. 115-123.
X. Guo and X. Na, “A research of the Port-Hopping telecommunication techniques based on non-linear feedback shift register (NLFSR),” Proceedings of the 2011 IEEE International Conference on Automation and Logistics (ICAL), Chongqing, 2011, pp. 336-338.
F. Gao, Y. Yang and G. Tan, “Some results on word-oriented nonlinear feedback shift registers,” Proceedings of the 2011 International Conference on Electronics and Optoelectronics, Dalian, 2011, pp. V4-357-V4-359.
T. Rachwalik, J. Szmidt, R. Wicik and J. Zabłocki, “Generation of nonlinear feedback shift registers with special-purpose hardware,” Proceedings of the 2012 Military Communications and Information Systems Conference (MCC), Gdansk, 2012, pp. 1-4.
S. Bondarenko, L. Bodenchuk, O. Krynytska and I. Gayvoronska, “Modelling instruments in risk management,” International Journal of Civil Engineering and Technology, vol. 10, issue 1, pp. 1561-1568, 2019.
K. Fukuda and A. Tsuneda, “Key-sensitivity improvement of block cipher systems based on nonlinear feedback shift registers,” Proceedings of the 2012 IEEE Asia Pacific Conference on Circuits and Systems, Kaohsiung, 2012, pp. 100-103. DOI: 10.1109/APCCAS.2012. 6418981
A. Falahati, H. Azizi and R. M. Edwards, “RFID light weight server-less search protocol based on NLFSRs,” Proceedings of the 2016 8th International Symposium on Telecommunications (IST), Tehran, 2016, pp. 741-745.
A. Tsuneda, D. Yoshioka and T. Hadate, “Design of spreading sequences with negative auto-correlations realizable by nonlinear feedback shift registers,” Proceedings of the Eighth IEEE International Symposium on Spread Spectrum Techniques and Applications - Programme and Book of Abstract, Sydney, NSW, Australia, 2004, pp. 330-334. DOI: 10.1109/ISSSTA.2004.1371716
J. Zhong, J. Lu, T. Huang, J. Cao, “Synchronization of mas-tercslave Boolean networks with impulsive effects: Necessary and sufficient criteria,” Neurocomputing, vol. 143, no. 143, pp. 269-274, 2014.
J. Zhong and D. Lin, “On minimum period of nonlinear feedback shift registers in grain-like structure,” IEEE Transactions on Information Theory, vol. 64, no. 9, pp. 6429-6442, Sept. 2018. DOI: 10.1109/TIT.2018.2849392.
K. Runovski, & H. Schmeisser, “On the convergence of fourier means and interpolation means,” Journal of Computational Analysis and Applications, vol. 6, issue 3, pp. 211-227, 2004.
J. Zhang, T. Tian, W. Qi and Q. Zheng, “A new method for finding affine sub-families of NFSR sequences,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1249-1257, Feb. 2019. DOI: 10.1109/TIT.2018.2858769
X. Han, Z. Chen, Z. Liu, Q. Zhang, “Calculation of siphons and minimal siphons in Petri nets based on semi-tensor product of matrices,” IEEE Transactions on Systems Man & Cybernetics Systems, vol. 47, issue 3, pp. 531-536, 2015.
R. Chornei, V. M. Hans Daduna, & P. Knopov, “Controlled Markov fields with finite state space on graphs,” Stochastic Models, vol. 21, issue 4, 847-874, 2005. DOI: 10.1080/15326340500294520.
D. W. Zhao, H. P. Peng, L. X. Li, S. L. Hui, Y. X. Yang, “Novel way to research nonlinear feedback shift register,” Science China Information Sciences, vol. 57, no. 9, pp. 1-14, 2014.
B. P. Tkach, & L. B. Urmancheva, “Numerical-analytic method for finding solutions of systems with distributed parameters and integral condition,” Nonlinear Oscillations, vol. 12, no. 1, pp. 113-122, 2009. DOI: 10.1007/s11072-009-0064-6.
Y. Yang, X. Zeng and Y. Xu, “Periods on the cascade connection of an LFSR and an NFSR,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 301-308, 2019. DOI: 10.1049/cje.2019.01.018.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
