OPPORTUNITIES TO MINIMIZE HARDWARE AND SOFTWARE COSTS FOR IMPLEMENTING BOOLEAN FUNCTIONS IN STREAM CIPHERS
DOI:
https://doi.org/10.47839/ijc.18.4.1614Keywords:
stream ciphers, pseudo-random sequence generators, NLFSR, nonlinear feedback shift register, Boolean functions, de Bruijn sequence, linear complexity, autocorrelation function, cryptographic analysis, nonlinear polynomials.Abstract
Currently, nonlinear Boolean functions are actively investigated worldwide. However, many questions remain unanswered. The theory of nonlinear Boolean functions that are suitable for use in cryptographically strong algorithms is significantly incomplete. Despite the existence of numerous publications on these themes, many issues related to the interconnection of design characteristics affecting the generator’s performance and its cryptographic characteristics still remain unsolved. The possibility of generating a special type of sequence, called de Bruijn sequence, at minimal hardware and software costs to implement nonlinear Boolean functions in stream encryption systems, is the main subject of this work. The paper presents the possible structure boundaries (algebraic degree of a Boolean function, the number of monomials in a function) of iterative de Bruijn sequence bitrate generators for various generated sequence characteristics, such as linear complexity and autocorrelation function. The profile of the linear complexity of the studied sequences is close to the expected value of the linear complexity, as well as for a truly random sequence.References
M. Schafheutle, A First Report on the Stream Cipher SNOW. [Online]. Available at: http://www.cryptonessie.org
C. Berbain, O. Billet, A. Canteaut, N. Courtois, B. Debraize, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin, and H. Sibert, Decim – A New Stream Cipher for Hardware applications, in ECRYPT Stream Cipher Project Report 2005/004. [Online]. Available at: http://www.ecrypt.eu.org
S. Kiyomoto, T. Tanaka, and K. Sakurai, “A word-oriented stream cipher using clock control,” Workshop Record of SASC 2007, pp.260–274, January 2007 [Online]. Available at: https://www.cosic.esat.kuleuven.be/ecrypt/stream/papersdir/2007/029.pdf
The eSTREAM Project – eSTREAM Phase 3. SOSEMANUK (Portfolio Profile 1). [Online]. Available at: http://www.ecrypt.eu.org
The eSTREAM Project – eSTREAM Phase 3. Grain (Portfolio Profile 2). [Online]. Available at: http://www.ecrypt.eu.org/stream/grainpf.html
The eSTREAM Project – eSTREAM Phase 3. MICKEY (Portfolio Profile 2). [Online]. Available at: http://www.ecrypt.eu.org/stream/mickeypf.html
The eSTREAM Project – eSTREAM Phase 3. Trivium (Portfolio Profile 2). [Online]. Available: http://www.ecrypt.eu.org/stream/triviumpf.html
P. Dabrowski, G. Łabuzek, T. Rachwalik, J. Szmidt, “Searching for nonlinear feedback shift registers with parallel computing,” 2013. [Online]. Available att: https://eprint.iacr.org/2013/542.pdf
H. Fredricksen, “A survey of full length nonlinear shift register cycle algorithms,” SIAM Review, vol. 24, no. 2, pp. 195-221, 1982.
C.J. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph.D. Thesis, Technical University of Delft, 1989.
C.J. Jansen, “The maximum order complexity of sequence ensembles,” Lecture Notes in Computer Science, Adv. Cryptology-Eupocrypt’1991, Berlin, Germany, 1991, vol. 547, pp. 153-159.
D. Linardatos, N. Kalouptsidis, “Synthesis of minimal cost nonlinear feedback shift registers,” Signal Process., vol. 82, no. 2, pp. 157–176, 2002.
P. Rizomiliotis, N. Kalouptsidis, “Results on the nonlinear span of binary sequences,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1555–5634, 2005.
K. Limniotis, N. Kolokotronis, N. Kalouptsidis, “On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences,” IEEE Transactions on Information Theory, vol. 53, no. 11, pp. 4293–4302, 2007.
E. Dubrova, “A scalable method for constructing Galois NLFSRs with period 2n-1 using cross-join pairs,” IEEE Transactions on Information Theory, vol. 59, issue 1, pp. 703-709, 2013.
J. Mykkeltveit, M.-K. Siu, P. Tong, “On the cyclic structure of some nonlinear shift register sequences,” Inform. and Control., vol. 43, pp. 202-215, 1979.
C. Carlet, “Boolean functions for cryptography and error correcting codes,” in: Crama Y., Hammer P. L. (Eds.), Boolean Methods and Models, Cambridge University Press. [Online]. Available at: http://www.rocq.inria.fr/secret/Claude.Carlet/chap-fcts-Bool.pdf
D. Knuth, The Art of Computer Programming, vol. II, Seminumerical Algorithms, USA, Commonwealth of Massachusetts: Addison-Wesley, 1969, 634 p.
M.С. Flye-Sainte, “Solution to question number 48,” l'Intermediaire des Mathematiciens, vol. 1, pp. 107-110, 1894.
N.G. de Bruijn, “A combitorial problem,” Nederl. Akad. Wetensch., vol. 49, pp. 758-764, 1946.
H. Fredricksen, “A survey of full length nonlinear shift register cycle algorithm,” SIAM Review, vol. 24, issue 2, pp. 195–221, 1982.
G.L. Mayhew, S.W. Golomb, “Characterizations of generators for modified de Bruijn sequences,” Advances in Applied Mathematics, vol. 13, issue 4, pp. 454-461, 1992. [Online]. Available at: https://www.sciencedirect.com/science/article/pii/019688589290021N
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, 474 p.
F.J. McWilliams, N.J. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1978, 762 p.
T. Kaida and J. Zheng, “On linear complexity of periodic sequences over extension fields from cyclic difference sets,” Proceedings of the 2015 Seventh International Workshop on Signal Design and its Applications in Communications (IWSDA), Bengaluru, 2015, pp. 15-18. DOI: 10.1109/IWSDA.2015.7458392
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. DOI: 10.1007/978-3-030-00253-4_6.
K. Tsuchiya, C. Ogawa, Y. Nogami and S. Uehara, “Linear complexity of generalized NTU sequences,” Proceedings of the 2017 Eighth International Workshop on Signal Design and its Applications in Communications (IWSDA), Sapporo, 2017, pp. 74-78. DOI: 10.1109/IWSDA.2017.8095739
A. Andrushkevych, Y. Gorbenko, O. Kuznetsov, R. Oliynykov, M. A. Rodinko, “A prospective lightweight block cipher 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. 95-112. DOI: 10.1007/978-3-030-00253-4_5.
J. Szmidt and P. Dąbrowski, “The construction of nonlinear feedback shift registers of small orders,” Proceedings of the 2015 International Conference on Military Communications and Information Systems (ICMCIS), Cracow, 2015, pp. 1-4.
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. Moriyama and A. Tsuneda, “A study on construction of low-density parity-check codes using nonlinear feedback shift registers,” Proceedings of the 2016 International Conference on Information and Communication Technology Convergence (ICTC), Jeju, 2016, pp. 697-699.
A. Kuznetsov, Y. Gorbenko, A. Andrushkevych and I. Belozersev, “Analysis of block symmetric algorithms from international standard of lightweight cryptography ISO/IEC 29192-2,” Proceedings of the 2017 4th International Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 203-206.
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, 2018.
A. M. Arshad, H. Ino, C. Ogawa and Y. Nogami, “Linear complexity of signed binary sequence over odd characteristic field,” Proceedings of the 2016 19th International Conference on Computer and Information Technology (ICCIT), Dhaka, 2016, pp. 266-269. DOI: 10.1109/ICCITECHN.2016.7860207
G.L. Mayhew, S.W. Golomb, “Linear spans of modified de Bruijn sequences,” IEEE Trans. Inform. Theory., vol. 36, no. 5, pp. 1166–1167, 1990.
P. Rizomiliotis, “Constructing periodic binary sequences with maximum nonlinear span,” IEEE Transactions on Information Theory, vol. 52, no. 9, pp. 4257-4261, Sept. 2006.
V.I. Dolgov, I.V.Lisitska, K.Ye. Lisitskyi, “The new concept of block symmetric ciphers design,” Telecommunications and Radio Engineering, vol. 76, issue 2, pp. 157-184, 2017.
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.
I. Gorbenko, O. Nariezhnii and I. Kudryashov, “Construction method and features of one class of cryptographic discrete signals,” Proceedings of the 2017 4th International Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 156-160.
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.
V. A. Krasnobayev, “Method for realization of transformations in public-key cryptography,” Telecommunications and Radio Engineering, vol. 66, issue 17, pp. 1559-1572, 2007. DOI: 10.1615/TelecomRadEng.v66.i17.60
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. 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
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.
