A matrix approach for constructing quadratic APN functions. (English) Zbl 1320.11122
Summary: A one to one correspondence is given between quadratic homogeneous APN functions and a special kind of matrices which we call as QAM’s. By modifying the elements of a known QAM, new quadratic APN functions can be constructed. Based on the nice mathematical structures of the QAM’s, an efficient algorithm for constructing quadratic APN functions is proposed. On \(\mathbb F_{2^7}\), we have found 471 new CCZ-inequivalent quadratic APN functions, which is 20 times more than the number of the previously known ones. Before this paper, It is only found 23 classes of CCZ-inequivalent APN functions on \(\mathbb F_{2^8}\). With the method of this paper, we have found 2,252 new CCZ-inequivalent quadratic APN functions, and this number is still increasing.
MSC:
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 94A60 | Cryptography |
| 06E30 | Boolean functions |
References:
| [1] | Beth T., Ding C.: On almost perfect nonlinear permutations. In: Advances in Cryptology—EUROCRYPT’93. LNCS, vol. 765, pp. 65-76. Springer, New York (1994). · Zbl 0951.94524 |
| [2] | Bracken C., Byrne E., Markin N., McGuire G.: New families of quadratic almost perfect nonlinear trinomials and multinomials. Finite Fields Appl. 14(3), 703-714 (2008). · Zbl 1153.11058 |
| [3] | Bracken C., Byrne E., Markin N., McGuire G.: A few more quadratic APN functions. Cryptogr. Commun. 3(3), 43-53 (2011). · Zbl 1282.11162 |
| [4] | Browning K., Dillon J.F., McQuistan M.: APN polynomials and related codes. J. Comb. Inf. Syst. Sci., 34(1-4), 135-159, (2009) (Special volume honoring the 75-th birthday of Prof. D.K.Ray-Chaudhuri). · Zbl 1269.94035 |
| [5] | Browning K., Dillon J.F., McQuistan M., Wolfe A.J.: An APN permutation in dimension six. Contemaray Math. 58, 33-42 (2010). · Zbl 1206.94026 |
| [6] | Budaghyan L., Carlet C., Pott A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inf. Theory 52(3), 1141-1152 (2006). · Zbl 1177.94136 |
| [7] | Budaghyan L., Carlet C.: Classes of quadratic APN trinomials and hexanomials and related structures. IEEE Trans. Inf. Theory 54(5), 2354-2357 (2008). · Zbl 1177.94134 |
| [8] | Budaghyan L, Carlet C., Leander G.: Constructing new APN functions from known ones. Finite Fields Appl. 15(2), 150-159 (2009). · Zbl 1184.94228 |
| [9] | Budaghyan L., Carlet C., Leander G.: Two classes of quadratic APN binomials inequivalent to power functions. IEEE Trans. Inf. Theory 54(9), 4218-4229 (2008). · Zbl 1177.94135 |
| [10] | Carlet C.: Vectorial Boolean functions for cryptography, In: Crama Y., Hammer P. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 398-469. Cambridge University Press, Cambridge. http://www.math.univ-paris13.fr/ carlet/pubs.html (2014). Accessed 25 Aug 2013. · Zbl 1209.94036 |
| [11] | Carlet C., Charpin P., Zinoviev V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125-156 (1998). · Zbl 0938.94011 |
| [12] | Daemen J., Rijmen V.: The Design of Rijndael. Springer (2002). · Zbl 1065.94005 |
| [13] | Dillon J.F.: APN polynomials: an update, Fq9, In: The 9th International Conference on Finite Fields and Their Applications, Dublin (2009). |
| [14] | Edel Y.: Geoemetric and combinatorial aspects of APN functions. In: Contact Forum: Coding Theory and Cryptography III, Brussels. http://cage.ugent.be/ ls/website2009/abstracts/slidesyvesedel.pdf (2009). Accessed 20 Aug 2013. |
| [15] | Edel Y.: Quadratic APN functions as subspaces of alternating bilinear forms. In: Proceedings of the Contact Forum Coding Theory and Cryptography III, Belgium 2009, pp. 11-24 (2011). |
| [16] | Edel Y., Pott A.: A new almost perfect nonlinear function which is not quadratic. Adv. Math. Commun. 3(1), 59-81 (2009). · Zbl 1231.11140 |
| [17] | Edel Y., Kyureghyan G., Pott A.: A new APN function which is not equivalent to a power mapping. IEEE Trans. Inf. Theory 52(2), 744-747 (2006). · Zbl 1246.11185 |
| [18] | Dempwolff U., Edel Y.: Dimensional dual hyperovals and APN functions with translation group. J. Algebr. Comb. 39, 457-496. http://link.springer.com/article/10.1007 (2014). · Zbl 1292.05068 |
| [19] | Edel Y.: On quadratic APN functions and dimensional dual hyperovals. Des. Codes Cryptogr. 57(1), 35-44 (2010). · Zbl 1198.51003 |
| [20] | Gold R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Trans. Inf. Theory 14(1), 154-156 (1968). · Zbl 0228.62040 |
| [21] | Lidl R., Niederreiter H.: Finite Fields, pp. 58. Cambridge University Press, Cambridge (1983). · Zbl 0554.12010 |
| [22] | Ling S., Qu L.J.: A note on linearized polynomials and the dimension of their kernels. Finite Fields Appl. 18(1), 56-62 (2012). · Zbl 1273.11171 |
| [23] | Nyberg K., Knudsen L.R.: Provable security against differential cryptanalysis. In: CRYPTO 92. LCNS, vol. 740, pp. 566-574. Springer, New York (1993). · Zbl 0824.68037 |
| [24] | Yoshiara S.: Equivalences of quadratic APN functions. J. Algebr. Comb. 35(3), 461-475 (2012). · Zbl 1377.11123 |
| [25] | Yu Y., Wang M., Li Y.: A matrix approach for constructing quadratic APN functions. Cryptology ePrint Archive. Report (2013/2007). · Zbl 1320.11122 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
