zbMATH — the first resource for mathematics

Cryptanalysis of a theorem: decomposing the only known solution to the big APN problem. (English) Zbl 1391.94789
Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53007-8/pbk; 978-3-662-53008-5/ebook). Lecture Notes in Computer Science 9815, 93-122 (2016).
Summary: The existence of almost perfect non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009.
In this paper, we apply methods intended to reverse-engineer S-boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over \(GF(2^3)\). More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are 2\(n\)-bit mappings with two CCZ-equivalent representations: one is a quadratic non-bijective function and one is a degree \(n+1\) permutation. We show that these structures always have differential uniformity at most 4 when \(n\) is odd. A particular case of this structure is actually a 3-round Feistel network with similar differential and linear properties. These functions also share an excellent non-linearity for \(n=3,5,7\).
Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6-bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive.
For the entire collection see [Zbl 1344.94002].

94A60 Cryptography
Full Text: DOI
[1] Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991) · Zbl 0729.68017 · doi:10.1007/BF00630563
[2] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) · Zbl 0951.94519 · doi:10.1007/3-540-48285-7_33
[3] Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002) · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4
[4] Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994) · Zbl 0951.94510 · doi:10.1007/3-540-48285-7_6
[5] Browning, K., Dillon, J., McQuistan, M., Wolfe, A.: An APN permutation in dimension six. Finite Fields Theory Appl. 518, 33–42 (2010) · Zbl 1206.94026 · doi:10.1090/conm/518/10194
[6] Bilgin, B., Bogdanov, A., Knežević, M., Mendel, F., Wang, Q.: Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 142–158. Springer, Heidelberg (2013) · Zbl 1353.94038 · doi:10.1007/978-3-642-40349-1_9
[7] Biryukov, A., Perrin, L., Udovenko, A.: Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 372–402. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49890-3_15 · Zbl 1385.94016 · doi:10.1007/978-3-662-49890-3_15
[8] Biryukov, A., Perrin, L.: On reverse-engineering S-Boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 116–140. Springer, Berlin Heidelberg (2015) · Zbl 1347.94019 · doi:10.1007/978-3-662-47989-6_6
[9] Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Heidelberg (2012) · Zbl 1292.94031 · doi:10.1007/978-3-642-34961-4_16
[10] Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394–405. Springer, Heidelberg (2001) · Zbl 0981.94015
[11] Biryukov, A., De Cannière, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: linear and affine equivalence algorithms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 33–50. Springer, Heidelberg (2003) · Zbl 1038.94521 · doi:10.1007/3-540-39200-9_3
[12] Developers, T.S.: SageMath, the Sage Mathematics Software System (Version 7.1) (2016). http://www.sagemath.org
[13] Perrin, L., Udovenko, A., Biryukov, A.: Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version). Cryptology ePrint Archive, Report 2016/539 (2016). http://eprint.iacr.org/ · Zbl 1391.94789
[14] Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Crypt. 15(2), 125–156 (1998) · Zbl 0938.94011 · doi:10.1023/A:1008344232130
[15] Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields Appl. 32, 120–147 (2015). Special Issue: Second Decade of FFA · Zbl 1372.94413 · doi:10.1016/j.ffa.2014.10.007
[16] 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 · doi:10.1109/TIT.2005.864481
[17] Daemen, J., Govaerts, R., Vandewalle, J.: A new approach to block cipher design. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 18–32. Springer, Heidelberg (1994) · Zbl 0943.94518 · doi:10.1007/3-540-58108-1_2
[18] Bracken, C., Leander, G.: A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree. Finite Fields Appl. 16(4), 231–242 (2010) · Zbl 1194.94182 · doi:10.1016/j.ffa.2010.03.001
[19] Bracken, C., Tan, C.H., Tan, Y.: Binomial differentially 4 uniform permutations with high nonlinearity. Finite Fields Appl. 18(3), 537–546 (2012) · Zbl 1267.94043 · doi:10.1016/j.ffa.2011.11.006
[20] Li, Y., Wang, M.: Constructing differentially 4-uniform permutations over GF( \[ 2^{2m} \] ) from quadratic APN permutations over GF( \[ 2^{2m+1} \] ). Des. Codes Crypt. 72(2), 249–264 (2014) · Zbl 1319.94077 · doi:10.1007/s10623-012-9760-9
[21] Kyureghyan, G.M., Suder, V.: On inverses of APN exponents. In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1207–1211. IEEE (2012) · doi:10.1109/ISIT.2012.6283047
[22] Carlet, C.: Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions. Des. Codes Crypt. 59(1), 89–109 (2011) · Zbl 1229.94041 · doi:10.1007/s10623-010-9468-7
[23] Li, Y., Wang, M.: Constructing S-Boxes for lightweight cryptography with Feistel structure. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 127–146. Springer, Heidelberg (2014) · Zbl 1375.94144
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.