Ограниченный поиск криптографически сильных булевых функций
Аннотация
В статье рассмотрены способы получения булевых функций с желательными криптографическими свойствами, основанные на поисковых алгоритмах. Исследованы возможности оптимизации таких алгоритмов, прежде всего за счет значительного сокращения области поиска. Использованы общая идея разбиения множества функций на классы эквивалентности в соответствии с какой-либо группой преобразований и идея перебора этих классов как вершин особого графа, называемого графом классов. Предложенная в статье P-эквивалентность, рассматриваемая на множестве сбалансированных булевых функций, обеспечивает сохранение практически всех криптографически значимых свойств функций внутри одного класса эквивалентности.
Литература
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.
Опубликован
2017-11-22
Как цитировать
Дмитриева, О. М., & Агафонова, И. В. (2017). Ограниченный поиск криптографически сильных булевых функций. Компьютерные инструменты в образовании, (3), 20-28. извлечено от http://cte.eltech.ru/ojs/index.php/kio/article/view/1464
Выпуск
Раздел
Нерешенные задачи для молодых ученых
Материал публикуется под лицензией:
