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

Lei Lei; Wenli Ren; Cuiling Fan

doi:10.3934/amc.2020080

Article Contents

2021, Volume 15, Issue 3: 525-537. Doi: 10.3934/amc.2020080

This issue Previous Article Binary codes from

$ m $

-ary

$ n $

-cubes

$ Q^m_n $

Next Article Internal state recovery of Espresso stream cipher using conditional sampling resistance and TMDTO attack

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

1.
School of Mathematics, Southwest Jiaotong University, Chengdu, 610031, China
2.
State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China
3.
College of Mathematical sciences, Dezhou University, Dezhou, 253023, China

Corresponding author: Cuiling Fan
Corresponding author: Cuiling Fan

Received: September 30, 2019

Revised: December 31, 2019

Early access: April 2020

Published: August 2021

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

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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\}$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

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