S-блоки специального вида от малого числа переменных

$S$-блоки специального вида от малого числа переменных

Зюбина Д. А., Токарева Н. Н.
Дискретный анализ и исследование операций, 30, 2, 67-80 (2023)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2023.30.729

Аннотация:

При построении блочных шифров в качестве $S$-блоков необходимо использовать векторные булевы функции со специальными криптографическими свойствами для стойкости шифра к различным видам криптоанализа. В данной работе исследуется следующая конструкция $S$-блока. Пусть $\pi$ — перестановка $n$ элементов, $\pi^i$ — $i$-кратное применение перестановки $\pi$, $f$ — булева функция от $n$ переменных. 
Рассматривается векторная булева функция $F_\pi : \mathbb{Z}_2^n \to \mathbb{Z}_2^n$ вида $F_{\pi}(x) = (f(x), f(\pi(x)), \dots , f(\pi^{n−1} (x)))$. В данной статье изучаются такие криптографические свойства $F_\pi$ от малого числа переменных, как сбалансированность, высокая алгебраическая степень, низкая $\delta$-дифференциальная равномерность, высокая нелинейность в зависимости от булевой функции $f$ и перестановки $\pi$. Получены полные множества булевых функций $f$ и векторных булевых функций $F_\pi$ с максимальной алгебраической иммунностью от малого числа переменных.  
Библиогр. 16.

Литература:
  1. Matsui M. Linear cryptanalysis method for DES cipher // Advances in cryptology — EUROCRYPT’93. Proc. Workshop Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 386–397 (Lect. Notes Comput. Sci.; V. 765).
     
  2. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V. 4. P. 3–72.
     
  3. Courtois N. T., Meier W. Algebraic attacks on stream ciphers with linear feedback // Advances in cryptology — EUROCRYPT 2003. Proc. Int. Conf. Theory and Application of Cryptographic Techniques (Warsaw, Poland, May 4–8, 2003). Heidelberg: Springer, 2003. P. 345–359 (Lect. Notes Comput. Sci.; V. 2656).
     
  4. Cusick T. W., Stanica P. Cryptographic Boolean functions and applications. San Diego, CA: Elsevier, 2009. 288 p.
     
  5. Carlet C. Vectorial Boolean functions for cryptography // Boolean models and methods in mathematics, computer science, and engineering. Cambridge: Camb. Univ. Press, 2010. P. 398–470.
     
  6. Tokareva N. N. Bent functions: Results and applications to cryptography. Amsterdam: Elsevier, 2015. 221 p.
     
  7. Городилова А. А. От криптоанализа шифра к криптографическому свойству булевой функции // Прикл. дискрет. математика. 2016. № 3. С. 16–44.
     
  8. Панкратова И. А. Булевы функции в криптографии. Томск: Изд. дом Томск. гос. ун-та, 2014. 88 с.
     
  9. Tokareva N. N., Gorodilova A. A., Agievich S. V. [et al.]. Mathematical methods in solutions of the problems from the Third International Students’ Olympiad in Cryptography // Прикл. дискрет. математика. 2018. № 40. С. 34–58.
     
  10. Dillon J. F. Elementary Hadamard difference sets: PhD thesis. College Park: Univ. Maryland, 1974.
     
  11. Alsalami Y. Constructions with high algebraic degree of differentially $4$-uniform ($n, n − 1$)-functions and differentially $8$-uniform ($n, n − 2$)-functions // Cryptogr. Commun. 2018. V. 10, No. 4. P. 611–628.
     
  12. Browning K. A., Dillon J. F., McQuistan M. T., Wolfe A. J. An APN permutation in dimension six // Finite fields: Theory and applications. Proc. 9th Int. Conf. Finite Fields and Applications (Dublin, Ireland, July 13–17, 2009). Providence: AMS, 2010. P. 33–42. (Contemp. Math.; V. 518).
     
  13. Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean models and methods in mathematics, computer science, and engineering. Cambridge: Camb. Univ. Press, 2010. P. 257–397.
     
  14. Nyberg K. Differentially uniform mappings for cryptography // Advances in cryptology — EUROCRYPT’93. Proc. Workshop Theory and Application of Cryptographic Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 55–64 (Lect. Notes Comput. Sci.; V. 765).
     
  15. Carlet C. On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions // Enhancing cryptographic primitives with techniques from error correcting codes. Proc. NATO Adv. Res. Workshop (Veliko Tarnovo, Bulgaria, Oct. 6–9, 2008). Amsterdam: IOS Press, 2009. P. 104–116. (NATO Sci. Peace Secur. Ser. D: Inf. Commun. Secur.; V. 23).
     
  16. Покрасенко Д. П. О максимальной компонентной алгебраической иммунности векторных булевых функций // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 88–99.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0018).

Зюбина Дарья Александровна
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: zyubinadarya@gmail.com

Токарева Наталья Николаевна
  1. Институт математики им. С. Л. Соболева, 
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: crypto1127@mail.ru

Статья поступила 29 декабря 2021 г. 
После доработки — 8 ноября 2022 г. 
Принята к публикации 10 ноября 2022 г.

Abstract:

When constructing block ciphers, it is necessary to use vector Boolean functions with special cryptographic properties as $S$-blocks for the cipher’s resistance to various types of cryptanalysis. In this paper, we investigate the following $S$-block construction: let $\pi$ be a permutation on $n$ elements, $\pi^i$ $i$-multiple application $\pi$, and $f$ a Boolean function in $n$ variables. 
Define a vectorial Boolean function $F_\pi : \mathbb {Z}_2^n \to \mathbb {Z}_2^n$ as $F_{\pi}(x) = (f(x), f(\pi(x)), \dots , f(π^{n−1}(x)))$. We study cryptographic properties of $F_\pi$ such as high nonlinearity, balancedness, and low differential $\delta$-uniformity in dependence on properties of $f$ and $\pi$ for small $n$. Complete sets of Boolean functions $f$ and vector Boolean functions $F_\pi$ in a small number of variables with maximum algebraic immunity are also obtained. 
Bibliogr. 16.

References:
  1. M. Matsui, Linear cryptanalysis method for DES cipher, in Advances in cryptology — EUROCRYPT’93 (Proc. Workshop Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 386–397 (Lect. Notes Comput. Sci., Vol. 765).
     
  2. E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology 4, 3–72 (1991).
     
  3. N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in cryptology — EUROCRYPT 2003 (Proc. Int. Conf. Theory and Application of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003) (Springer, Heidelberg, 2003), pp. 345–359 (Lect. Notes Comput. Sci., Vol. 2656).
     
  4. T. W. Cusick and P. Stanica, Cryptographic Boolean Functions and Applications (Elsevier, San Diego, CA, 2009). 
     
  5. C. Carlet, Vectorial Boolean functions for cryptography, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, (Camb. Univ. Press, Cambridge, 2010), pp. 398–470.
     
  6. N. N. Tokareva, Bent Functions: Results and Applications to Cryptography (Elsevier, Amsterdam, 2015).
     
  7. A. A. Gorodilova, From cryptanalysis to cryptographic property of a Boolean function, Prikl. Diskretn. Mat., No. 3, 16–44 (2016) [Russian].
     
  8. I. A. Pankratova, Boolean Functions in Cryptography (Izd. Dom Tomsk. Gos. Univ., Tomsk, 2014) [Russian].
     
  9. N. N. Tokareva, A. A. Gorodilova, S. V. Agievich, [et al.]. Mathematical methods in solutions of the problems from the Third International Students’ Olympiad in Cryptography, Prikl. Diskretn. Mat., No. 40, 34–58 (2018). 
     
  10. J. F. Dillon, Elementary Hadamard difference sets, PhD Thesis (Univ. Maryland, College Park, 1974).
     
  11. Y. Alsalami, Constructions with high algebraic degree of differentially $4$-uniform ($n, n−1$)-functions and differentially $8$-uniform ($n, n−2$)-functions, Cryptogr. Commun. 10 (4), 611–628 (2018).
     
  12. K. A. Browning, J. F. Dillon, M. T. McQuistan, and A. J. Wolfe, An APN permutation in dimension six, in Finite Fields: Theory and Applications (Proc. 9th Int. Conf. Finite Fields and Applications, Dublin, Ireland, July 13–17, 2009) (AMS, Providence, 2010), pp. 33–42. (Contemp. Math., Vol. 518).
     
  13. C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, (Camb. Univ. Press, Cambridge, 2010), pp. 257–397.
     
  14. K. Nyberg, Differentially uniform mappings for cryptography, in Advances in cryptology — EUROCRYPT 2003 (Proc. Int. Conf. Theory and Application of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003) (Springer, Heidelberg, 1994), pp. 55–64 (Lect. Notes Comput. Sci., Vol. 765).
     
  15. C. Carlet, On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions, in Enhancing cryptographic primitives with techniques from error correcting codes. Proc. NATO Adv. Res. Workshop, Veliko Tarnovo, Bulgaria, Oct. 6–9, 2008 (IOS Press, Amsterdam, 2009), pp. 104–116. (NATO Sci. Peace Secur. Ser. D: Inf. Commun. Secur., Vol. 23).
     
  16. D. P. Pokrasenko, On the maximal component algebraic immunity of vectorial Boolean functions, Diskretn. Anal. Issled. Oper. 23 (2), 88–99 (2016) [Russian] [J. Appl. Ind. Math. 10 (2), 257–263 (2016)].