Skip to main content
Top
Published in: Designs, Codes and Cryptography 8/2023

06-05-2023

Differential spectrum of a class of APN power functions

Authors: Xiantong Tan, Haode Yan

Published in: Designs, Codes and Cryptography | Issue 8/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

APN power functions are fundamental objects as they are used in various theoretical and practical applications in cryptography, coding theory, combinatorial design, and related topics. Let p be an odd prime and n be a positive integer. Let \(F(x)=x^d\) be a power function over \({\mathbb {F}}_{p^n}\), where \(d=\frac{3p^n-1}{4}\) when \(p^n\equiv 3\pmod 8\) and \(d=\frac{p^n+1}{4}\) when \(p^n\equiv 7\pmod 8\). When \(p^n>7\), F is an APN function, which is proved by Helleseth et al. (IEEE Trans Inform Theory 45(2):475–485, 1999). In this paper, we study the differential spectrum of F. By investigating some system of equations, the number of solutions of certain system of equations and consequently the differential spectrum of F can be expressed by quadratic character sums over \({\mathbb {F}}_{p^n}\). By the theory of elliptic curves over finite fields, the differential spectrum of F can be investigated by a given p. It is the fourth infinite family of APN power functions with nontrivial differential spectrum.
Literature
1.
go back to reference Beth T., Ding C.S.: On almost perfect nonlinear permutations. In: Advances in Cryptology-EUROCRYPT-93. LNCS, pp. 65–76 (1994). Beth T., Ding C.S.: On almost perfect nonlinear permutations. In: Advances in Cryptology-EUROCRYPT-93. LNCS, pp. 65–76 (1994).
3.
go back to reference Blondeau C., Canteaut A., Charpin P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010).MathSciNetMATH Blondeau C., Canteaut A., Charpin P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010).MathSciNetMATH
4.
go back to reference Blondeau C., Canteaut A., Charpin P.: Differential properties of \(x \mapsto x^{2^t-1}\). IEEE Trans. Inf. Theory 57(12), 8127–8137 (2011).CrossRefMATH Blondeau C., Canteaut A., Charpin P.: Differential properties of \(x \mapsto x^{2^t-1}\). IEEE Trans. Inf. Theory 57(12), 8127–8137 (2011).CrossRefMATH
5.
go back to reference 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).MathSciNetCrossRefMATH 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).MathSciNetCrossRefMATH
6.
go back to reference 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).MathSciNetCrossRefMATH 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).MathSciNetCrossRefMATH
7.
go back to reference Budaghyan L., Carlet C., Helleseth T., Li N., Sun B.: On upper bounds for algebraic degrees of APN functions. IEEE Trans. Inf. Theory 64(6), 4399–4411 (2017).MathSciNetCrossRefMATH Budaghyan L., Carlet C., Helleseth T., Li N., Sun B.: On upper bounds for algebraic degrees of APN functions. IEEE Trans. Inf. Theory 64(6), 4399–4411 (2017).MathSciNetCrossRefMATH
8.
go back to reference Budaghyan L., Calderini C., Carlet R., Coulter R., Villa I.: Constructing APN functions through iostopic shift. IEEE Trans. Inf. Theory 66(8), 5299–5309 (2020).CrossRefMATH Budaghyan L., Calderini C., Carlet R., Coulter R., Villa I.: Constructing APN functions through iostopic shift. IEEE Trans. Inf. Theory 66(8), 5299–5309 (2020).CrossRefMATH
9.
10.
go back to reference 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).MATH 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).MATH
11.
go back to reference Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021).MATH Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021).MATH
12.
go back to reference Choi S.-T., Hong S., No J.-S., Chung H.: Differential spectrum of some power functions in odd prime characteristic. Finite Fields Appl. 21, 11–29 (2013).MathSciNetCrossRefMATH Choi S.-T., Hong S., No J.-S., Chung H.: Differential spectrum of some power functions in odd prime characteristic. Finite Fields Appl. 21, 11–29 (2013).MathSciNetCrossRefMATH
13.
14.
15.
go back to reference Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): the Welch case. IEEE Trans. Inf. Theory 45(4), 1271–1275 (1999).CrossRefMATH Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): the Welch case. IEEE Trans. Inf. Theory 45(4), 1271–1275 (1999).CrossRefMATH
16.
go back to reference Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): the Niho case. IEEE Trans. Inf. Theory 151(1–2), 57–72 (1999).MATH Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): the Niho case. IEEE Trans. Inf. Theory 151(1–2), 57–72 (1999).MATH
17.
go back to reference Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): a new case for \(n\) divisible by 5. In: Finite Fields and Applications, pp. 113–121. Augsburg. Springer, Berlin (2001). Dobbertin H.: Almost perfect nonlinear power functions on \(\mathbb{F} _{2^n}\): a new case for \(n\) divisible by 5. In: Finite Fields and Applications, pp. 113–121. Augsburg. Springer, Berlin (2001).
18.
go back to reference Dobbertin H., Helleseth T., Kumar P.V., Martinsen H.: Ternary m-sequences with three-valued cross-correlation function: new decimations of Welch and Niho type. IEEE Trans. Inf. Theory 47(4), 1473–1481 (2001).MathSciNetCrossRefMATH Dobbertin H., Helleseth T., Kumar P.V., Martinsen H.: Ternary m-sequences with three-valued cross-correlation function: new decimations of Welch and Niho type. IEEE Trans. Inf. Theory 47(4), 1473–1481 (2001).MathSciNetCrossRefMATH
19.
go back to reference Dobbertin H., Mills D., Muller E.N., Pott A., Willems W.: APN Functions in odd characteristic. Discret. Math. 267(1–3), 95–112 (2003).MathSciNetCrossRefMATH Dobbertin H., Mills D., Muller E.N., Pott A., Willems W.: APN Functions in odd characteristic. Discret. Math. 267(1–3), 95–112 (2003).MathSciNetCrossRefMATH
20.
go back to reference Helleseth T., Sandberg D.: Some power mappings with low differential uniformity. Appl. Algeb. Eng. Commun. Comput. 8(5), 363–370 (1997).MathSciNetCrossRefMATH Helleseth T., Sandberg D.: Some power mappings with low differential uniformity. Appl. Algeb. Eng. Commun. Comput. 8(5), 363–370 (1997).MathSciNetCrossRefMATH
21.
go back to reference Helleseth T., Rong C.M., Sandberg D.: New families of almost perfect nonlinear power mappings. IEEE Trans. Inf. Theory 45(2), 475–485 (1999).MathSciNetCrossRefMATH Helleseth T., Rong C.M., Sandberg D.: New families of almost perfect nonlinear power mappings. IEEE Trans. Inf. Theory 45(2), 475–485 (1999).MathSciNetCrossRefMATH
22.
go back to reference Jiang S., Li K.Q., Li Y.B., Qu L.J.: Differential spectrum of a class of power functions. J. Cryptol. Res. 9(3), 484–495 (2021). Jiang S., Li K.Q., Li Y.B., Qu L.J.: Differential spectrum of a class of power functions. J. Cryptol. Res. 9(3), 484–495 (2021).
23.
go back to reference Lei L., Ren W., Fan C.L.: The differential spectrum of a class of power functions over finite fields. Adv. Math. Commun. 15(3), 525–537 (2020).MathSciNetCrossRefMATH Lei L., Ren W., Fan C.L.: The differential spectrum of a class of power functions over finite fields. Adv. Math. Commun. 15(3), 525–537 (2020).MathSciNetCrossRefMATH
24.
go back to reference Li N., Wu Y.N., Zeng X.Y., Tang X.H.: On the differential spectrum and the APcN property of a class of power functions over finite fields. IEEE Trans. Inform. Theory 69(1), 582–597 (2023).MathSciNetCrossRef Li N., Wu Y.N., Zeng X.Y., Tang X.H.: On the differential spectrum and the APcN property of a class of power functions over finite fields. IEEE Trans. Inform. Theory 69(1), 582–597 (2023).MathSciNetCrossRef
25.
go back to reference Lidl R., Niederreite H.: Finite Fields, Encyclopedia of Mathematics and Its Applications, vol. 20. Cambridge University Press, Cambridge (1997). Lidl R., Niederreite H.: Finite Fields, Encyclopedia of Mathematics and Its Applications, vol. 20. Cambridge University Press, Cambridge (1997).
26.
go back to reference Man Y.Y., Xia Y.B., Li C.L., Helleseth T.: On the differential properties of the power mapping \(x^{p^m+2}\). Finite Fields Appl. 84, 102100 (2022).CrossRefMATH Man Y.Y., Xia Y.B., Li C.L., Helleseth T.: On the differential properties of the power mapping \(x^{p^m+2}\). Finite Fields Appl. 84, 102100 (2022).CrossRefMATH
27.
go back to reference Nyberg K.: Differentially uniform mappings for cryptography. In: Helleseth T. (ed.) Advances in cryptology-EUROCRYPT-93. Norway. 1993. LNCS, vol. 765, pp. 55–64. Springer, Berlin (1994). Nyberg K.: Differentially uniform mappings for cryptography. In: Helleseth T. (ed.) Advances in cryptology-EUROCRYPT-93. Norway. 1993. LNCS, vol. 765, pp. 55–64. Springer, Berlin (1994).
28.
30.
go back to reference Tian S.Z., Chen Y.: Differential Spectrums for a Class of Power Functions over \({\mathbb{F} }_{{p^{n}}}\). J. Syst. Sci. Math. Sci. 37(5), 1351–1367 (2017). Tian S.Z., Chen Y.: Differential Spectrums for a Class of Power Functions over \({\mathbb{F} }_{{p^{n}}}\). J. Syst. Sci. Math. Sci. 37(5), 1351–1367 (2017).
31.
go back to reference Xia Y.B., Zhang X.L., Li C.L., Helleseth T.: The differential spectrum of a ternary power mapping. Finite Fields Appl. 64, 101660 (2020).MathSciNetCrossRefMATH Xia Y.B., Zhang X.L., Li C.L., Helleseth T.: The differential spectrum of a ternary power mapping. Finite Fields Appl. 64, 101660 (2020).MathSciNetCrossRefMATH
32.
go back to reference Xiong M.S., Yan H.D.: A note on the differential spectrum of a differentially 4-uniform power function. Finite Fields Appl. 48, 117–125 (2017).MathSciNetCrossRefMATH Xiong M.S., Yan H.D.: A note on the differential spectrum of a differentially 4-uniform power function. Finite Fields Appl. 48, 117–125 (2017).MathSciNetCrossRefMATH
33.
go back to reference Xiong M.S., Yan H.D., Yuan P.Z.: On a conjecture of differentially 8-uniform power functions. Des. Codes Cryptogr. 86(8), 1601–1621 (2018).MathSciNetCrossRefMATH Xiong M.S., Yan H.D., Yuan P.Z.: On a conjecture of differentially 8-uniform power functions. Des. Codes Cryptogr. 86(8), 1601–1621 (2018).MathSciNetCrossRefMATH
34.
go back to reference Yan H.D., Li C.J.: Differential spectra of a class of power permutations with characteristic 5. Des. Codes Cryptogr. 89(6), 1181–1191 (2021).MathSciNetCrossRefMATH Yan H.D., Li C.J.: Differential spectra of a class of power permutations with characteristic 5. Des. Codes Cryptogr. 89(6), 1181–1191 (2021).MathSciNetCrossRefMATH
35.
go back to reference Yan H.D., Li Z.: A note on the differential spectrum of a class of power mappings with Niho exponent. Cryptogr. Commun. 14(5), 1081–1089 (2022).MathSciNetCrossRefMATH Yan H.D., Li Z.: A note on the differential spectrum of a class of power mappings with Niho exponent. Cryptogr. Commun. 14(5), 1081–1089 (2022).MathSciNetCrossRefMATH
36.
go back to reference Yan H.D., Zhou Z.C., Weng J., Wen J.M., Helleseth T., Wang Q.: Differential spectrum of Kasami power permutations over odd characteristic finite fields. IEEE Trans. Inf. Theory 65(10), 6819–6826 (2019).MathSciNetCrossRefMATH Yan H.D., Zhou Z.C., Weng J., Wen J.M., Helleseth T., Wang Q.: Differential spectrum of Kasami power permutations over odd characteristic finite fields. IEEE Trans. Inf. Theory 65(10), 6819–6826 (2019).MathSciNetCrossRefMATH
37.
go back to reference Yan H.D., Xia Y.B., Li C.L., Helleseth T., Luo J.Q.: The differential spectrum of the power mapping \(x^{p^n-3}\). IEEE Trans. Inform. Theory 68(8), 5535–5547 (2022).MathSciNetCrossRefMATH Yan H.D., Xia Y.B., Li C.L., Helleseth T., Luo J.Q.: The differential spectrum of the power mapping \(x^{p^n-3}\). IEEE Trans. Inform. Theory 68(8), 5535–5547 (2022).MathSciNetCrossRefMATH
38.
go back to reference Yan H.D., Mesnager S., Tan X.T.: On the differential spectrum of a class of APN power functions over odd characteristic finite fields and their \(c\)-differential properties. arXiv:2210.10390. Yan H.D., Mesnager S., Tan X.T.: On the differential spectrum of a class of APN power functions over odd characteristic finite fields and their \(c\)-differential properties. arXiv:​2210.​10390.
39.
go back to reference Yan H.D., Mesnager S., Tan X.T.: Two low differentially uniform power permutations over odd characteristic finite fields: APN and differentially 4-uniform functions. arXiv:2210.09822. Yan H.D., Mesnager S., Tan X.T.: Two low differentially uniform power permutations over odd characteristic finite fields: APN and differentially 4-uniform functions. arXiv:​2210.​09822.
41.
go back to reference Zha Z.B., Wang X.Q.: Power functions with low uniformity on odd characteristic finite fields. Sci. China Math. 53(8), 1931–1940 (2010).MathSciNetCrossRefMATH Zha Z.B., Wang X.Q.: Power functions with low uniformity on odd characteristic finite fields. Sci. China Math. 53(8), 1931–1940 (2010).MathSciNetCrossRefMATH
42.
go back to reference Zha Z.B., Wang X.Q.: Almost perfect nonlinear power functions in odd characteristic. IEEE Trans. Inf. Theory 57(7), 4826–4832 (2011).MathSciNetCrossRefMATH Zha Z.B., Wang X.Q.: Almost perfect nonlinear power functions in odd characteristic. IEEE Trans. Inf. Theory 57(7), 4826–4832 (2011).MathSciNetCrossRefMATH
43.
go back to reference Zha Z.B., Kyureghyan G.M., Wang X.Q.: Perfect nonlinear binomials and their semifields. Finite Fields Appl. 15(2), 125–133 (2009).MathSciNetCrossRefMATH Zha Z.B., Kyureghyan G.M., Wang X.Q.: Perfect nonlinear binomials and their semifields. Finite Fields Appl. 15(2), 125–133 (2009).MathSciNetCrossRefMATH
Metadata
Title
Differential spectrum of a class of APN power functions
Authors
Xiantong Tan
Haode Yan
Publication date
06-05-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 8/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01218-4

Other articles of this Issue 8/2023

Designs, Codes and Cryptography 8/2023 Go to the issue

Premium Partner