Article Contents
Article Contents

# The differential spectrum of a class of power functions over finite fields

• Corresponding author: Cuiling Fan

The work of L. Lei and C. Fan was supported by the National Natural Science Foundation of China under Grant 11971395, and partially supported by National Cryptography Development Fund under Grant MMJJ20180103. The work of W. Ren was supported by Natural Science Foundation of Shandong Province under Grant ZR2018LA001

• Functions with good differential-uniformity properties have important applications in coding theory and sequence design in addition to the applications in cryptography. The differential spectrum of a cryptographic function is useful for estimating its resistance to some variants of differential cryptanalysis. The objective of this paper is to determine the differential spectrum of the power function $x^{p^{2k}-p^k+1}$ over $\mathbb F_{p^n}$, where $p$ is an odd prime, $n, k, e$ are integers with $\gcd(n,k) = e$ and $\frac{n}{e}$ being odd. In particular, when $n$ is odd and $e = 1$, our result includes a recent one (IEEE Trans. Inform. Theory 65(10): 6819-6826) as a special case.

Mathematics Subject Classification: Primary: 94A05; Secondary: 60G35.

 Citation:

• Table 1.  Some power functions $\Pi(x) = x^d$ over $\mathbb{F}_{p^n}$ with known differential spectrum

 $p$ $d$ condition $\Delta(\Pi)$ references 2 $2^s+1$ $\gcd(s,n)=2$ 4 [3] 2 $2^{2s}-2^s+1$ $\gcd(s,n)=2$ 4 [3] 2 $2^n-2$ $n$ even 4 [3] 2 $2^{2k}+2^k+1$ $n=4k$, $k$ odd 4 [3] 2 $2^{2k}+2^k+1$ $n=4k$ 4 [28] 2 $2^t-1$ $t=3,n-2$ 6 [4] 2 $2^t-1$ $t=(n-1)/2$,$(n+3)/2$, $n$ odd $6$ or $8$ [5] 2 $2^m+2^{(m+1)/2}+1$ $n=2m$, $m\geq5$ odd $8$ [29] 2 $2^{m+1}+3$ $n=2m$, $m\geq5$ odd $8$ [29] 3 $(3^m-3)/4$ $n$ odd $\leq 3$ [31] odd $(p^k+1)/2$ $e=\gcd(n,k)$ $(p^e-1)/2$or $p^e+1$} [10] odd $(p^n+1)/(p^m+1)$$+(p^n-1)/2$} $p \equiv 3 \; (\mathrm{mod}\; 4)$,$n$ odd, $m|n$} $(p^m+1)/2$ [10] odd $p^{2k}-p^k+1$ $n$ odd, $\gcd(n,k)=1$ $p+1$ [32] odd $p^{2k}-p^k+1$ $\gcd(n,k)=e$, $\frac{n}{e}$ odd $p^e+1$ This paper

Table 2.  Differential spectrum of some $\Pi(x) = x^{p^{2k}-p^k+1}$ over $\mathbb F_{p^n}$

 $p$ $n$ $k$ $e$ $\Pi(x)$ $\mathcal{S}=\omega_0,\omega_{p^e-1},\omega_{p^e},\omega_{p^e+1}$ 3 $5$ $2$ $1$ $x^{73}$ $\left\{ {{\rm{152,60,1,30}}} \right\}$ $3$ $6$ $2$ $2$ $x^{73}$ $\left\{ {{\rm{647,45,1,36}}} \right\}$ $3$ $9$ $3$ $3$ $x^{703}$ $\left\{ {{\rm{18953,378,1,351}}} \right\}$ $3$ $9$ $6$ $3$ $x^{530713}$ $\left\{ {{\rm{18953,378,1,351}}} \right\}$ $5$ $6$ $2$ $2$ $x^{601}$ $\left\{ {{\rm{14999,325,1,300}}} \right\}$
•  [1] T. P. Berger, A. Canteaut, P. Charpin and Y. Laigle-Chapuy, On almost perfect nonlinear functions over $F_{2^n}$, IEEE Trans. Inform. Theory, 52 (2006), 4160-4170.  doi: 10.1109/TIT.2006.880036. [2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563. [3] C. Blondeau, A. Canteaut and P. Charpin, Differential properties of power functions, Int. J. Inf. Coding Theory, 1 (2010), 149-170.  doi: 10.1504/IJICOT.2010.032132. [4] C. Blondeau, A. Canteaut and P. Charpin, Differential properties of $x \mapsto x^{2^t-1}$, IEEE Trans. Inform. Theory, 57 (2011), 8127-8137.  doi: 10.1109/TIT.2011.2169129. [5] C. Blondeau and L. Perrin, More differentially $6$-uniform power functions, Des. Codes Cryptogr., 73 (2014), 487-505.  doi: 10.1007/s10623-014-9948-2. [6] A. Canteaut and M. Videau, Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis, Advances in Cryptology - EUROCRYPT, Lecture Notes in Comput. Sci., Springer, Berlin, 2332 (2002), 518-533.  doi: 10.1007/3-540-46035-7_34. [7] C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156.  doi: 10.1023/A:1008344232130. [8] C. Carlet and C. S. Ding, Highly nonlinear mappings, J. Complexity, 20 (2004), 205-244.  doi: 10.1016/j.jco.2003.08.008. [9] C. Carlet, C. S. Ding and J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes, IEEE Trans. Inform. Theory, 51 (2005), 2089-2102.  doi: 10.1109/TIT.2005.847722. [10] S.-T. Choi, S. Hong, J.-S. No and H. Chung, Differential spectrum of some power functions in odd prime characteristic, Finite Fields Appl., 21 (2013), 11-29.  doi: 10.1016/j.ffa.2013.01.002. [11] R. S. Coulter and R. W. Matthews, Planar functions and planes of Lenz-Barlotti class II, Des. Codes Cryptogr., 10 (1997), 167-184.  doi: 10.1023/A:1008292303803. [12] N. T. Courtois and J. Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations, Advances in Cryptology - ASIACRYPT, Lecture Notes in Comput. Sci., Springer, Berlin, 2501 (2002), 267-287.  doi: 10.1007/3-540-36178-2_17. [13] C. S. Ding, M. J. Moisio and J. Yuan, Algebraic constructions of optimal frequency-hopping sequences, IEEE Trans. Inform. Theory, 53 (2007), 2606-2610.  doi: 10.1109/TIT.2007.899545. [14] C. S. Ding and J. Yuan, A family of skew Hadamard difference sets, J. Comb. Theory, Ser. A, 113 (2006), 1526-1535.  doi: 10.1016/j.jcta.2005.10.006. [15] H. Dobbertin, D. Mills, E. N. Muller and A. P. Willems, APN functions in odd characteristic, Discrete Math., 267 (2003), 95-112.  doi: 10.1016/S0012-365X(02)00606-4. [16] H. Dobbertin, Almost perfect nonlinear power functions on $GF(2^n)$: The Welch case, IEEE Trans. Inform. Theory, 45 (1999), 1271-1275.  doi: 10.1109/18.761283. [17] Y. Edel, G. Kyureghyan and A. Pott, A new APN functions which is not equivalent to a power mapping, IEEE Trans. Inform. Theory, 52 (2006), 744-747.  doi: 10.1109/TIT.2005.862128. [18] T. Helleseth, C. M. Rong and D. Sandberg, New families of almost perfect nonlinear power mapping, IEEE Trans. Inform. Theory, 45 (1999), 475-485.  doi: 10.1109/18.748997. [19] T. Helleseth and D. Sandberg, Some power mappings with low differential uniformity, Appl. Algebra Engrg. Comm. Comput., 8 (1997), 363-370.  doi: 10.1007/s002000050073. [20] T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X. [21] T. Jakobsen and L. R. Knudsen, The interpolation attack on block ciphers, Fast Software Encryption - FSE, Lecture Notes in Comput. Sci., Springer, Berlin, 1267 (1997), 28-40.  doi: 10.1007/BFb0052332. [22] P. V. Kumar and O. Moreno, Prime-phase sequences with periodic correlation properties better than binary sequences, IEEE Trans. Inform. Theory, 37 (1991), 603-616.  doi: 10.1109/18.79916. [23] R. Lidl and  H. Niederreiter,  Finite Fields, Second edition, Encyclopedia of Mathematics and its Applications, 20. Cambridge University Press, Cambridge, 1997. [24] S. X. Ma, H. L. Zhang, W. D. Jin and X. H. Niu, A new family of optimal ternary cyclic codes, IEICE Trans. Fund., E97 (2014), 690-693.  doi: 10.1587/transfun.E97.A.690. [25] G. J. Ness and T. Helleseth, A new family of ternary almost perfect nonlinear mappings, IEEE Trans. Inform. Theory, 53 (2007), 2581-2586.  doi: 10.1109/TIT.2007.899508. [26] A. Pott, Almost perfect and planar functions, Des. Codes Cryptogr., 78 (2016), 141-195.  doi: 10.1007/s10623-015-0151-x. [27] H. Trachtenberg, On the Cross-Correlation Functions of Maximal Linear Sequences, Ph. D. thesis, University of Southern California, 1970. [28] M. S. Xiong and H. D. Yan, A note on the differential spectrum of a differentially 4-uniform power function, Finite Fields Appl., 48 (2017), 117-125.  doi: 10.1016/j.ffa.2017.07.008. [29] M. S. Xiong, H. D. Yan and P. Z. Yuan, On a conjecture of differentially 8-uniform power functions, Des. Codes Cryptogr., 86 (2018), 1601-1621.  doi: 10.1007/s10623-017-0416-7. [30] G. K. Xu, X. W. Cao and S. D. Xu, Several classes of polynomials with low differential uniformity over finite fields of odd characteristic, Appl. Algebra Engrg. Comm. Comput., 27 (2016), 91-103.  doi: 10.1007/s00200-015-0272-5. [31] H. D. Yan and D. C. Han, A class of 3-uniform ternary power function and related codes, IEICE Trans. Fund., E102-A (2019), 849-853. [32] H. D. Yan, Z. C. Zhou, J. Weng, J. M. Wen, T. Helleseth and Q. Wang, Differencial spectrum of Kasami power permutation over odd characteristic finite fields, IEEE Trans. Inform. Theory, 65 (2019), 6819-6826.  doi: 10.1109/TIT.2019.2910070. [33] X. Y. Zeng, L. Hu, W. F. Jiang, Q. Yue and X. W. Cao, The weight distribution of a class of $p$-ary cyclic codes, Finite Fields Appl., 16 (2010), 56-73.  doi: 10.1016/j.ffa.2009.12.001. [34] Z. B. Zha and X. L. Wang, Almost perfect nonlinear power functions in odd characteristic, IEEE Trans. Inform. Theory, 57 (2011), 4826-4832.  doi: 10.1109/TIT.2011.2145130. [35] Z. B. Zha and X. L. Wang, Power functions with low uniformity on odd characteristic finite fields, Sci. China Math., 53 (2010), 1931-1940.  doi: 10.1007/s11425-010-3149-x. [36] Z. C. Zhou and C. S. Ding, A class of three-weight codes, Finite Fields Appl., 25 (2014), 79-93.  doi: 10.1016/j.ffa.2013.08.005.

Tables(2)