Bounded Search of Cryptographically Strong Boolean Functions
Abstract
In this paper we consider methods for obtaining Boolean functions with desirable cryptographic properties based on search algorithms. We investigate the possibility of optimizing such algorithms, primarily due to a significant reduction in the search space. Here we use the general idea of partition of the set of Boolean functions into equivalence classes in accordance to some transformation group and the idea of exhaustive search among these classes as vertices of a specific graph called class graph. The P-equivalence proposed in this paper if considered on the set of balanced Boolean functions ensures the preservation of almost all cryptographically significant properties of functions within one equivalence class.
References
1. Carlet C. Boolean functions for cryptography and error correcting codes // in: Boolean models and methods in mathematics, computer science and engineering. Y. Crama and P. L. Hammer (eds.). Cambridge University Press, 2010. P. 257–397.
2. Pieprzyk J. M¨ obius transforms, coincident Boolean functions and non-coincidence property of Boolean functions // International Journal of Computer Mathematics. 2011. № 7. P. 1398–1416.
3. Агафонова И.В., Дмитриева О.М. Методы построения полиномов Жегалкина для булевых функций // Материалы III Международной научно-технической и научно-методической конференции «Актуальные проблемы инфотелекоммуникаций в науке и образовании», 25–26 февраля 2014 г.). СПб.: Санкт-Петерб. гос. университет им. проф. М.А.Бонч-Бруевича, 2014. С. 525–530.
4. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.
5. Таранников Ю.В. О корреляционно-иммунных и устойчивых булевых функциях // Математические вопросы кибернетики. М.: Физматлит, 2002. Вып. 11. С. 91–148.
6. Агафонова И.В. Криптографические свойства нелинейных булевых функций // В сб.: Избранные главы дискретного гармонического анализа и геометрического моделирования. Часть I. Издание 2-е. Под ред. проф. В.Н. Малозёмова. СПб.: ВВМ, 2014. C. 428–451.
7. Городилова А.А. От криптоанализа шифра к криптографическому свойству булевой функции //Прикладная дискретная математика. 2016. № 3. С. 16–44.
8. Cusick T.W., and Stanica P. Cryptographic Boolean functions and applications. Amsterdam, Boston, Heidelberg, London, New York, Oxford, Paris, San Diego, San Francisco, Singapore, Sidney, Tokio: Academic Press, 2009.
9. Braeken A., Borissov Y., Nikova S., and Preneel B. Classification on Boolean functions of 6 variables or less with respect to some cryptographic properties // In Proc. 32nd Int. Colloq. Automata, Lang. Program. 2005. P. 324–334.
10. Фомичев В.М. Дискретная математика и криптология. Курс лекций / Под общ. ред. д-ра физ.-мат. н. Н.Д. Подуфалова. М.: ДИАЛОГ-МИФИ, 2003.
11. Токарева Н.Н. Симметричная криптография. Краткий курс: учебное пособие. Новосибирск.: Новосиб. гос. ун-т., 2012.
12. Черёмушкин А.В. Методы аффинной и линейной классификации двоичных функций // В сб.: Российская Академия наук. Академия криптографии Российской Федерации. Труды по дискретной математике. М.: Физматлит, 2001. Т. 4. С. 273–314.
13. Lechner R.J. A transform approach to logic design // IEEE Trans. on Computers. Jul. 1970. Vol. C-19. № 7. P. 627–640.
14. Millan W. New cryptographic applications of Boolean function equivalence classes // in ACISP. 2005. LNCS 3574. Brisbane. Australia. 2005. P. 572–583.
15. Zhang Y., Yang G., Hung W.N.N., and Zhang J. Computing Affine Equivalence Classes of Boolean functions by group isomorphism // IEEE Trans. on Computers. Dec. 2016. Vol. 65. № 7. P. 3606–3616.
16. Meng Q., Zhang G., Yang M., and Wang Z. Analysis of affinely equivalent Boolean functions // Sci China Ser F-Inf Sci. June 2007. Vol. 50. № 3. P. 299–306.
17. Millan W., Fuller J., and E. Dawson E. New concepts in evolutionary search for Boolean functions in cryptology // In Proc. of CEC 2003. IEEE. 2003. P. 2157–2164.
18. Fuller J. Analysis of affine equivalent Boolean functions for cryptography. PhD thesis. Queensland University of Technology. Brisbane. Australia. 2003.
19. Burnett L., Millan W., Dawson E., and Clark A. Simpler methods for generating better Boolean functions with good cryptographic properties // Australasian Journal of Combinatorics. 2004. Vol. 29. P. 231–247.
20. Picek S., Jakobovic D., Miller J.F., Marchiori E., and Batina L. Evolutionary methods for the construction of cryptographic Boolean functions // In Proc. EuroGP 2015. LNCS 9025. P. Machado, MI. Heywood, J. McDermott, M. Castelli, P. Garcia-Sanchez, P. Burelli, S. Risi, K. Sim (eds.) Switzerland: Springer, 2015. P. 192–204.
21. Izbenko Y., Kovtun V., and Kuznetsov A. The design of Boolean functions by modified hill climbing method // Cryptology ePrint Archive. Report 2008/111. 2008.
22. McLaughlin J., Clark J.A. Evolving balanced Boolean functions with optimal resistance to algebraic and fast algebraic attacks, maximal algebraic degree, and very high nonlinearity // Cryptology ePrint Archive. Report 2013/011. 2013.
2. Pieprzyk J. M¨ obius transforms, coincident Boolean functions and non-coincidence property of Boolean functions // International Journal of Computer Mathematics. 2011. № 7. P. 1398–1416.
3. Агафонова И.В., Дмитриева О.М. Методы построения полиномов Жегалкина для булевых функций // Материалы III Международной научно-технической и научно-методической конференции «Актуальные проблемы инфотелекоммуникаций в науке и образовании», 25–26 февраля 2014 г.). СПб.: Санкт-Петерб. гос. университет им. проф. М.А.Бонч-Бруевича, 2014. С. 525–530.
4. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.
5. Таранников Ю.В. О корреляционно-иммунных и устойчивых булевых функциях // Математические вопросы кибернетики. М.: Физматлит, 2002. Вып. 11. С. 91–148.
6. Агафонова И.В. Криптографические свойства нелинейных булевых функций // В сб.: Избранные главы дискретного гармонического анализа и геометрического моделирования. Часть I. Издание 2-е. Под ред. проф. В.Н. Малозёмова. СПб.: ВВМ, 2014. C. 428–451.
7. Городилова А.А. От криптоанализа шифра к криптографическому свойству булевой функции //Прикладная дискретная математика. 2016. № 3. С. 16–44.
8. Cusick T.W., and Stanica P. Cryptographic Boolean functions and applications. Amsterdam, Boston, Heidelberg, London, New York, Oxford, Paris, San Diego, San Francisco, Singapore, Sidney, Tokio: Academic Press, 2009.
9. Braeken A., Borissov Y., Nikova S., and Preneel B. Classification on Boolean functions of 6 variables or less with respect to some cryptographic properties // In Proc. 32nd Int. Colloq. Automata, Lang. Program. 2005. P. 324–334.
10. Фомичев В.М. Дискретная математика и криптология. Курс лекций / Под общ. ред. д-ра физ.-мат. н. Н.Д. Подуфалова. М.: ДИАЛОГ-МИФИ, 2003.
11. Токарева Н.Н. Симметричная криптография. Краткий курс: учебное пособие. Новосибирск.: Новосиб. гос. ун-т., 2012.
12. Черёмушкин А.В. Методы аффинной и линейной классификации двоичных функций // В сб.: Российская Академия наук. Академия криптографии Российской Федерации. Труды по дискретной математике. М.: Физматлит, 2001. Т. 4. С. 273–314.
13. Lechner R.J. A transform approach to logic design // IEEE Trans. on Computers. Jul. 1970. Vol. C-19. № 7. P. 627–640.
14. Millan W. New cryptographic applications of Boolean function equivalence classes // in ACISP. 2005. LNCS 3574. Brisbane. Australia. 2005. P. 572–583.
15. Zhang Y., Yang G., Hung W.N.N., and Zhang J. Computing Affine Equivalence Classes of Boolean functions by group isomorphism // IEEE Trans. on Computers. Dec. 2016. Vol. 65. № 7. P. 3606–3616.
16. Meng Q., Zhang G., Yang M., and Wang Z. Analysis of affinely equivalent Boolean functions // Sci China Ser F-Inf Sci. June 2007. Vol. 50. № 3. P. 299–306.
17. Millan W., Fuller J., and E. Dawson E. New concepts in evolutionary search for Boolean functions in cryptology // In Proc. of CEC 2003. IEEE. 2003. P. 2157–2164.
18. Fuller J. Analysis of affine equivalent Boolean functions for cryptography. PhD thesis. Queensland University of Technology. Brisbane. Australia. 2003.
19. Burnett L., Millan W., Dawson E., and Clark A. Simpler methods for generating better Boolean functions with good cryptographic properties // Australasian Journal of Combinatorics. 2004. Vol. 29. P. 231–247.
20. Picek S., Jakobovic D., Miller J.F., Marchiori E., and Batina L. Evolutionary methods for the construction of cryptographic Boolean functions // In Proc. EuroGP 2015. LNCS 9025. P. Machado, MI. Heywood, J. McDermott, M. Castelli, P. Garcia-Sanchez, P. Burelli, S. Risi, K. Sim (eds.) Switzerland: Springer, 2015. P. 192–204.
21. Izbenko Y., Kovtun V., and Kuznetsov A. The design of Boolean functions by modified hill climbing method // Cryptology ePrint Archive. Report 2008/111. 2008.
22. McLaughlin J., Clark J.A. Evolving balanced Boolean functions with optimal resistance to algebraic and fast algebraic attacks, maximal algebraic degree, and very high nonlinearity // Cryptology ePrint Archive. Report 2013/011. 2013.
Published
2017-11-22
How to Cite
Дмитриева, О. М., & Агафонова, И. В. (2017). Bounded Search of Cryptographically Strong Boolean Functions. Computer Tools in Education, (3), 20-28. Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1464
Issue
Section
Unsolved Problems for Young Scientists
This work is licensed under a Creative Commons Attribution 4.0 International License.
