×

zbMATH — the first resource for mathematics

Highly nonlinear mappings. (English) Zbl 1053.94011
The paper is a survey on non-Boolean functions with optimal nonlinearity. It contains generalizations of well-known classical results as well as several new results. In section 2, the authors present two important measures for the nonlinearity of a function \(f:A\to B\): (1) \(N_f=\min_{l\in L} d(f,l)\), where \(L\) denotes the set of all affine functions from \((A,+)\) to \((B,+)\) and \(d(f,g)=| \{x\in A| f(x)\neq g(x)\}| \); (2) \(P_f=\max_{0\neq a\in A}\max_{b\in B} \text{Pr}(D_af(x)=b)\), where \(D_af(x)=f(x+a)-f(x)\) and \(\text{Pr}(E)\) denotes the probability of the occurence of the event \(E\). Section 3 is devoted to functions with perfect nonlinearity. A function \(f:A\to B\) is said to have perfect nonlinearity if \(P_f=1/| B| \). A function \(g:A\to B\) is balanced if the size of \(g^{_1}(b)\) is the same for all \(b\in B\). A function has perfect nonlinearity iff \(D_af\) is balanced for every \(a\in A^*\) (Theorem 5). Further, perfect nonlinear functions are stable under actions of the general affine groups (Theorems 6, 7). In Sections 3.2 and 3.3, the authors study connections between perfect nonlinearity and difference partitions and generalized Hadamard matrices. Section 3.4 contains a characterization of perfect nonlinear functions via the Fourier transform. In Section 3.5, methods are described for obtaining functions with perfect nonlinearity from known ones. Section 3.6 is devoted to the connections of perfect nonlinear functions and bent functions. Sections 4 and 5 contain a detailed treatment of binary and nonbinary functions with optimal nonlinearity. Finally, various constructions of functions with optimum nonlinearity are described in Section 6.

MSC:
94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
05B05 Combinatorial aspects of block designs
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ambrosimov, A.S., Properties of bent functions of q-valued logic over finite fields, Discrete math. appl., 4, 4, 341-350, (1994) · Zbl 0816.03010
[2] Arasu, K.T.; Jedwab, J.A.; Sehgal, S., New constructions of menon difference sets, J. combin. theory A, 64, 329-336, (1993) · Zbl 0795.05032
[3] T. Beth, C. Ding, On almost perfect nonlinear permutations, in: Advances in Cryptology—Eurocrypt’ 93, Lecture Notes in Computer Science, Vol. 765, Springer, New York, 1994, pp. 65-76. · Zbl 0951.94524
[4] T. Beth, D. Jungnickel, H. Lenz, Design Theory, Vol. 1, 2nd Edition, Cambridge University Press, Cambridge, 1999. · Zbl 0945.05004
[5] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. cryptology, 4, 1, 3-72, (1991) · Zbl 0729.68017
[6] Brock, B.W., Hermitian congruence and the existence and completion of generalized Hadamard matrices, J. combin. theory A, 49, 233-261, (1988) · Zbl 0667.05011
[7] Brock, B.W., A new construction of circulant \(GH(p\^{}\{2\}; Zp)\), Discrete math., 112, 249-252, (1993) · Zbl 0780.05009
[8] P. Camion, A. Canteaut, Construction of t-resilient functions over a finite alphabet, in: Advances in Cryptology, EUROCRYPT’96, Lecture Notes in Computer Sciences, Vol. 1070, Springer, Berlin, 1996, pp. 283-293. · Zbl 1304.94038
[9] Camion, P.; Canteaut, A., Generalization of siegenthaler inequality and schnorr – vaudenay multipermutations, (), 372-386 · Zbl 1329.94055
[10] A. Canteaut, C. Carlet, P. Charpin, C. Fontaine, Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions, in: Proceedings of Eurocrypt’00, Lecture Notes in Computer Science, Vol. 1807, Springer, Berlin, 2000, pp. 507-520. · Zbl 1082.94510
[11] Canteaut, A.; Charpin, P.; Dobbertin, H., Weight divisibility of cyclic codes, highly nonlinear functions on F_2^m, and cross correlation of maximum-length sequences, SIAM J. discrete math., 13, 1, 105-138, (2000) · Zbl 1010.94013
[12] C. Carlet, Two new classes of bent functions, in: Advances in Cryptology—Eurocrypt’93, Lecture Notes in Computer Sciences, Vol. 765, Springer, Heidelberg, 1994, pp. 77-101. · Zbl 0951.94542
[13] C. Carlet, A construction of bent functions, in: Finite Fields and Applications, London Mathematical Society Lecture Notes Series 233, Cambridge University Press, Cambridge, 1996, pp. 47-58. · Zbl 0871.94027
[14] C. Carlet, Recent results on bent functions, in: Proceedings of the International Conference on Combinatorics, Information Theory and Statistics, Portland, Maine, 1999, pp. 275-291.
[15] Carlet, C., On cryptographic propagation criteria for Boolean functions, Inform. and comput., 151, 32-56, (1999) · Zbl 1011.94012
[16] Carlet, C.; Dubuc, S., On generalized bent and q-ary perfect nonlinear functions, (), 81-94 · Zbl 1010.94549
[17] Carlet, C.; Guillot, P., An alternate characterization of the bentness of binary functions with uniqueness, J. combin. theory A, 76, 328-335, (1996)
[18] Carlet, C.; Guillot, P., A characterization of binary bent functions, Designs, codes and cryptography, 14, 130-140, (1998)
[19] C. Carlet, P. Guillot, A new characterization of Boolean functions, in: Proceedings of AAECC’13, Hawaii, Lecture Notes in Computer Science, Vol. 1719, Springer, 1999, pp. 94-103. · Zbl 0979.94040
[20] F. Chabaud, S. Vaudenay, Links between differential and linear cryptanalysis, in: Proceedings of EUROCRYPT’94, Advances in Cryptology, Lecture Notes in Computer Science, Vol. 950, Springer, Berlin, 1995, pp. 356-365. · Zbl 0879.94023
[21] Chen, Y.Q., On the existence of abelian Hadamard difference sets and a new family of difference sets, Finite fields appl., 3, 234-256, (1997) · Zbl 0907.05013
[22] Colbourn, C.J.; de Launey, W., Difference matrices, (), 287-297, (Chapter IV.11) · Zbl 0858.05022
[23] Coulter, R.S.; Matthews, R., Planar functions and plans of the lenz – barlotti class II, Designs, codes and cryptography, 10, 165-195, (1997)
[24] Cusick, T.W.; Ding, C.; Renvall, A., Stream ciphers and number theory, North-holland mathematical library, Vol. 55, (1998), North-Holland/Elsevier Amsterdam · Zbl 0930.11086
[25] Cusick, T.W.; Dobbertin, H., Some new 3-valued cross correlation functions of binary sequences, IEEE trans. inform. theory, 42, 1238-1240, (1996) · Zbl 0855.94012
[26] Davis, J.A., Almost difference sets and reversible difference sets, Arch. math., 59, 595-602, (1992) · Zbl 0794.05008
[27] de Launey, W., Square GBRDs over non-abelian groups, Ars combin., 27, 40-49, (1989) · Zbl 0673.05014
[28] de Launey, W., Generalized Hadamard matrices which are developed modulo a group, Discrete math., 104, 49-65, (1992) · Zbl 0762.05025
[29] de Launey, W., Circulant \(GH(p\^{}\{2\}, Zp)\) exist for all primes p, Graphs combin., 8, 317-321, (1992) · Zbl 0770.05024
[30] J.F. Dillon, Elementary Hadamard Difference sets, Ph.D. Thesis, University of Maryland, 1974. · Zbl 0346.05003
[31] Dillon, J.F., Multiplicative difference sets via additive characters, Designs, codes and cryptography, 17, 225-235, (1999) · Zbl 0944.05012
[32] J.F. Dillon, H. Dobbertin, Cyclic difference sets with singer parameters, Manuscript, 1999. · Zbl 1043.05024
[33] Ding, C., Binary cyclotomic generators, (), 29-60 · Zbl 0939.94512
[34] C. Ding, Cryptographic counter generators, TUCS Dissertations 4, Turku Centre for Computer Science, Turku, Painosalama Oy, 1997.
[35] Ding, C.; Helleseth, T.; Lam, K.Y., Several classes of binary sequences with three-level autocorrelation, IEEE trans. inform. theory, 45, 7, 2601-2606, (1999) · Zbl 0983.94026
[36] Ding, C.; Helleseth, T.; Martinsen, H.M., New families of binary sequences with optimal three-level autocorrelation, IEEE trans. inform. theory, 47, 1, 428-433, (2001) · Zbl 1019.94009
[37] Dobbertin, H., Construction of bent functions and balanced Boolean functions with high nonlinearity, (), 61-74 · Zbl 0939.94563
[38] Dobbertin, H., One-to-one highly nonlinear functions on finite fields with characteristic 2, Appl. algebra eng. comm. comput., 9, 139-152, (1998) · Zbl 0924.94026
[39] Dobbertin, H., Almost perfect nonlinear power functions on GF(2n)the welch case, IEEE trans. inform. theory, 45, 1271-1275, (1999) · Zbl 0957.94021
[40] Dobbertin, H., Almost perfect nonlinear power functions on GF(2n)the niho case, Inform. and comput., 151, 57-72, (1999) · Zbl 1072.94513
[41] Gold, R., Maximal recursive sequences with 3-valued recursive cross correlation functions, IEEE trans. inform. theory, 14, 154-156, (1968) · Zbl 0228.62040
[42] Gordon, B.; Mills, W.H.; Welch, L.R., Some new difference sets, Canad. J. math., 14, 614-625, (1962) · Zbl 0111.24201
[43] Hammons, A.R.; Kumar, P.V.; Calderbank, A.R.; Sloane, N.J.A.; Solé, P., The Z4-linearity of kerdock, preparata, goethals and related codes, IEEE trans. inform. theory, 40, 2, 301-319, (1994) · Zbl 0811.94039
[44] Helleseth, T.; Rong, C.; Sandberg, D., New families of almost perfect nonlinear power mappings, IEEE trans. inform. theory, 45, 2, 475-485, (1999) · Zbl 0960.11051
[45] Helleseth, T.; Sandberg, D., Some power mappings with low differential uniformity, Applicable algebra eng. comm. computing, 8, 363-370, (1997) · Zbl 0886.11067
[46] Hewitt, E.; Ross, K., Abstract harmonic analysis, (1970), Springer Heidelberg · Zbl 0213.40103
[47] Hou, X.D., q-ary bent functions constructed from chain rings, Finite fields appl., 4, 55-61, (1998) · Zbl 1012.05038
[48] Hou, X.D., Bent functions, partial difference sets, and quasi-Frobenius local rings, Designs, codes and cryptography, 20, 251-268, (2000) · Zbl 0960.05028
[49] Hou, X.D.; Langevin, P., Results on bent functions, J. combin. theory A, 80, 232-246, (1997) · Zbl 0896.05011
[50] H. Janwa, R. Wilson, Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes, in: Proceedings AAECC-10, Lecture Notes in Computer Science, Vol. 673, Springer, Berlin, 1993, pp. 180-194. · Zbl 0798.94012
[51] Jungnickel, D., Difference sets, () · Zbl 0695.05010
[52] Jungnickel, D.; Pott, A., Perfect and almost perfect sequences, Discrete appl. math., 95, 331-359, (1999) · Zbl 0941.05013
[53] Jungnickel, D.; Pott, A., Difference sets: an introduction, (), 259-295 · Zbl 0946.05011
[54] Kasami, T., The weight enumerates for several classes of subcodes of the second order binary Reed-muller codes, Inform. and control, 18, 369-394, (1971) · Zbl 0217.58802
[55] Kerdock, A.M., A class of low-rate nonlinear codes, Inform. and control, 20, 182-187, (1972) · Zbl 0271.94016
[56] Kraemer, R.G., Proof of a conjecture on Hadamard 2-groups, J. combin. theory A, 63, 1-10, (1993) · Zbl 0771.05020
[57] Kumar, P.V.; Scholtz, R.A.; Welch, L.R., Generalized bent functions and their properties, J. combin. theory A, 40, 90-107, (1985) · Zbl 0585.94016
[58] Lachaud, G.; Wolfmann, J., The weights of the orthogonal of the extended quadratic binary Goppa codes, IEEE trans. inform. theory, 36, 686-692, (1990) · Zbl 0703.94011
[59] Lempel, A.; Cohn, M.; Eastman, W.L., A class of binary sequences with optimal autocorrelation properties, IEEE trans. inform. theory, 23, 1, 38-42, (1977) · Zbl 0359.94018
[60] Logachev, O.A.; Salnikov, A.A.; Yashchenko, V.V., Bent functions on a finite abelian group, Discrete math. appl., 7, 6, 547-564, (1997) · Zbl 0982.94012
[61] MacWilliams, F.J.; Sloane, N.J.A., The theory of error-correcting codes, (1977), North-Holland Amsterdam · Zbl 0369.94008
[62] Maschietti, A., Difference sets and hypherovals, Designs, codes and cryptography, 14, 89-98, (1998) · Zbl 0887.05010
[63] M. Matsui, Linear cryptanalysis method for DES cipher, in: Advances in Cryptology—EUROCRYPT’93, Lecture Notes in Computer Science, Vol. 765, Springer, Berlin, 1994, pp. 386-397. · Zbl 0951.94519
[64] Menezes, A.; van Oorschot, P.; Vanstone, S., Handbook of applied cryptography, CRC press series on discrete mathematics and its applications, (1996), CRC Press Boca Raton
[65] No, J.-S.; Golomb, S.W.; Gong, G.; Lee, H.-K.; Gaal, P., Binary pseudorandom sequences of period 2^m−1 with ideal autocorrelation generated by the polynomial zd+(z+1)d, IEEE trans. inform. theory, 44, 3, 1278-1282, (1998) · Zbl 0912.94017
[66] K. Nyberg, Perfect non-linear S-boxes, in: Advances in Cryptology, EUROCRYPT’91, Lecture Notes in Computer Science, Vol. 547, Springer, Berlin, 1992, pp. 378-386.
[67] K. Nyberg, Differentially uniform mappings for cryptography, in: Advances in Cryptography—Eurocrypt’93, Lecture Notes in Computer Science, Vol. 765, Springer, New York, 1994, pp. 55-64. · Zbl 0951.94510
[68] Olsen, J.D.; Scholtz, R.A.; Welch, L.R., Bent function sequences, IEEE trans. inform. theory, 28, 6, 858-864, (1982) · Zbl 0492.94019
[69] Pless, V.S.; Huffman, W.C., Handbook of coding theory, (1998), Elsevier Amsterdam · Zbl 0907.94001
[70] Pott, A., Finite geometry and character theory, Lecture notes in mathematics, Vol. 1601, (1995), Springer Berlin · Zbl 0818.05001
[71] Rothaus, O.S., On bent functions, J. combin. theory A, 20, 300-305, (1976) · Zbl 0336.12012
[72] Storer, T., Cyclotomy and difference sets, (1967), Markham Chicago · Zbl 0157.03301
[73] Tze, T.W.; Chanson, S.; Ding, C.; Helleseth, T.; Parker, M., Logarithm authentication codes, Inform. and comput., 184, 93-108, (2003) · Zbl 1038.94010
[74] Turyn, R.J., A special class of williamson matrices and difference sets, J. combin. theory A, 36, 111-115, (1984) · Zbl 0523.05016
[75] Wolfmann, J., Bent functions and coding theory, (), 393-417 · Zbl 0972.94023
[76] Xia, M., Some infinite class of williamson matrices and difference sets, J. combin. theory A, 61, 230-242, (1992) · Zbl 0772.05022
[77] Xiang, Q., Recent results on difference sets with classical parameters, (), 419-434 · Zbl 0940.05014
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.