Heuristic methods for gradient search of cryptographic Boolean functions

Authors

  • А.А. Kuznetsov
  • I.V. Moskovchenko
  • D.I. Prokopovych-Tkachenko
  • T.Y. Kuznetsova

DOI:

https://doi.org/10.30837/rt.2018.4.195.15

Keywords:

heuristic methods, cryptographic Boolean functions, symmetric cryptography, nonlinear substitute blocks

Abstract

Heuristic methods of gradient search of cryptographic Boolean functions that satisfy the required properties of balance, nonlinearity, autocorrelation, and other stability indicators are considered. The proposed method of gradient descent is investigated, in particular, estimates of nonlinearity and correlation immunity of the synthesized Boolean functions are given. A method for evaluating the computational efficiency of gradient search methods is proposed, based on the construction of sample (empirical) distribution functions, which characterize the probability of the formation of Boolean functions with persistence indicators not lower than those required. As an indicator of computational efficiency, we propose the average number of attempts that need to be performed using the heuristic method to form a cryptographic Boolean function with the required properties. It is shown that the proposed gradient descent method allows the formation of cryptographic functions with the required durability indicators in fewer steps. The results of investigations of the cryptographic properties of the formed Boolean functions in comparison with the best known assessments are given.

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.

Information technologies. Cryptographic Data Security. Symmetric block transformation algorithm. National Standard of Ukraine DSTU 7624:2014, 2015 (in Ukr.).

Information technology. Cryptography protection of information. Block ciphers. National Standard of Russian Federation GOST R 34.12-2015, 2015 (in Rus.).

Information technology and security. Information security. Cryptography encryption and integrity control algorithms. State Standard of the Republic of Belarus STB 34.101.31-2011, 2011.

О.О. Kuznetsov, Yu.І. Gorbenko, І.М. Bilozertsev, А.V. Аndrushkevych, О.P. Narizhnyi. Algebraic Immunity of Non-linear Blocks of Symmetric Ciphers // Telecommunications and Radio Engineering. – 2018. – Vol. 77, Issue 4. – Р. 309-325.

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 // International Conference on Computer Technology and Development, Kota Kinabalu, 2009. – Р. 212-216.

A. Kuznetsov, R. Serhiienko, D. Prokopovych-Tkachenko and Y. Tarasenko. Evaluation of Algebraic Immunity of modern block ciphers // IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018. – Р. 288-293.

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, 6 Oct. 2003.

A. Kuznetsov, I. Kolovanova and T. Kuznetsova. Periodic characteristics of output feedback encryption mode // 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017. – Р. 193-198.

S. Sulaiman, Z. Muda and J. Juremi. The new approach of Rijndael key schedule // Proceedings Title: 2012 International Conference on Cyber Security, Cyber Warfare and Digital Forensic (CyberSec), Kuala Lumpur, 2012, pp. 23-27.

O. Kuznetsov, Y. Gorbenko and I. Kolovanova. Combinatorial properties of block symmetric ciphers key schedule // Third International Scientific-Practical Conference Problems of Infocommunications Science and Technology (PIC S&T), Kharkiv, 2016, pp. 55-58.

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 // 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 // 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 203-206.

I. Gorbenko, A. Kuznetsov, M. Lutsenko and D. Ivanenko. The research of modern stream ciphers // 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 207-210.

A. Kuznetsov, V. Frolenko, E. Eremin and O. Zavgorodnia. Research of cross-platform stream symmetric ciphers implementation // IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 300-305.

I. Gorbenko, O. Kuznetsov, Y. Gorbenko, A. Alekseychuk and V. Tymchenko, "Strumok keystream generator," 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 294-299.

V. Gopi and E. Logashanmugam. Design and analysis of nonlinear AES S-box and mix-column transformation with the pipelined architecture // 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 // 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 // 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 // 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 // 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 // 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 // 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 // Evolutionary Computation, 2003. CEC '03. The 2003 Congress on, 2003, pp. 2157-2164 Vol.3.

S. Picek, C. Carlet, S. Guilley, J. F. Miller and D. Jakobovic. Evolutionary Algorithms for Boolean Functions in Diverse Domains of Cryptography // 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, pp. 50-63, 1997.

Y. Izbenko, V. Kovtun and A. Kuznetsov. The Design of Boolean Functions by Modified Hill Climbing Method // Sixth International Conference on Information Technology: New Generations, Las Vegas, NV, 2009, pp. 356-361.

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 // Proc. IMA Conf. Cryptography and Coding (Lecture Notes in Computer Science). New York: Springer-Verlag, 1999, vol. 1746, pp. 35–45.

Clark J., Jacob S., Stepney S., Maitra, Millan W. Evolving Boolean Functions Satisfying Multiple Criteria // Proceedings of INDOCRYPT’02. LNCS Vol. 2551, Springer (2002) 246-259.

Millan W., Clark A., Dawson E. An Effective Genetic Algorithm for Finding Highly Non-linear Boolean Functions // Proceedings of the First International Conference on Information and Communications Security. LNCS Vol. 1334. Springer-Verlag, Berlin Heidelberg New York (1997) 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, Volume 2012, pages 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, 1(5):316–333, 1995.

S. Maitra. Highly nonlinear balanced Boolean functions with very good autocorrelation property // Workshop on Coding and Cryptography-WCC 2001, Paris, January 8–12, 2001. Electronic Notes in Discrete Mathematics, Volume 6, Elsevier Science, 2001.

S. Maitra. Autocorrelation properties of correlation immune Boolean functions // INDOCRYPT 2001, Lecture Notes in Computer Science Volume 2247, pages 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, 48(7): 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 // Advances in Cryptology – EUROCRYPT’93, vol.765, Lecture Notes in Computer Science, Springer-Verlag, pp.181-199,1994.

J. Seberry and X. Zhang. Hadamar Matrices, Bent Functions and Cryptography // J.H.Dinitz and D.R. Stinson, editors, Contemporary Design Theory: A Collection of Surveys,chapter 11, pages 431-559, John Wiley and Sons, Inc, 1995.

Downloads

Published

2018-12-28

How to Cite

Kuznetsov А., Moskovchenko, I., Prokopovych-Tkachenko, D., & Kuznetsova, T. (2018). Heuristic methods for gradient search of cryptographic Boolean functions. Radiotekhnika, 4(195), 150–164. https://doi.org/10.30837/rt.2018.4.195.15

Issue

No. 195 (2018): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. 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.

2. 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.

3. 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 (See The Effect of Open Access).