HEURISTIC METHODS FOR THE DESIGN OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS
DOI:
https://doi.org/10.47839/ijc.18.3.1519Keywords:
heuristic methods, cryptographic Boolean functions, symmetric cryptography, nonlinear substitute blocks.Abstract
In this article, heuristic methods of hill climbing for cryptographic Boolean functions satisfying the required properties of balance, nonlinearity, autocorrelation, and other stability indicators are considered. A technique for estimating the computational efficiency of gradient search methods, based on the construction of selective (empirical) distribution functions characterizing the probability of the formation of Boolean functions with indices of stability not lower than required, is proposed. As an indicator of computational efficiency, an average number of attempts is proposed to be performed using a heuristic method to form a cryptographic Boolean function with the required properties. Comparative assessments of the effectiveness of the heuristic methods are considered. The results of investigations of the cryptographic properties of the formed Boolean functions in comparison with the best known assessments are given. On the basis of the conducted research, it can be concluded that the functions constructed in accordance with the developed method have high persistence indexes and exceed the known functions by these indicators.References
Information Technology. Security Techniques. Encryption Algorithms. Part 3: Block ciphers. ISO/IEC 18033-3: 2010, 2010.
Advanced Encryption Standard, Federal Information Processing Standards Publications FIPS-197, 2001.
A New Encryption Standard of Ukraine: The Kalyna Block Cipher. Cryptology ePrint Archive: Report 2015/650. https://eprint.iacr.org/2015/650.
Information Technology. Cryptography Protection of Information. Block Ciphers. National Standard of Russian Federation, GOST R 34.12-2015, 2015 (in Russian).
О. О. Kuznetsov, Yu. І. Gorbenko, І. М. Bilozertsev, А. V. Аndrushkevych, О. P. Narizhnyi, “Algebraic immunity of non-linear blocks of symmetric ciphers,” Telecommunications and Radio Engineering, vol. 77, issue 4, pp. 309-325, 2018. DOI: 10.1615/TelecomRadEng.v77.i4.30
B. N. Tran, T. D. Nguyen and T. D. Tran, “A new S-box structure to increase complexity of algebraic expression for block cipher cryptosystems,” Proceedings of the 2009 International Conference on Computer Technology and Development, Kota Kinabalu, 2009, pp. 212-216.
A. Kuznetsov, R. Serhiienko, D. Prokopovych-Tkachenko and Y. Tarasenko, “Evaluation of algebraic immunity of modern block ciphers,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 288-293. DOI: 10.1109/DESSERT.2018.8409146
M. McLoone and J. V. McCanny, “High-performance FPGA implementation of DES using a novel method for implementing the key schedule,” IEE Proceedings-Circuits, Devices and Systems, vol. 150, no. 5, pp. 373, Oct. 2003.
A. Kuznetsov, I. Kolovanova and T. Kuznetsova, “Periodic characteristics of output feedback encryption mode,” Proceedings of the 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 193-198. DOI: 10.1109/INFOCOMMST.2017.8246378
S. Sulaiman, Z. Muda and J. Juremi, “The new approach of Rijndael key schedule,” Proceedings of the 2012 International Conference on Cyber Security, Cyber Warfare and Digital Forensic (CyberSec), Kuala Lumpur, 2012, pp. 23-27.
L. May, M. Henricksen, W. Millan, G. Carter, and E. Dawson, “Strengthening the key schedule of the AES,” in Information Security and Privacy, Lecture Notes in Computer Science, vol. 2384, Springer Berlin / Heidelberg, pp. 226-240, 2002.
F. H. Nejad, S. Sabah and A. J. Jam, “Analysis of avalanche effect on advance encryption standard by using dynamic S-Box depends on rounds keys,” Proceedings of the 2014 International Conference on Computational Science and Technology (ICCST), Kota Kinabalu, 2014, pp. 1-5.
H. Liu and C. Jin, “Lower bounds of differential and linear active S-boxes for 3D-like structure,” The Computer Journal, vol. 58, no. 4, pp. 904-921, April 2015.
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 Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 203-206. DOI: 10.1109/INFOCOMMST.2017.8246380.
I. Gorbenko, A. Kuznetsov, M. Lutsenko and D. Ivanenko, “The research of modern stream ciphers,” Proceedings of the 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 207-210. DOI: 10.1109/INFOCOMMST.2017.8246381
Information Technologies. Cryptographic Data Security. Symmetric Stream Transformation Algorithm. National Standard of Ukraine DSTU 8845:2019, 2019 (in Ukrainian).
C. A. Wood, S. P. Radziszowski and M. Lukowiak, “Constructing large S-boxes with area minimized implementations,” Proceedings of the 2015 IEEE Military Communications Conference MILCOM’2015, Tampa, FL, 2015, pp. 49-54.
V. Gopi and E. Logashanmugam, “Design and analysis of nonlinear AES S-box and mix-column transformation with the pipelined architecture,” Proceedings of the 2013 International Conference on Current Trends in Engineering and Technology (ICCTET), Coimbatore, 2013, pp. 235-238.
H. Wang, H. Zheng, B. Hu and H. Tang, “Improved lightweight encryption algorithm based on optimized S-box,” Proceedings of the 2013 International Conference on Computational and Information Sciences, Shiyang, 2013, pp. 734-737.
I. Das, S. Nath, S. Roy and S. Mondal, “Random S-box generation in AES by changing irreducible polynomial,” Proceedings of the 2012 International Conference on Communications, Devices and Intelligent Systems (CODIS), Kolkata, 2012, pp. 556-559.
Y. Chen, W. Tian and Y. Zhang, “Construction for balanced boolean function with maximum algebraic immunity,” Proceedings of the 2014 7th International Conference on Advanced Software Engineering and its Applications, Haikou, 2014, pp. 32-34.
C. E, S. Liang and T. Zhang, “Construction method of boolean functions based on genetic algorithm,” Proceedings of the 2011 7th International Conference on Wireless Communications, Networking and Mobile Computing, Wuhan, 2011, pp. 1-4.
R. Asthana, N. Verma and R. Ratan, “Generation of Boolean functions using Genetic Algorithm for cryptographic applications,” Proceedings of the 2014 IEEE International Advance Computing Conference (IACC), Gurgaon, 2014, pp. 1361-1366.
Bharti and D. K. Sharma, “Searching Boolean function using simulated annealing and hill climbing optimization techniques,” Proceedings of the 2016 International Conference on Advanced Communication Control and Computing Technologies (ICACCCT), Ramanathapuram, 2016, pp. 62-64.
W. Millan, J. Fuller and E. Dawson, “New concepts in evolutionary search for Boolean functions in cryptology,” Proceedings of the 2003 Congress on Evolutionary Computation CEC’03, 2003, vol. 3, pp. 2157-2164.
S. Picek, C. Carlet, S. Guilley, J. F. Miller and D. Jakobovic, “Evolutionary algorithms for Boolean functions in diverse domains of cryptography,” Proceedings of the Evolutionary Computation, vol. 24, no. 4, pp. 667-694, Dec. 2016.
W. Millan, A. Clark, E. Dawson, “Smart hill climbing finds better Boolean functions,” Proceedings of the Workshop on Selected Areas on Cryptography SAC’97, Springer-Verlag, 1997, pp. 50-63.
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. DOI: 10.1109/ITNG.2009.102
A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22, 2001.
E. Pasalic and T. Johansson, “Further results on the relation between nonlinearity and resiliency of Boolean functions,” Proceedings of the IMA Conference on Cryptography and Coding (Lecture Notes in Computer Science). New York: Springer-Verlag, 1999, vol. 1746, pp. 35–45.
J. A. Clark, J. L. Jacob, S. Stepney, S. Maitra, W. Millan, “Evolving Boolean functions satisfying multiple criteria,” Proceedings of the INDOCRYPT’02. Lecture Notes in Computer Science, vol. 2551, Springer, 2002, pp. 246-259.
W. Millan, A. Clark, E. Dawson, “An effective genetic algorithm for finding highly non-linear Boolean functions,” Proceedings of the First International Conference on Information and Communications Security, Lecture Notes in Computer Science, vol. 1334. Springer-Verlag, Berlin Heidelberg New York, 1997, pp. 149-158.
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, vol. 2012, pp. 264–274. Springer Verlag, 2000.
X-M. Zhang and Y. Zheng, “GAC-the criterion for global avalanche characteristics of cryptographic functions,” Journal of Universal Computer Science, vol. 1, issue 5, pp. 316–333, 1995.
S. Maitra, “Highly nonlinear balanced Boolean functions with very good autocorrelation property,” Proceedings of the Workshop on Coding and Cryptography-WCC’2001, Paris, January 8–12, 2001, Electronic Notes in Discrete Mathematics, vol. 6, Elsevier Science, 2001.
S. Maitra, “Autocorrelation properties of correlation immune Boolean functions,” Proceedings of the INDOCRYPT 2001, Lecture Notes in Computer Science, vol. 2247, pp. 242–253, Springer Verlag, December 2001.
S. Maitra and E. Pasalic, “Further constructions of resilient Boolean functions with very high nonlinearity,” IEEE Transactions on Information Theory, vol. 48, issue 7, pp. 1825–1834, July 2002.
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.
J. Seberry, X.M. Zhang, Y. Zheng, “On constractions and nonlinearity of correlation immune functions,” Proceedings of the Advances in Cryptology – EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765, Springer-Verlag, 1994, pp. 181-199.
J. Seberry and X. Zhang. “Hadamar matrices, Bent functions and cryptography,” in J.H. Dinitz and D.R. Stinson, editors, Contemporary Design Theory: A Collection of Surveys, chapter 11, pp. 431-559, John Wiley and Sons, Inc, 1995.
A. S. Omar and O. Basir, “SIMON 32/64 and 64/128 block cipher: Study of cross correlation and linear span attack immunity,” Proceedings of the 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Montreal, QC, 2017, pp. 1-6.
C. Carlet and X. Chen, “Constructing low-weight $d$ th-order correlation-immune Boolean functions through the Fourier-Hadamard transform,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2969-2978, April 2018.
Z. Wang and G. Gong, “Discrete Fourier transform of Boolean functions over the complex field and its applications,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 3000-3009, April 2018.
A. Belazi, R. Rhouma and S. Belghith, “A novel approach to construct S-box based on Rossler system,” Proceedings of the 2015 International Wireless Communications and Mobile Computing Conference (IWCMC), Dubrovnik, 2015, pp. 611-615.
N. Ferguson, et al., “Improved cryptanalysis of Rijndael,” in Fast Software Encryption, Lecture Notes in Computer Science, vol. 1978, Springer Berlin / Heidelberg, 2001, pp. 213-230.
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.
K. Verma and D. K. Sharma, “Calculation of non-linearity and algebraic degree of constructed Boolean function,” Proceedings of the 2017 2nd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT), Bangalore, 2017, pp. 501-505.
B. P. Tkach, & L. B. Urmancheva, “Numerical-analytic method for finding solutions of systems with distributed parameters and integral condition,” Nonlinear Oscillations, vol. 12, issue 1, pp. 113-122, 2009. doi:10.1007/s11072-009-0064-6
R. Chornei, V. M. Hans Daduna, & P. Knopov, “Controlled Markov fields with finite state space on graphs,” Stochastic Models, vol. 21, issue 4, pp. 847-874, 2005. doi: 10.1080/15326340500294520
G. Manjula and H.S. Mohan, “Constructing key dependent dynamic S-Box for AES block cipher system,” Proceedings of the 2016 2nd International Conference on Applied and Theoretical Computing and Communication Technology (iCATccT), Bangalore, 2016, pp. 613-617.
O. Oksiiuk and V. Chaikovska, “Authentication process threats in the cloud technologies,” Proceedings of the 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 113-118. doi:10.1109/INFOCOMMST.2018.8632126
R. Goyal, “Annihilator immunity of a bent function,” Proceedings of the 2017 International Conference on Intelligent Communication and Computational Techniques (ICCT), Jaipur, 2017, pp. 23-25.
C. D. Akshima, M. Ghosh, A. Goel, S.K. Sanadhya, “Single key recovery attacks on 9-round Kalyna-128/256 and Kalyna-256/512,” in Kwon S., Yun A. (eds) Information Security and Cryptology – ICISC’2015, Lecture Notes in Computer Science, Springer, Cham, vol. 9558, 2016.
A New Standard of Ukraine: The Kupyna Hash Function. Cryptology ePrint Archive Report 2015/885. https://eprint.iacr.org/2015/885.
J. Zou, L. Dong, “Cryptanalysis of the round-reduced Kupyna hash function,” Cryptology ePrint Archive Report 2015/959, https://eprint.iacr.org/2015/959.pdf.
O. Duman, Application of Fault Analysis to Some Cryptographic Standards, Master Thesis in the Concordia Institute for Information Systems Engineering, https://spectrum.library.concordia.ca/981334/1/Duman_MASc_f2016.pdf
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.
