От криптоанализа шифра к криптографическому свойству булевой функции | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/2

Настоящий обзор посвящён описанию основных криптографических свойств булевых функций, таких, как высокая алгебраическая степень, уравновешенность и совершенная уравновешенность, лавинные характеристики, отсутствие линейных структур, корреляционная иммунность и устойчивость, высокая нелинейность, статистическая независимость, алгебраическая иммунность, уровень аффинности и k-нормальность, дифференциальная равномерность, разложимость в сумму специальных функций, мультипликативная сложность, высокие мощности линеари-зационных множеств. Исследуются вопросы формирования данных свойств на основе атак на блочные и поточные шифры, использующих определённые уязвимости булевых функций, являющихся компонентами шифров; приводятся основные идеи данных атак. Кратко рассмотрены базовые теоретические результаты, полученные для каждого из свойств, и сформулированы открытые проблемы в данной области.
  • Title От криптоанализа шифра к криптографическому свойству булевой функции
  • Headline От криптоанализа шифра к криптографическому свойству булевой функции
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(33)
  • Date:
  • DOI 10.17223/20710410/33/2
Ключевые слова
булева функция, поточный шифр, блочный шифр, алгебраическая степень, уравновешенность, совершенная уравновешенность, лавинные характеристики, линейная структура, корреляционная иммунность, устойчивость, нелинейность, статистическая независимость, алгебраическая иммунность, уровень аффинности, k-нормальность, дифференциальная равномерность, пороговое разбиение, мультипликативная сложность, линеаризационное множество, линейная сложность, корреляционный криптоанализ, быстрая корреляционная атака, линейный криптоанализ, статистический аналог, алгебраический криптоанализ, дифференциальный криптоанализ, атаки по сторонним каналам, линеаризационная атака, Boolean function, stream cipher, block cipher, algebraic degree, balanced-ness, perfect balancedness, avalanche characteristics, linear structure, correlation immunity, resiliency, nonlinearity, statistical independence, algebraic immunity, affinity level, k-normality, differential uniformity, threshold implementation, multiplicative complexity, linearization set, linear complexity, correlation attack, fast correlation attack, linear cryptanalysis, statistical analogue, differential cryptanalysis, side-channel attacks, linearization attack
Авторы
Ссылки
Агибалов Г. П. Избранные теоремы начального курса криптографии: учеб. пособие. Томск: Изд-во НТЛ, 2005. 116с.
Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным полем // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 4-9.
Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского государственного университета. Приложение. 2003. №6. С. 31-41.
Агибалов Г. П., Панкратова И. А. Элементы теории статистических аналогов дискретных функций с применением в криптоанализе итеративных блочных шифров // Прикладная дискретная математика. 2010. №3. C. 51-68.
Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2002. 480с.
Буряков М. Л. Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций: дис..канд. физ.-мат. наук. М., 2007.
Глухов М. М. О совершенно и почти совершенно нелинейных функциях // Математические вопросы криптографии. 2016. (в печати)
Глухов М. М. Планарные отображения конечных полей и их обобщения. Презентация для конф. «Алгебра и логика, теория и приложения». Красноярск, 21-27 июля, 2013.
Городилова А. А. Характеризация почти совершенно нелинейных функций через подфункции // Дискретная математика. 2015. Т. 27. Вып.3. C.3-16.
Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18. Вып.3. C. 152-159.
Логачев О. А., Сальников А. А, Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
Логачев О. А., Сальников А. А., Ященко В. В. Корреляционная иммунность и реальная секретность // Математика и безопасность информационных технологий. Материалы конф. в МГУ 23-24 октября 2003 г. М.: МЦНМО, 2004. С. 165-171.
Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. Т. 5. Вып. 4. С. 73-97.
Панкратова И. А. Булевы функции в криптографии: учеб. пособие. Томск: Издательский Дом Томского государственного университета, 2014. 88 с.
Сачков В. Н. Комбинаторные свойства дифференциально 2-равномерных подстановок // Математические вопросы криптографии. 2015. Т. 6. Вып. 1. С. 159-179.
Селезнева С. Н. Мультипликативная сложность некоторых функций алгебры логики // Дискретная математика. 2014. Т. 26. Вып. 4. C. 100-109.
Смышляев С. В. О криптографических слабостях некоторых классов преобразований двоичных последовательностей // Прикладная дискретная математика. 2010. №1. С. 5-15.
Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикладной и промышленной математики. 1994. Т. 1. Вып. 1. С. 33-55.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Математич. вопросы кибернетики. 2002. Вып. 11. С. 91-148.
Токарева Н. Н. Симметричная криптография. Краткий курс: учеб. пособие. Новосибирск: Новосибирский государственный университет, 2012. 232 с.
Bilgin B., NikovaS., Nikov V., et al. Threshold implementations of small S-boxes // Cryptography and Communications. 2015. V. 7. No. 1. P. 3-33.
Blondeau C. and Nyberg K. Perfect nonlinear functions and cryptography // Finite Fields and their Applications. 2015. V. 32. P. 120-147.
Braeken A. Cryptographic Properties of Boolean Functions and S-boxes. PhD Thesis, Katholieke Universiteit Leuven, 2006.
Carlet С. Boolean functions for cryptography and error correcting codes // Ch. 8 of the Monograph "Boolean Methods and Models in Mathematics, Computer Science, and Engineering", Cambridge Univ. Press, 2010. P. 257-397.
Carlet C. Vectorial Boolean functions for cryptography // Ch. 9 of the Monograph "Boolean Methods and Models in Mathematics, Computer Science, and Engineering", Cambridge Univ. Press, 2010. P. 398-472.
Carlet C., Charpin P., and Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Des. Codes Cryptogr. 1998. V. 15. P. 125-156.
Charpin P. Normal Boolean functions //J. Complexity. 2004. V. 20. P. 245-265.
Courtois N., Hulme D., and Mourouzis T. Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis. Cryptology ePrint Archive. Report 2011/475 (2011).
Courtois N. and Meier W. Algebraic attack on stream ciphers with linear feedback // LNCS. 2003. V. 2656. P. 345-359.
Cusick T. W. and Stanica P. Cryptographic Boolean Functions and Applications. Acad. Press. Elsevier, 2009. 245 p.
Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // FSE'95. LNCS. 1995. V. 1008. P. 61-74.
Evertse J.H. Linear structures in block ciphers // EUROCRYPT'87. LNCS. 1988. V.304. P. 249-266.
Fon-Der-Flaass D. G. A bound on correlation immunity // Siberian Elektron. Mat. Izv. 2007. No. 4. P. 133-135.
Golic J.Dj. On the security of nonlinear filter generators // FSE'96. LNCS. 1996. V. 1039. P. 173-188.
Gorodilova A. On a Remarkable Property of APN Gold Functions. Cryptology ePrint Archive. Report 2016/286 (2016).
Mihaljevic M., Gangopadhyay S., Paul G., and Imai H. An algorithm for the internal state recovery of Grain-v1 // Proc. CECC'2011. Debrecen, Hungary, June 30-July 2, 2011. P. 7-20.
Nikova S., Rechberger C., and Rijmen V. Threshold implementations against side-channel attacks and glitches // LNCS. 2006. V. 4307. P. 529-545.
Nyberg K. Differentially uniform mappings for cryptography // Eurocrypt'93. LNCS. 1994. V. 765. P. 55-64.
Preneel B., Van Leekwijck W., Van Linden L., et al. Propagation characteristics of Boolean functions // Eurocrypt'90. LNCS. 1991. V.473. P. 161-173.
Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Trans. Inform. Theory. 1984. V.30. No. 5. P. 776-780.
Tarannikov Y. V. Generalized proper matrices and constructing of m-resilient Boolean functions with maximal nonlinearity for expanded range of parameters // Siberian Elektron. Mat. Izv. 2014. No. 11. P. 229-245.
Tokareva N. Bent Functions: Results and Applications to Cryptography. Acad. Press. Elsevier, 2015. 220 p.
Webster A. F. and Tavares S. E. On the design of S-boxes // Crypto'85. LNCS. 1986. V. 218. P. 523-534.
Zajac P. and Jokay M. Multiplicative complexity of bijective 4 x 4 S-boxes // Cryptography and Communications. 2014. V. 6. No. 3. P. 255-277.
Zhang X.-M. and Zheng Y. GAC - the criterion for Global Avalanche Characteristics of cryptographic functions //J. Universal Computer Science. 1995. V. 1. No. 5. P. 320-337.
 От криптоанализа шифра к криптографическому свойству булевой функции | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/2
От криптоанализа шифра к криптографическому свойству булевой функции | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/2