×

zbMATH — the first resource for mathematics

Nonlinear functions in abelian groups and relative difference sets. (English) Zbl 1035.05023
This paper shows that the main results on nonlinear functions on finite fields can be generalized to abelian groups using the discrete Fourier tranform. The paper is a very interesting survey on (generalisations of) relative difference sets and nonlinear functions introducing new points of view.
Let \(K\) and \(N\) be abelian (additive) groups with \(| K| =m\), \(| N| =n\) and \(f:K\to N\) be a function. Let \(D_f=\{\langle g,f(g)\rangle \mid g\in K\}\subset G=K\times N\). Call a function \(f\) perfect nonlinear if \(\delta_f(a,b)=| \{g\in K\mid f(g+a)-f(g)=b\}| \) is equal to \(m/n\) for all \(a\in K\setminus\{0\}\) and \(b\in N\). Now \(D_f\) is a splitting \((m,n,m,m/n)\)-DS in \(G\) relative to \(\{0\}\times N\) if and only if \(f\) is perfect nonlinear. This suggest to use the discrete Fourier transform to study more general sets \(D_f\). A key of the paper is the following definition: a function \(f:K\to N\) is an almost perfect nonlinear function if \(\sum_{a,b}[\delta_f(a,b)]^2\leq\sum_{a,b}[\delta_g(a,b)]^2\) for all functions \(g:K\to N\).
Too many definitions and notations are necessary to go here into detail; we can only note that using this new point of view many proofs are more transparent and connections with relative difference sets become apparent.

MSC:
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
20K99 Abelian groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arasu, K.T.; Dillon, J.F.; Jungnickel, D.; Pott, A., The solution of the Waterloo problem, J. combin. theory ser. A, 71, 316-331, (1995) · Zbl 0833.05008
[2] Arasu, K.T.; Dillon, J.F.; Leung, K.H.; Ma, S.L., Cyclic relative difference sets with classical parameters, J. combin. theory ser. A, 94, 118-126, (2001) · Zbl 0980.05016
[3] Arasu, K.T.; Jungnickel, D.; Ma, S.L.; Pott, A., Relative difference sets with n=2, Discrete math., 147, 1-17, (1995) · Zbl 0842.05009
[4] T. Beth, D. Jungnickel, H. Lenz, Design Theory, Vol. 1, 2nd Edition, Cambridge University Press, Cambridge, 1999. · Zbl 0945.05005
[5] Beth, T.; Jungnickel, D.; Lenz, H., Design theory, (1999), Cambridge University Press Cambridge
[6] A. Blokhuis, D. Jungnickel, B. Schmidt, Proof of the prime power conjecture for projective planes of order n with abelian collineation groups of order n2, Proc. Amer. Math. Soc. 130 (2002), pp. 1473-1476 (electronic). · Zbl 1004.51012
[7] Canteaut, A.; Charpin, P.; Dobbertin, H., Binary m-sequences with three-valued crosscorrelationa proof of Welch’s conjecture , IEEE trans. inform. theory, 46, 4-8, (2000) · Zbl 1003.94519
[8] Chabaud, F.; Vaudenay, S., Links between differential and linear cryptanalysis, (), 356-365 · Zbl 0879.94023
[9] Coulter, R.S.; Mathews, R.W., Planar functions and planes of lenz – barlotti class II, Des. codes cryptogr., 10, 167-184, (1997) · Zbl 0872.51007
[10] Davis, J.A.; Jedwab, J., A unifying construction for difference sets, J. combin. theory ser. A, 80, 13-78, (1997) · Zbl 0884.05019
[11] Davis, J.A.; Jedwab, J.; Mowbray, M., New families of semi-regular relative difference sets, Des. codes cryptogr., 13, 131-146, (1998) · Zbl 0888.05008
[12] Dembowski, P.; Ostrom, T., Planes of order n with collineation groups of order n2, Math. Z., 103, 239-258, (1968) · Zbl 0163.42402
[13] Dillon, J.F., Multiplicative difference sets via additive characters, Des. codes, cryptogr., 17, 225-235, (1999) · Zbl 0944.05012
[14] J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, Finite Fields Appl. (2003), to appear. · Zbl 1043.05024
[15] Dobbertin, H., One-to-one highly nonlinear power functions on GF(2n), Appl. algebra eng. commun. comput., 9, 139-152, (1998) · Zbl 0924.94026
[16] Dobbertin, H., Almost perfect nonlinear power functions on GF(2n)the niho case , Inform. comput., 151, 57-72, (1999) · Zbl 1072.94513
[17] Dobbertin, H., Almost perfect nonlinear power functions on GF(2n)the welch case , IEEE trans. inform. theory, 45, 1271-1275, (1999) · Zbl 0957.94021
[18] Dobbertin, H., Kasami power functions, permutation polynomials and cyclic difference sets, (), 133-158 · Zbl 0946.05010
[19] Dobbertin, H., Almost perfect nonlinear power functions on GF(2n): a new case for n divisible by 5, (), 113-121 · Zbl 1010.94550
[20] Dobbertin, H.; Mills, D.; Müller, E.N.; Pott, A.; Willems, W., APN functions in odd characteristic, Discrete appl. math., 267, 95-112, (2003) · Zbl 1028.11076
[21] Elliott, J.E.H.; Butson, A.T., Relative difference sets, Illinois J. math., 10, 517-531, (1966) · Zbl 0145.01503
[22] Evans, R.; Hollmann, H.D.L.; Krattenthaler, C.; Xiang, Q., Gauss sums, Jacobi sums, and p-ranks of cyclic difference sets, J. combin. theory A, 87, 74-119, (1999) · Zbl 0943.05021
[23] Ganley, M.J., On a paper of P. Dembowski and T.G. ostromplanes of order n with collineation groups of order n2 (math. Z. 103 (1968) 239-258) , Arch. math. (basel), 27, 93-98, (1976)
[24] Gordon, B.; Mills, W.H.; Welch, L.R., Some new difference sets, Canad. J. math., 14, 614-625, (1962) · Zbl 0111.24201
[25] T. Helleseth, P.V. Kumar, Sequences with low correlation, in: Handbook of Coding Theory, Vol. I, II, North-Holland, Amsterdam, 1998, pp. 1065-1138.
[26] Helleseth, T.; Rong, C.; Sandberg, D., New families of almost perfect nonlinear power mappings, IEEE trans. inform. theory, 45, 475-485, (1999) · Zbl 0960.11051
[27] Helleseth, T.; Sandberg, D., Some power mappings with low differential uniformity, Appl. algebra eng. commun. comput., 8, 363-370, (1997) · Zbl 0886.11067
[28] Hollmann, H.H.; Xiang, Q., A proof of the welch and niho conjectures on crosscorrelations of binary m-sequences, Finite fields appl., 7, 253-286, (2001) · Zbl 1027.94006
[29] Jungnickel, D., On a theorem of ganley, Graphs combin., 3, 141-143, (1987) · Zbl 0659.05028
[30] Jungnickel, D.; Pott, A., Perfect and almost perfect sequences, Discrete appl. math., 95, 331-359, (1999) · Zbl 0941.05013
[31] M. Kantor, W., Note on GMW designs, Electron. J. combin., 22, 63-69, (2001) · Zbl 0964.05015
[32] Maschietti, A., Difference sets and hyperovals, Des. codes cryptogr., 14, 89-98, (1998) · Zbl 0887.05010
[33] K. Nyberg, Perfect nonlinear S-boxes, in: Advances in Cryptology—EUROCRYPT’91, Brighton, 1991, Springer, Berlin, 1991, pp. 378-386. · Zbl 0766.94012
[34] Pott, A., Finite geometry and character theory, Lecture notes in mathematics, Vol. 1601, (1995), Springer Berlin, Heidelberg · Zbl 0818.05001
[35] Pott, A., A survey on relative difference sets, (), 195-232 · Zbl 0847.05018
[36] Sarwate, D.V.; Pursley, M.B., Crosscorrelation properties of pseudorandom and related sequences, Proc. IEEE, 68, 593-619, (1980)
[37] Schmidt, B., On (pa,pb,pa,pa−b)-relative difference sets, J. algebraic combin., 6, 279-297, (1997)
[38] V.V. Shorin, V.V. Jelezniakov, E.M. Gabidulin, Linear and differential cryptanalysis of Russian GOST, in: D. Augot, C. Carlet (Eds.), Workshop on Coding and Cryptography 2001, INRIA, 2001, pp. 467-476. · Zbl 0985.94035
[39] Sidel’nikov, V.M., On the mutual correlation of sequences, Soviet math. dokl., 12, 197-201, (1971) · Zbl 0241.94008
[40] Singer, J., A theorem in finite projective geometry and some applications to number theory, Trans. amer. math. soc., 43, 377-385, (1938) · JFM 64.0972.04
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.