ГлавнаяАрхивNonlinearity of APN functions: comparative analysis and estimates

Nonlinearity of APN functions: comparative analysis and estimates | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/2

Нелинейность APN-функции определяется как расстояние Хэмминга от неё до множества аффинных отображений в пространстве значений векторных булевых функций фиксированной размерности. Для APN-функций размерности n получены нижняя граница нелинейности вида 2n - √(2n+1 - 7 · 2-2) - 2 -1 и соответствующая ей нижняя граница порядка аффинности. Найдены точные значения нелинейности всех APN-функций размерности, не превосходящей 5, а также для одной известной APN-подстановки размерности 6 и для всех дифференциально 4-равномерных подстановок размерности 4.
  • Title Nonlinearity of APN functions: comparative analysis and estimates
  • Headline Nonlinearity of APN functions: comparative analysis and estimates
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 61
  • Date:
  • DOI 10.17223/20710410/61/2
Ключевые слова
векторная булева функция, подстановка, APN-функция, EA-эквивалентность, нелинейность, дифференциальная равномерность
Авторы
Ссылки
Glukhov M. M. О priblizhenii diskretnvkh funktsiv linevnymi funktsivami [On the approximation of discrete functions by linear functions], Matematicheskiye Voprosv Kriptograffi, 2016, vol. 7, no. 4, pp. 29-50. (in Russian).
Nyberg K. On the construction of highly nonlinear permutations. LNCS, 1993, vol. 658, pp.92-98.
Nyberg K. Differentially uniform mappings for cryptography. LNCS, 1994, vol. 765, pp. 55-64.
Nyberg K. and Knudsen L. R. Provable security against a differential attack. LNCS, 1993, vol. 740, pp. 566-574.
Chen L. and Fu F. On the nonlinearity of multi-output Boolean functions. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2001, vol. 34, no. 4, pp. 28-33. (in Chinese).
Liu J. and Chen L. On nonlinearity of the second type of multi-output Boolean functions. Chinese J. Eng. Math., 2014, vol. 31, no. 1, pp.9-22. (in Chinese).
Liu J., Mesnager S., and Chen L. On the nonlinearity of S-boxes and linear codes. Cryptography and Communications, 2017, vol. 9, no. 1, pp. 345-361.
Nagy G.P. Thin Sidon sets and the nonlinearity of vectorial Boolean functions, https://arxiv.org/pdf/2212.05887.pdf, 2022.
Ryabov V. G. О priblizhenii vektornvkh funktsiv nad konechnvmi polvami i ikh ogranicheniv na lineynyve mnogoobraziva affinnymi analogami [On approximation of vectorial functions over finite fields and their restrictions to linear manifolds by affine analogues]. Diskretnava Matematika, 2022, vol.34, no. 2, pp. 83-105. (in Russian).
Ryabov V. G. К voprosu о priblizhenii vektornvkh funktsiv nad konechnvmi polvami affinnymi analogami (On the question of approximation of vectorial functions over finite fields by affine analogues]. Matematicheskive Voprosv Kriptografii, 2022, vol. 13, no. 4, pp. 125-146. (in Russian).
Carlet C. and Ding C. Nonlinearities of S-boxes. Finite Fields Appl., 2007, vol. 13, no. 1, pp.121-135.
Carlet C. Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions. Designs Codes Cryptography, 2011, vol. 59, no. 1-3, pp.89-109.
Carlet C. Open questions on nonlinearity and on APN functions. LNCS, 2015, vol. 9061, pp.83-107.
Carlet C. On the properties of the Boolean functions associated to the differential spectrum of general APN functions and their consequences. IEEE Trans. Inform. Theory, 2021, vol. 67, no. 10, pp.6926-6939.
Carlet C. Bounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions. IEEE Trans. Inform. Theory, 2021, vol. 67, no. 12, pp. 8325-8334.
Carlet C., Heuser A., and Picek S. Trade-offs for S-Boxes: cryptographic properties and side-channel resilience. LNSC, 2017, vol. 10355, pp. 393-414.
Gorodilova A. A., Tokareva N. N., Agievich S. V., et al. An overview of the Eight International Olympiad in Cryptography "Non-Stop University CRYPTO". Sibirskive Elektronnvve Matematicheskive Izvestiva, 2022, vol. 19, no. 1, pp. A.9-A.37.
Нои X. Affinity of permutations of E/. Discrete Appl. Math., 2006, vol. 154, no. 2, pp.313-325.
Carlet C. Vectorial Boolean functions for cryptography. In Y. Crama & P. Hammer (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications), Cambridge, Cambridge University Press, 2010, pp. 398-470.
Gorshkov S. P. and Dvinyaninov A. V. Nizhnvava i verkhnvava otsenki porvadka affinnosti preobrazovaniv prostranstv bulevvkh vektorov (Lower and upper bounds on the affinity order of transformations of spaces of Boolean vectors]. Prikladnava Diskretnava Matematika, 2013, no. 2(20), pp. 14-18. (in Russian).
Brinkmann M. and Leander G. On the classification of APN functions up to dimension five. Designs Codes Cryptography, 2008, vol. 49, no. 1-3, pp. 273-288.
Brinkmann M. Extended Affine and CCZ Equivalence up to Dimension 4. https://eprint.iacr.org/2019/316.pdf, 2019.
Budaghyan L., Carlet C., and Pott A. New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inform. Theory, 2006, vol. 52, no. 3, pp. 1141-1152.
Dobbertin P.I. Almost perfect nonlinear power functions on GF(2ra): the Niho case. Information and Computation, 1999, vol. 151, no. 1-2, pp. 57-72.
Yoshiara S. Equivalences of power APN functions with power or quadratic APN functions. J. Algebraic Combinatorics, 2016, vol. 44, no.3, pp. 561-585.
Dempwolff U. CCZ equivalence of power functions. Designs Codes Cryptography, 2018, vol. 86, no. 3, pp.665-692.
Dempwolff U. Correction to: CCZ equivalence of power functions. Designs Codes Cryptography, 2022, vol. 90, no. 2, pp. 473-475.
Calderini M. On the EA-classes of known APN functions in small dimensions, https://eprint.iacr.org/2019/369.pdf, 2019.
Calderini M. On the EA-classes of known APN functions in small dimensions. Cryptography and Communications, 2020, vol. 12, no. 5, pp. 821-840.
Browning K. A., Dillon J.F., McQuistan M. T., and Wolfe A. J. An APN permutation in dimension six. Finite Fields: Theory and Appl., 2010, pp. 33-42.
Leander G. and Poschmann A. On the classification of 4 bit S-boxes. LNCS, 2007, vol. 4547, pp.156-176.
Nonlinearity of APN functions: comparative analysis and estimates | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/2
Nonlinearity of APN functions: comparative analysis and estimates | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/2