Abstract
While the classical differential uniformity (c = 1) is invariant under the CCZ-equivalence, the newly defined (Ellingsen et al., IEEE Trans. Inf. Theory 66(9), 5781–5789, 2020) concept of c-differential uniformity (cDU), as was observed in Hasan et al. (2020), is not invariant under EA or CCZ-equivalence, for c≠ 1. In this paper, we find an intriguing behavior of the inverse function, namely, that adding some appropriate linearized monomials increases the c-differential uniformity significantly, for some c. For example, adding the linearized monomial \(x^{2^{d}}\) to \(x^{2^{n}-2}\), where d is the largest nontrivial divisor of n, increases the mentioned c-differential uniformity from 2 or 3 (for c≠ 0,1) to ≥ 2d + 2, which in the case of the inverse function (as used in the AES) on \({\mathbb {F}}_{2^{8}}\) is a significant value of 18. We consider the case of perturbations via more general linearized polynomials and give bounds for the cDU based upon character sums. We further provide some computational results on other known Sboxes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bartoli, D., Calderini, M.: On construction and (non)existence of c-(almost) perfect nonlinear functions. arXiv:2008.03953 (2020)
Bartoli, D., Timpanella, M.: On a generalization of planar functions. J. Algebr. Comb. 52, 187–213 (2020)
Berlekamp, E. R., Rumsey, H., Solomon, G.: On the solutions of algebraic equations over finite fields. Inf. Control. 10, 553–564 (1967)
Bluher, A. W.: On xq+ 1+ax+b. Finite Fields Appl. 10(3), 285–305 (2004)
Borisov, N., Chew, M., Johnson, R., Wagner, D.: Multiplicative differentials. In: Daemen, J., Rijmen, V (eds.) Fast Software Encryption, FSE 2002, LNCS 2365, pp 17–33. Springer, Berlin (2002)
Bourbaki, N.: Elements of Mathematics, Algebra II (translated by P. M. Cohn and J. Howie). Springer, Berlin (1990)
Budaghyan, L.: Construction and Analysis of Cryptographic Functions. Springer, Berlin (2014)
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models, pp. 257–397. Cambridge Univ. Press, Cambridge (2010)
Carlet, C.: Vectorial boolean functions for cryptography. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models, pp 398–472. Cambridge Univ. Press, Cambridge (2010)
Cusick, T.W., Stănică, P.: Cryptographic Boolean Functions and Applications, 2nd edn. Academic Press, San Diego (2017)
Daemen, J., Rijmen, V.: AES Proposal: Rijndael. https://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf
Ellingsen, P., Felke, P., Riera, C., Stănică, P., Tkachenko, A.: C-differentials, multiplicative uniformity and (almost) perfect c-nonlinearity. IEEE Trans. Inf. Theory 66(9), 5781–5789 (2020)
Hasan, S.U., Pal, M., Riera, C., Stănică, P.: On the c-differential uniformity of certain maps over finite fields. Des. Codes Cryptogr. https://doi.org/10.1007/s10623-020-00812-0 (2020)
Helleseth, T., Kholosha, A.: On the equation x2ℓ+ 1 + x + a = 0 over GF(2k). Finite Fields Appl. 14, 159–176 (2008)
Li, K., Qu, L., Sun, B., Li, C.: New results about the boomerang uniformity of permutation polynomials. IEEE Trans. Inf. Theory 65(11), 7542–7553 (2019)
Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn., vol. 20. Cambridge Univ. Press, Cambridge (1997). Encycl. Math Appl.
Mesnager, S.: Bent Functions: Fundamentals and Results. Springer, Berlin (2016)
Mills, D.: On the evaluation of Weil Sums of Dembowski–Ostrom polynomials. J. Number Theory 92(1), 87–98 (2002)
Mesnager, S., Riera, C., Stănică, P., Zhou, Z., Yan, H.: Investigations on c-(almost) perfect nonlinear functions manuscript (2020)
Stănică, P.: Investigations on c-boomerang uniformity and perfect nonlinearity. arXiv:2004.11859 (2020)
Stănică, P.: Using double Weil sums in finding the Boomerang and the c-Boomerang Connectivity Table for monomial functions on finite fields. arXiv:2007.09553 (2020)
Tokareva, N.: Bent Functions, Results and Applications to Cryptography. Academic Press, San Diego (2015)
Zha, Z., Hu, L.: Some classes of power functions with low c-differential uniformity over finite fields. https://arxiv.org/pdf/2008.12183v1.pdf
Acknowledgments
The authors would like to express their sincere appreciation for the reviewers’ careful reading, beneficial comments and suggestions, and to the editors for the prompt handling of our paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Stănică, P., Geary, A. The c-differential behavior of the inverse function under the EA-equivalence. Cryptogr. Commun. 13, 295–306 (2021). https://doi.org/10.1007/s12095-020-00466-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-020-00466-8
Keywords
- Boolean and p-ary functions
- c-differentials
- Differential uniformity
- Perfect and almost perfect c-nonlinearity
- Perturbations
- Characters