Differentially 4-uniform bijections by permuting the inverse function.

*(English)*Zbl 1329.94079Summary: Block ciphers use substitution boxes (S-boxes) whose aim is to create confusion into the cryptosystems. Functions used as S-boxes should have low differential uniformity, high nonlinearity and algebraic degree larger than 3 (preferably strictly larger). They should be fastly computable; from this viewpoint, it is better when they are in even number of variables. In addition, the functions should be bijections in a substitution-permutation network. Almost perfect nonlinear (APN) functions have the lowest differential uniformity 2 and the existence of APN bijections over \(\mathbb {F}_{2^n}\) for even \(n\geq 8\) is a big open problem. In the present paper, we focus on constructing differentially 4-uniform bijections suitable for designing S-boxes for block ciphers. Based on the idea of permuting the inverse function, we design a construction providing a large number of differentially 4-uniform bijections with maximum algebraic degree and high nonlinearity. For every even \(n\geq 12\), we mathematically prove that the functions in a subclass of the constructed class are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first mathematical proof that the functions in an infinite class of differentially 4-uniform bijections are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. We also get a naive lower bound on the nonlinearity of our functions, which can be very high in some cases, and obtain improved lower bounds on the nonlinearity for three special subcases of functions which are extremely large.

##### MSC:

94A60 | Cryptography |

06E30 | Boolean functions |

11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |

##### Keywords:

block cipher; substitution box; differentially 4-uniform bijection; CCZ-equivalence; nonlinearity
PDF
BibTeX
XML
Cite

\textit{D. Tang} et al., Des. Codes Cryptography 77, No. 1, 117--141 (2015; Zbl 1329.94079)

Full Text:
DOI

##### References:

[1] | Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3-72 (1991). · Zbl 0729.68017 |

[2] | 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 |

[3] | Bracken C., Tan C., Tan Y.: Binomial differentially 4 uniform permutations with high nonlinearity. Finite Fields Appl. 18(3), 537-546 (2012). · Zbl 1267.94043 |

[4] | Browning K.A., Dillon J.F., McQuistan M.T., Wolfe A.J.: An APN permutation in dimension six. In: Post Proceedings of the 9th International Conference on Finite Fields and their Applications Fq’9. Contemp. Math. J. Am. Math. Soc. 518, 33-42 (2010). · Zbl 1206.94026 |

[5] | Budaghyan L., Carlet C., Pott A.: New classes of almost bent and almost perfect nonlinear functions. IEEE Trans. Inf. Theory 52(3), 1141-1152 (2006). · Zbl 1177.94136 |

[6] | Carlet C.: On known and new differentially uniform functions. In: Proceedings of the Australasian Conference on Information Security Privacy. Lecture Notes in Computer Science, vol. 6812, pp. 1-15. Springer, Berlin (2011). · Zbl 1279.94060 |

[7] | 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 |

[8] | Carlet C., Tang D., Tang X., Liao Q.: New construction of differentially 4-uniform bijections. To appear in Lecture Notes in Computer Science (2014). · Zbl 1347.94024 |

[9] | Knudsen L.: Truncated and higher order differentials. In: Proceedings of the Second International Workshop Fast Software Encryption. Lecture Notes in Computer Science, vol. 1008, pp. 196-211. Springer, Berlin (1995). · Zbl 0939.94556 |

[10] | MacWilliams F.J., Sloane N.J.: The theory of error-correcting codes. North Holland, Amsterdam (1977). · Zbl 0369.94008 |

[11] | Matsui M.: Linear cryptanalysis method for DES cipher. Advances in Cryptology-EUROCRYPT 1993. Lecture Notes in Computer Science, vol. 765, pp. 386-397. Springer, Berlin (1994). · Zbl 0951.94519 |

[12] | Nyberg K.: Differentially uniform mappings for cryptography. Advances in Cryptology-EUROCRYPT 1993. Lecture Notes in Computer Science, vol. 765, pp. 55-64. Springer, Berlin (1994). · Zbl 0951.94510 |

[13] | Shannon C.E.: Communication theory of secrecy systems. Bell Sys. Tech. J. 28, 656-715 (1949). · Zbl 1200.94005 |

[14] | Lachaud G., Wolfmann J.: The weights of the orthogonals of the extended quadratic binary Goppa codes. IEEE Trans. Inf. Theory 36(3), 686-692 (1990). · Zbl 0703.94011 |

[15] | Li Y., Wang M.: Constructing differentially 4-uniform permutations over \(GF(2^{2m})\) from quadratic APN permutations over \(GF(2^{2m+1})\). Des. Codes Cryptogr. 72, 249-264 (2012). doi:10.1007/s10623-012-9760-9. · Zbl 1319.94077 |

[16] | Qu L., Tan Y., Tan C., Li C.: Constructing differentially \(4\)-uniform permutations over \(\mathbb{F}_{2^{2k}}\) via the switching method. IEEE Trans. Inf. Theory 59(7), 4675-4686 (2013). · Zbl 1364.94565 |

[17] | Zha Z., Hu L., Sun S.: Constructing new differentially 4-uniform permutations from the inverse function. Finite Fields Appl. 25, 64-78 (2014). · Zbl 1305.94084 |

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.