Том 25, номер 4, 2018 г., Стр. 59-80

УДК 519.8
Милосердов А. В.
Взаимно однозначные биномиальные функции над конечными полями

Аннотация:
Рассматриваются биномиальные функции над конечным полем порядка $2^n$. Найдено необходимое условие взаимной однозначности биномиальной функции. Доказано, что в случае простого числа $2^{n} - 1$ взаимно однозначных биномиальных функций не существует. Построены взаимно однозначные биномиальные функции в случае составного $n$, и найдены взаимно однозначные биномиальные функции для $n \le 8$.
Табл. 2, библиогр. 30.

Ключевые слова: векторная булева функция, биномиальная функция, взаимная однозначность, APN-функция.

DOI: 10.17377/daio.2018.25.611

Милосердов Алексей Васильевич ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: amiloserdov6@gmail.com

Статья поступила 20 февраля 2018 г.
Исправленный вариант — 4 июня 2018 г.

Литература

[1] Глухов М. М. О приближении дискретных функций линейными функциями // Мат. вопросы криптографии. 2016. Т. 7, № 4. С. 29–50.

[2] Городилова А. А. От криптоанализа шифра к криптографическому свойству булевой функции // Прикл. дискрет. математика. 2016. Т. 33, № 3. С. 16–44

[3] Покрасенко Д. П. О максимальной компонентной алгебраической иммунности векторных булевых функций // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 88–99.

[4] Сачков В. Н. Комбинаторные свойства дифференциально $2$-равномерных подстановок // Мат. вопросы криптографии. 2015. Т. 6, № 1. С. 159–179.

[5] Токарева Н. Н. Симметричная криптография. Краткий курс. Новосибирск: Новосиб. гос. ун-т, 2012. 234 с.

[6] Тужилин М. Э. Почти совершенные нелинейные функции // Прикл. дискрет. математика. 2009. Т. 5, № 3. С. 14–20.

[7] Ayad M., Belghaba K., Kihel O. On permutation binomials over finite fields // Bull. Aust. Math. Soc. 2014. No. 89. P. 112–124.

[8] Bracken C., Byrne E., Markin N., McGuire G. Fourier spectra of Binomial APN functions // SIAM J. Discrete Math. 2008. Vol. 2, No. 23. P. 596–608.

[9] Budaghyan L. Construction and analysis of cryptographic functions // Berlin: Springer-Verl., 2015. 176 p.

[10] Budaghyan L., Carlet C., Felke P., Leander G. An infinite class of quadratic APN functions which are not equivalent to power mappings // Proc. 17th IEEE Int. Symp. Information Theory (Seattle, USA, July 9–14,
2006). Piscataway: IEEE, 2006. P. 2637–2641.

[11] Budaghyan L., Carlet C., Leander G. Another class of quadratic APN binomials over $\mathbb {F}_{2^n}$ : the case $n$ divisible by $4$ // Proc. Int. Workshop Coding Cryptography (WCC 2007). (Versailles, France, Apr. 16–20, 2007). P. 49–58.

[12] Budaghyan L., Carlet C., Leander G. Constructing new APN functions from known ones // Finite Fields Appl. 2009. Vol. 15, No. 2. P. 150–159.

[13] Canteaut A., Charpin P., Kyureghyan G. A new class of monomial bent functions // Finite Fields Appl. 2008. Vol. 14, № 1. P. 221–241.

[14] 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 ACPTECC (Veliko Tarnovo, Bulgaria, Oct. 6–9, 2008). Amsterdam: IOS Press, 2009. P. 104–116.

[15] Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean models and methods in mathematics, computer science, and engineering. New York: Camb. Univ. Press, 2010. P. 257–397. (Encycl. Math. Its Appl.; Vol. 134).

[16] Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. New York: Camb. Univ. Press, 2010. P. 398–470. (Encycl. Math. Its Appl.; Vol. 134).

[17] Daemen J., Rijmen V. AES Proposal: Rijndael. Belgium, 1999.

[18] Daemen J., Rijmen V. The design of Rijndael. Heidelberg: Springer, 2002. 238 p.

[19] Dobbertin H. Almost perfect nonlinear power functions on F2n : the Welch case // IEEE Trans. Inf. Theory. 1999. Vol. 45, No. 4. P. 1271–1275.

[20] Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and Their Applications – SETA 2004. Rev. Sel. Papers 3rd Int. Conf. (Seoul, Korea, Oct. 24–28, 2004). Heidelberg: Springer, 2005. P. 1–29. (Lect. Notes Comput. Sci.; Vol. 3486).

[21] Dobbertin H., Leander G., Canteaut A., Carlet C., Felkea P., Gaborit P. Construction of bent functions via Niho power functions // J. Comb. Theory. Ser. A. 2006. Vol. 113, No. 5. P. 779–798.

[22] Hou X. Permutation polynomials over finite fields — A survey of recent advances // Finite Fields Their Appl., 2015. Vol. 32. P. 82–119

[23] Masuda A. M., Zieve M. E. Permutation binomials over finite fields // Trans. Am. Math. Soc. 2009. Vol. 361, No. 8. P. 4169–4180.

[24] Niederreiter H., Robinson K. Complete mappings of finite fields // J. Aust. Math. Soc. 1982. Vol. 33, No. 2. P. 197–212.

[25] Nyberg K. Differentially uniform mappings for cryptography // Advances in Cryptology (EUROCRYPT’93). Proc. Workshop Theory Appl. Crypt. Tech. (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. (Lect. Notes Comput. Sci.; Vol. 765).

[26] Seroussi G. Table of low-weight binary irreducible polynomials. Tech. Rep. HPL–98–135. Hewlett-Packard, 1998.

[27] Tokareva N. N. Bent functions: Results and applications to cryptography. London: Acad. Press, 2015. 220 p.

[28] Turnwald G. Permutation polynomials of binomial type // Contributions to general algebra. Vienna: Holder–Pichler–Tempsky, 1988. Vol. 6. 281–286.

[29] Shallue C. J. Permutation polynomials of finite fields // Honours project. Monash University, 2012.

[30] Yang M., Meng Q., Zhang H. Evolutionary design of trace form bent functions // Cryptology ePrint Arch. Rep. 2005/322. https://eprint.iacr.org/2005/322.