Invariants for EA- and CCZ-equivalence of APN and AB functions
Tóm tắt
An (n,m)-function is a mapping from
${\mathbb {F}_{2}^{n}}$
to
${\mathbb {F}_{2}^{m}}$
. Such functions have numerous applications across mathematics and computer science, and in particular are used as building blocks of block ciphers in symmetric cryptography. The classes of APN and AB functions have been identified as cryptographically optimal with respect to the resistance against two of the most powerful known cryptanalytic attacks, namely differential and linear cryptanalysis. The classes of APN and AB functions are directly related to optimal objects in many other branches of mathematics, and have been a subject of intense study since at least the early 90’s. Finding new constructions of these functions is hard; one of the most significant practical issues is that any tentatively new function must be proven inequivalent to all the known ones. Testing equivalence can be significantly simplified by computing invariants, i.e. properties that are preserved by the respective equivalence relation. In this paper, we survey the known invariants for CCZ- and EA-equivalence, with a particular focus on their utility in distinguishing between inequivalent instances of APN and AB functions. We evaluate each invariant with respect to how easy it is to implement in practice, how efficiently it can be calculated on a computer, and how well it can distinguish between distinct EA- and CCZ-equivalence classes.
Tài liệu tham khảo
Encyclopedia of Boolean functions. http://web.archive.org/web/20080207010024/http://www.808multimedia.com/winnt/kernel.ht://boolean.h.uib.no/mediawiki/index.php/Main_Page
Beierle, C., Leander, G.: New instances of quadratic APN functions. arXiv:2009.07204 (2020)
Thomas, B., Cunsheng, D.: On almost perfect nonlinear permutations. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp 65–76. Springer (1993)
Beth, T., Jungnickel, D., Lenz, H.: Design Theory, vol. 1. Cambridge, Cambridge University Press (1999)
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)
Biryukov, A., De Canniere, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp 33–50. Springer (2003)
Bonnetain, X., Perrin, L., Tian, S.: Anomalies and vector space search: Tools for s-box analysis. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer (2019)
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user language. J. Symb. Comput. 24(3-4), 235–265 (1997)
Bracken, C., Byrne, E., Markin, N., McGuire, G.: A few more quadratic APN functions. Cryptogr. Commun. 3(1), 43–53 (2011)
Brinkmann, M., Leander, G.: On the classification of APN functions up to dimension five. Des. Codes Crypt. 49, 273–288 (2008)
Browning, K.: APN polynomials and related codes. Special Vol. J. Comb. Inf. Syst. Sci. 34, 135–159 (2009)
Browning, K.A., Dillon, J.F., McQuistan, M.T., Wolfe, A.J.: An APN permutation in dimension six. Finite Fields: Theory Appl. 518, 33–42 (2010)
Budaghyan, L., Calderini, M., Carlet, C., Coulter, R., Villa, I.: Generalized isotopic shift construction for APN functions Des. Codes Crypt. 89, 1–14 (2020)
Budaghyan, L., Calderini, M., Carlet, C., Coulter, R.S., Villa, I.: Constructing APN functions through isotopic shifts. IEEE Trans. Inf. Theory 66(8), 5299–5309 (2020)
Budaghyan, L., Carlet, C.: Classes of quadratic APN trinomials and hexanomials and related structures. IEEE Trans. Inf. Theory 54(5), 2354–2357 (2008)
Budaghyan, L., Carlet, C., Helleseth, T., Kaleyski, N.: On the distance between APN functions. IEEE Trans. Inf. Theory 66(9), 5742–5753 (2020)
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)
Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Finite Fields Their Appl 15(2), 150–159 (2009)
Budaghyan, L., Carlet, C., Leander, G.: On a construction of quadratic APN functions. In: 2009 IEEE Information Theory Workshop. pp 374–378 (2009)
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)
Budaghyan, L., Helleseth, T., Kaleyski, N.: A new family of APN quadrinomials. IEEE Trans. Inf. Theory 66(11), 7081–7087 (2020)
Budaghyan, L., Kazymyrov, O.: Verification of restricted ea-equivalence for vectorial boolean functions. In: International Workshop on the Arithmetic of Finite Fields, pp 108–118. Springer (2012)
Canteaut, A., Couvreur, A., Perrin, L.: Recovering or testing extended-affine equivalence. arXiv:2103.00078 (2021)
Canteaut, A., Perrin, L.: On CCZ-equivalence, extended-affine equivalence, and function twisting. Finite Fields Their Appl. 56, 209–246 (2019)
Carlet, C.: Boolean functions for cryptography and coding theory (2021)
Carlet, C., Charpin, P., Zinoviev, V.A.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Crypt. 15(2), 125–156 (1998)
Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 94, vol. 950, pp 356–365 (1994)
Colbourn, C.J., Dinitz, J.H.: Handbook of combinatorial designs. CRC press (2006)
Daemen, J., Rijmen, V.: AES proposal: Rijndael (1999)
Daemen, J., Rijmen, V.: The design of Rijndael, vol. 2. Springer, Berlin (2002)
Dempwolff, U.: Ccz equivalence of power functions. Des. Codes Crypt. 86(3), 665–692 (2018)
Dobbertin, H.: Almost perfect nonlinear power functions on GF(2n): the Niho case. Inf. Comput. 151(1), 57–72 (1999)
Dobbertin, H.: Almost perfect nonlinear power functions on GF(2n): the Welch case. IEEE Trans. Inf. Theory 45(4), 1271–1275 (1999)
Dobbertin, H.: Almost perfect nonlinear power functions on GF(2n): A new case for n divisible by 5. Int. Conf. Finite Fields Appl. 113–121 (2001)
Edel, Y.: Quadratic APN functions as subspaces of alternating bilinear forms. In: Proceedings of the Contact Forum Coding Theory and Cryptography III, vol. 2009, pp 11–24 (2011)
Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Adv. Math. Commun. 3(1), 59–81 (2009)
Edel, Y., Pott, A.: On the equivalence of nonlinear functions (2009)
Gold, R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.) IEEE Trans. Inf. Theory 14(1), 154–156 (1968)
Göloğlu, F., Pavlů, J.: On CCZ-inequivalence of some families of almost perfect nonlinear functions to permutations. Cryptogr. Commun. 1–15 (2021)
Janwa, H., Wilson, R.M: Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes. In: International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pp 180–194. Springer (1993)
Joux, A.: Algorithmic cryptanalysis. CRC press (2009)
Kaleyski, N.: Deciding ea-equivalence via invariants. In: The 11th International Conference on Sequences and Their Applications (SETA 2020) (2020)
Kalgin, K., Idrisova, V.: The classification of quadratic APN functions in 7 variables (2020)
Kasami, T.: The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes. Inf. Comput. 18(4), 369–394 (1971)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp 386–397. Springer (1993)
Nyberg, K.: Differentially uniform mappings for cryptography. Lect. Notes Comput. Sci 765, 55–64 (1994)
Nyberg, K., Knudsen, L.R.: Provable security against a differential attack. J. Cryptol. 8(1), 27–37 (1995)
Özbudak, F., Sınak, A., Yayla, O.: On verification of restricted extended affine equivalence of vectorial boolean functions. In: International Workshop on the Arithmetic of Finite Fields, pp 137–154. Springer (2014)
Perrin, L.: How to take a function apart with sboxu. The 5th International Workshop on Boolean Functions and their Applications (BFA 2020) (2020)
Sălăgean, A.: Discrete antiderivatives for functions over \(\mathbb {F}_{p}^{n}\). Des. Codes Crypt. 88(3), 471–486 (2020)
Sidelnikov, V.M.: On the mutual correlation of sequences. Soviet Math. Dokl. 12, 197–201 (1971)
Taniguchi, H.: On some quadratic APN functions. Des. Codes Crypt. 87, 1–11 (2019)
Yoshiara, S.: Equivalences of quadratic APN functions. J. Algebraic Comb. 35(3), 461–475 (2012)
Yoshiara, S.: Equivalences of power APN functions with power or quadratic APN functions. J. Algebraic Comb. 44(3), 561–585 (2016)
Yu, Y., Wang, M., Li, Y.: A matrix approach for constructing quadratic APN functions (2013)
Yuyin, Y., Wang, M., Li, Y.: A matrix approach for constructing quadratic APN functions. Des. Codes Cryptogr. 73(2), 587–600 (2014)
Zhou, Y., Pott, A.: A new family of semifields with 2 parameters. Adv. Math. 234, 43–60 (2013)