On constructing APN permutations using subfunctions

V. A. Idrisova

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 17-27.

Résumé

Our subject for investigation is the problem of APN permutation existence for even number of variables. In this work, we consider $2$-to-$1$ functions that are isomorphic to $(n-1)$-subfunctions of APN permutations. These $2$-to-$1$ functions can be obtained with a special algorithm which searches for $2$-to-$1$ APN functions that are potentially EA-equivalent to permutations. The algorithm is based on constructing special symbol sequences that are called admissible. It is known that $(n-1)$-subfunction of an APN permutation can be represented as a differentially $4$-uniform $2$-to-$1$ function that takes values from the half of the Boolean cube. Therefore, the following algorithm can be used to search for APN permutations. On the first step all the possible admissible sequences are constructed and we assign obtained sequences in order to find a differentially $4$-uniform $2$-to-$1$ function. Therefore, obtained function can be isomorphic to a $(n-1)$-subfunction of an APN permutation, so, this $(n-1)$-subfunction can be expanded to bijective APN function. In order to construct an APN permutation, we need to find all possible coordinate Boolean functions $f$ such that the bijective function constructed from the given $(n-1)$-subfunction $S$ and function $f$ is APN. Unfortunately, the exhaustive search through the set of potential coordinate functions is computationally hard when $n\ge7$, so, we need to estimate the number $n(S)$ of such coordinate Boolean functions. For a given bijective vectorial function $F$, we introduce an associated permutation $F^\star$ as follows. We split the set $\mathbb F_2^n$ into two disjoint subsets $\mathcal F_1$ and $\mathcal F_2$, fix integer $k$, indices $i_1,\dots,i_k$, and index $j\not\in\{i_1,\dots,i_k\}$. Then the value $F^\star(x)$ is equal to $F(x)$ if $F(x)\in\mathcal F_1$ and $F^\star(x)$ is equal to $F(x)+e_j$ otherwise. We prove that $F^\star$ is an APN permutation if and only if $F$ is an APN permutation. This fact allows us to obtain the necessary bound. We prove that if $n(S)$ is not equal to zero, then $n(S)\ge2^n$.

Détail

Keywords: vectorial function, APN function, subfunction.
Mots-clés : permutation

Bibliographie

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

[2] Gold R., “Maximal recursive sequences with 3-valued recursive crosscorrelation functions”, IEEE Trans. Inform. Theory, 14 (1968), 154–156 | DOI | Zbl

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

[4] Kasami T., “The weight enumerators for several classes of subcodes of the second order binary Reed–Muller codes”, Inform. Control, 18 (1971), 369–394 | DOI | MR | Zbl

[5] Janwa H., Wilson R., “Hyperplane sections of Fermat varieties in $P^3$ in char. 2 and some applications to cyclic codes”, Proc. AAECC-10, LNCS, 673, 1993, 180–194 | MR | Zbl

[6] Canteaut A., Charpin P., Dobbertin H., “Binary $m$-sequences with three-valued crosscorrelation: a proof of Welch conjecture”, IEEE Trans. Inform. Theory, 46 (2000), 4–8 | DOI | MR | Zbl

[7] Dobbertin H., “Almost perfect nonlinear functions over $\mathrm{GF}(2^n)$: the Welch case”, IEEE Trans. Inform. Theory, 45 (1999), 1271–1275 | DOI | MR | Zbl

[8] Dobbertin H., “Almost perfect nonlinear functions over $\mathrm{GF}(2^n)$: the Niho case”, Inform. Comput., 151 (1999), 57–72 | DOI | MR | Zbl

[9] Hollmann H., Xiang Q., “A proof of the Welch and Niho conjectures on crosscorrelations of binary $m$-sequences”, Finite Fields Appl., 7 (2001), 253–286 | DOI | MR | Zbl

[10] Beth T., Ding C., “On almost perfect nonlinear permutations”, EUROCRYPT'93, LNCS, 765, 1993, 65–76 | MR

[11] Dobbertin H., “Almost perfect nonlinear power functions over $\mathrm{GF}(2^n)$: a new case for $n$ divisible by 5”, Finite Fields and Applications, eds. D. Jungnickel, H. Niederreiter, Springer, Berlin–Heidelberg, 2001, 113–121 | DOI | MR | Zbl

[12] Glukhov M. M., “On the approximation of discrete functions by linear functions”, Mat. Vopr. Kriptogr., 7:4 (2016), 29–50 (in Russian) | DOI | MR

[13] Blondeau C., Nyberg K., “Perfect nonlinear functions and cryptography”, Finite Fields Appl., 32 (2015), 120–147 | DOI | MR | Zbl

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

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

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

[17] Budaghyan L., Construction and Analysis of Cryptographic Functions, Springer International Publishing, 2014, 168 pp. | MR | Zbl

[18] Carlet C., “Vectorial Boolean functions for cryptography”, Ch. 9 of the monograph, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, 2010, 398–472 | DOI

[19] Hou X.-D., “Affinity of permutations of $\mathrm F_2^n$”, Discr. Appl. Math., 154, Special Issue: Coding and Cryptography Archive (2006), 313–325 | DOI | Zbl

[20] Browning K. A., Dillon J. F., McQuistan M. T., Wolfe A. J., “An APN permutation in dimension six”, 9-th Intern. Conf. Finite Fields and Their Applications Fq'09, Contemporary Math., 518, AMS, 2010, 33–42 | DOI | MR | Zbl

[21] Canteaut A., Duval S., Perrin L., “A generalisation of Dillon's APN permutation with the best known differential and linear properties for all fields of size $2^{4k+2}$”, IEEE Trans. Inform. Theory, 63 (2016), 7575–7591 | DOI | MR

[22] Perrin L., Udovenko A., Biryukov A., “Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem”, CRYPTO 2016, Part II, LNCS, 9815, 2016, 93–122 | MR | Zbl

[23] Idrisova V., “On an algorithm generating 2-to-1 APN functions and its applications to ‘the big APN problem’ ”, Cryptography and Communications, 2018, 1–19

[24] Gorodilova A. A., “Characterization of almost perfect nonlinear functions in terms of subfunctions”, Discr. Math. Appl., 26:4 (2016), 193–202 | DOI | MR | Zbl