The survey is devoted to description of basic, but not all, cryptographic properties of Boolean functions: algebraic degree, balancedness and perfect balancedness, avalanche characteristics, non-existence of linear structures, correlation immunity and resiliency, high nonlinearity, statistical independence, algebraic immunity, affinity level and k-normality, differential uniformity, threshold implementation, multiplicative complexity, high cardinality of linearization sets. The questions about these properties formation are studied based on the attacks on stream and block ciphers that exploit the vulnerabilities of Boolean functions used in ciphers as components. The ideas of such attacks are given. We briefly describe the basic theoretical results obtained for each of the properties and formulate open problems in this area.
Download file
Counter downloads: 380
- Title From cryptanalysis to cryptographic property of a Boolean function
- Headline From cryptanalysis to cryptographic property of a Boolean function
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(33)
- Date:
- DOI 10.17223/20710410/33/2
Keywords
булева функция, поточный шифр, блочный шифр, алгебраическая степень, уравновешенность, совершенная уравновешенность, лавинные характеристики, линейная структура, корреляционная иммунность, устойчивость, нелинейность, статистическая независимость, алгебраическая иммунность, уровень аффинности, 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 attackAuthors
References
Агибалов Г. П. Избранные теоремы начального курса криптографии: учеб. пособие. Томск: Изд-во НТЛ, 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.
From cryptanalysis to cryptographic property of a Boolean function | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 3(33). DOI: 10.17223/20710410/33/2
Download full-text version
Counter downloads: 1059