HomeIssuesThe linear spectrum of quadratic APN functions

The linear spectrum of quadratic APN functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/1

Almost perfect nonlinear (APN) functions are studied. We introduce the linear spectrum Л = (A,..., A-1) of a quadratic APN function F, where Af equals the number of linear functions L such that |{a e F^ \ {0} : Ba(F) = Ba(F + L)}| = k and Ba(F) = {F(x) + F(x + a) : x e F^}. We prove that Af = 0 for all even k < 2-2 and for all k < (2 - 1)/3, where F is a quadratic APN function in even number of variables n. Linear spectra for APN functions in small number of variables n = 3, 4, 5, 6 are computed and presented. We consider APN Gold functions F(x) = x + for (k,n) = 1 and prove that An-1 = 2 if n = 4t for some t and k = n/2 ± 1, and A-1 = 2 otherwise.
Download file
Counter downloads: 200
  • Title The linear spectrum of quadratic APN functions
  • Headline The linear spectrum of quadratic APN functions
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(34)
  • Date:
  • DOI 10.17223/20710410/34/1
Keywords
APN-функция, ассоциированная булева функция, линейный спектр, функция Голда, APN function, associated Boolean function, linear spectrum, Gold function
Authors
References
Nyberg K. and Knudsen L. R. Provable security against differential cryptanalysis // CRYPTO'92. LNCS. 1993. V. 740. P. 566-574.
Глухое М. М. О совершенно и почти совершенно нелинейных функциях // Математические вопросы криптографии. 2016. (в печати)
Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3. С. 14-20.
Pott A. Almost perfect and planar functions // Des. Codes Cryptogr. 2016. V. 78. P. 141-195.
Carlet C. Open questions on nonlinearity and on APN functions // LNCS. 2015. V. 9061. P. 83-107.
Глухов М. М. О матрицах переходов разностей при использовании некоторых модулярных групп // Математические вопросы криптографии. 2013. Т. 4. №4. С. 27-47.
Сачков В. Н. Комбинаторные свойства дифференциально 2-равномерных подстановок // Математические вопросы криптографии. 2015. Т. 6. №1. С. 159-179.
Городилова А. А. Характеризация почти совершенно нелинейных функций через подфункции // Дискретная математика. 2015. Т. 27. Вып.3. C.3-16.
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.
Carlet C. and Prouff E. On plateaued functions and their constructions // LNCS. 2003. V. 2887. P. 54-73.
Городилова А. А. О дифференциальной эквивалентности квадратичных APN-функций // Прикладная дискретная математика. Приложение. 2016. №9. C. 21-24.
Brinkman M. and Leander G. On the classification of APN functions up to dimension five // Des. Codes Cryptogr. 2008. V. 49. Iss. 1. P. 273-288.
Browning K. A., Dillon J. F., Kibler R. E., and McQuistan M. T. APN polynomials and related codes //J. Combinatorics, Information and System Science. 2009. V. 34. No. 1-4. P. 135-159.
Edel Y. Quadratic APN functions as subspaces of alternating bilinear forms // Contact Forum Coding Theory and Cryptography III. Belgium, 2009. P. 11-24.
Nyberg K. Differentially uniform mappings for cryptography // Eurocrypt'93. LNCS. 1994. V. 765. P. 55-64.
Yu Y., Wang M. , and Li Y. A Matrix Approach for Constructing Quadratic APN Functions. Cryptology ePrint Archive, Report 2013/007. 2013.
The linear spectrum of quadratic APN functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/1
The linear spectrum of quadratic APN functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/1