The linear spectrum of quadratic APN functions

A. A. Gorodilova

Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 5-16.

Résumé

Almost perfect nonlinear (APN) functions are studied. We introduce the linear spectrum $\Lambda^F = (\lambda_0^F, \ldots, \lambda_{2^n-1}^F)$ of a quadratic APN function $F$, where $\lambda_k^F$ equals the number of linear functions $L$ such that $|\{a\in\mathbb{F}_2^n\setminus\{\mathbf{0}\}: B_a(F) = B_a(F+L)\}| = k$ and $B_a(F) = \{F(x)+F(x+a): x\in\mathbb{F}_2^n\}$. We prove that $\lambda_k^F=0$ for all even $k \leqslant 2^n-2$ and for all $k(2^n-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^{2^k+1}$ for $(k,n)=1$ and prove that $\lambda^F_{2^n-1}=2^{n+n/2}$ if $n=4t$ for some $t$ and $k = n/2 \pm 1$, and $\lambda^F_{2^n-1} = 2^{n}$ otherwise.

Détail

Keywords: APN function, associated Boolean function, linear spectrum, Gold function.

Bibliographie

[1] Nyberg K., Knudsen L. R., “Provable security against differential cryptanalysis”, CRYPTO'92, LNCS, 740, 1993, 566–574 | MR | Zbl

[2] Glukhov M. M., “About perfectly and almost perfectly non-linear functions”, Matematicheskie Voprosy Kriptografii, 2016 (in Russian)

[3] Tuzhilin M. E., “APN-functions”, Prikladnaya Diskretnaya Matematika, 2009, no. 3, 14–20 (in Russian)

[4] Pott A., “Almost perfect and planar functions”, Des. Codes Cryptogr., 78 (2016), 141–195 | DOI | MR | Zbl

[5] Carlet C., “Open questions on nonlinearity and on APN functions”, LNCS, 9061, 2015, 83–107 | MR | Zbl

[6] Glukhov M. M., “On the matrices of transitions of differences for some modular groups”, Mat. Vopr. Kriptogr., 4:4 (2013), 27–47 (in Russian) | MR

[7] Sachkov V. N., “Combinatorial properties of differentially 2-uniform substitutions”, Mat. Vopr. Kriptogr., 6:1 (2015), 159–179 (in Russian) | MR

[8] Gorodilova A. A., “Characteristics of almost perfectly non-linear functions by subfunctions”, Diskr. Mat., 27:3 (2015), 3–16 (in Russian) | DOI

[9] Carlet C., Charpin P., Zinoviev V., “Codes, bent functions and permutations suitable for DES-like cryptosystems”, Des. Codes Cryptogr., 15 (1998), 125–156 | DOI | MR | Zbl

[10] Carlet C., Prouff E., “On plateaued functions and their constructions”, LNCS, 2887, 2003, 54–73 | Zbl

[11] Gorodilova A. A., “On differential equivalence of quadratic APN functions”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2016, no. 9, 21–24 (in Russian)

[12] Brinkman M., Leander G., “On the classification of APN functions up to dimension five”, Des. Codes Cryptogr., 49:1 (2008), 273–288 | DOI | MR | Zbl

[13] Browning K. A., Dillon J. F., Kibler R. E., McQuistan M. T., “APN polynomials and related codes”, J. Combinatorics, Information and System Science, 34:1–4 (2009), 135–159 | MR | Zbl

[14] Edel Y., “Quadratic APN functions as subspaces of alternating bilinear forms”, Contact Forum Coding Theory and Cryptography III (Belgium, 2009), 11–24 | Zbl

[15] Nyberg K., “Differentially uniform mappings for cryptography”, Eurocrypt'93, LNCS, 765, 1994, 55–64 | MR | Zbl

[16] Yu Y., Wang M., Li Y., A Matrix Approach for Constructing Quadratic APN Functions, Cryptology ePrint Archive, Report 2013/007, 2013 | MR