article

Highly nonlinear mappings

Authors:

Claude Carlet,

Cunsheng DingAuthors Info & Claims

Journal of Complexity, Volume 20, Issue 2-3

Pages 205 - 244

https://doi.org/10.1016/j.jco.2003.08.008

Published: 01 April 2004 Publication History

Abstract

Functions with high nonlinearity have important applications in cryptography, sequences and coding theory. The purpose of this paper is to give a well-rounded treatment of non-Boolean functions with optimal nonlinearity. We summarize and generalize known results, and prove a number of new results. We also present open problems about functions with high nonlinearity.

References

[1]

{1} A.S. Ambrosimov, Properties of bent functions of q-valued logic over finite fields, Discrete Math. Appl. 4 (4) (1994) 341-350.]]

Crossref

Google Scholar

[2]

{2} K.T. Arasu, J.A. Jedwab, S. Sehgal, New constructions of Menon difference sets, J. Combin. Theory A 64 (1993) 329-336.]]

Digital Library

Google Scholar

[3]

{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.]]

Digital Library

Google Scholar

[4]

{4} T. Beth, D. Jungnickel, H. Lenz, Design Theory, Vol. 1, 2nd Edition, Cambridge University Press, Cambridge, 1999.]]

Digital Library

Google Scholar

[5]

{5} E. Biham, A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology 4 (1) (1991) 3-72.]]

Digital Library

Google Scholar

[6]

{6} B.W. Brock, Hermitian congruence and the existence and completion of generalized Hadamard matrices, J. Combin. Theory A 49 (1988) 233-261.]]

Digital Library

Google Scholar

[7]

{7} B.W. Brock, A new construction of circulant GH(p2; Zp), Discrete Math. 112 (1993) 249-252.]]

Digital Library

Google Scholar

[8]

{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.]]

Google Scholar

[9]

{9} P. Camion, A. Canteaut, Generalization of Siegenthaler inequality and Schnorr-Vaudenay multipermutations, in: N. Koblitz (Ed.), Advances in Cryptoloy--CRYPTO'96, Lecture Notes in Computer Science, Vol. 1109, Springer, Berlin, 1996, pp. 372-386.]]

Digital Library

Google Scholar

[10]

{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.]]

Google Scholar

[11]

{11} A. Canteaut, P. Charpin, H. Dobbertin, Weight divisibility of cyclic codes, highly nonlinear functions on F2m, and cross correlation of maximum-length sequences, SIAM J. Discrete Math. 13 (1) (2000) 105-138.]]

Digital Library

Google Scholar

[12]

{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.]]

Digital Library

Google Scholar

[13]

{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.]]

Crossref

Google Scholar

[14]

{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.]]

Google Scholar

[15]

{15} C. Carlet, On cryptographic propagation criteria for Boolean functions, Inform. and Comput. 151 (1999) 32-56.]]

Digital Library

Google Scholar

[16]

{16} C. Carlet, S. Dubuc, On generalized bent and q-ary perfect nonlinear functions, in: D. Jungnickel, H. Niederreiter (Eds.), Finite Fields and Applications, Proceedings of Fq5, Springer, Berlin, 2000, pp. 81-94.]]

Google Scholar

[17]

{17} C. Carlet, P. Guillot, An alternate characterization of the bentness of binary functions with uniqueness, J. Combin. Theory A 76 (1996) 328-335.]]

Digital Library

Google Scholar

[18]

{18} C. Carlet, P. Guillot, A characterization of binary bent functions, Designs, Codes and Cryptography 14 (1998) 130-140.]]

Digital Library

Google Scholar

[19]

{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.]]

Digital Library

Google Scholar

[20]

{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.]]

Google Scholar

[21]

{21} Y.Q. Chen, On the existence of a belian Hadamard difference sets and a new family of difference sets, Finite Fields Appl. 3 (1997) 234-256.]]

Digital Library

Google Scholar

[22]

{22} C.J. Colbourn, W. de Launey, Difference matrices, in: C. Colbourn, J.H. Dinitz (Eds.), Handbook of Combinatorial Designs, CRC Press, New York, 1996, pp. 287-297 (Chapter IV.11).]]

Google Scholar

[23]

{23} R.S. Coulter, R. Matthews, Planar functions and plans of the Lenz-Barlotti class II, Designs, Codes and Cryptography 10 (1997) 165-195.]]

Digital Library

Google Scholar

[24]

{24} T.W. Cusick, C. Ding, A. Renvall, Stream Ciphers and Number Theory, in: North-Holland Mathematical Library, Vol. 55, North-Holland/Elsevier, Amsterdam, 1998.]]

Google Scholar

[25]

{25} T.W. Cusick, H. Dobbertin, Some new 3-valued cross correlation functions of binary sequences, IEEE Trans. Inform. Theory 42 (1996) 1238-1240.]]

Crossref

Google Scholar

[26]

{26} J.A. Davis, Almost difference sets and reversible difference sets, Arch. Math. 59 (1992) 595-602.]]

Crossref

Google Scholar

[27]

{27} W. de Launey, Square GBRDs over non-abelian groups, Ars Combin. 27 (1989) 40-49.]]

Google Scholar

[28]

{28} W. de Launey, Generalized Hadamard matrices which are developed modulo a group, Discrete Math. 104 (1992) 49-65.]]

Digital Library

Google Scholar

[29]

{29} W. de Launey, Circulant GH(p2, Zp) exist for all primes p, Graphs Combin. 8 (1992) 317-321.]]

Digital Library

Google Scholar

[30]

{30} J.F. Dillon, Elementary Hadamard Difference sets, Ph.D. Thesis, University of Maryland, 1974.]]

Google Scholar

[31]

{31} J.F. Dillon, Multiplicative difference sets via additive characters, Designs, Codes and Cryptography 17 (1999) 225-235.]]

Digital Library

Google Scholar

[32]

{32} J.F. Dillon, H. Dobbertin, Cyclic difference sets with singer parameters, Manuscript, 1999.]]

Google Scholar

[33]

{33} C. Ding, Binary cyclotomic generators, in: B. Preneel (Ed.), Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, New York, 1995, pp. 29-60.]]

Google Scholar

[34]

{34} C. Ding, Cryptographic counter generators, TUCS Dissertations 4, Turku Centre for Computer Science, Turku, Painosalama Oy, 1997.]]

Google Scholar

[35]

{35} C. Ding, T. Helleseth, K.Y. Lam, Several classes of binary sequences with three-level autocorrelation, IEEE Trans. Inform. Theory 45 (7) (1999) 2601-2606.]]

Digital Library

Google Scholar

[36]

{36} C. Ding, T. Helleseth, H.M. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Trans. Inform. Theory 47 (1) (2001) 428-433.]]

Digital Library

Google Scholar

[37]

{37} H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in: B. Preneel (Ed.), Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, Heidelberg, 1995, pp. 61-74.]]

Google Scholar

[38]

{38} H. Dobbertin, One-to-one highly nonlinear functions on finite fields with characteristic 2, Appl. Algebra Eng. Comm. Comput. 9 (1998) 139-152.]]

Crossref

Google Scholar

[39]

{39} H. Dobbertin, Almost perfect nonlinear power functions on GF(2n): the Welch case, IEEE Trans. Inform. Theory 45 (1999) 1271-1275.]]

Digital Library

Google Scholar

[40]

{40} H. Dobbertin, Almost perfect nonlinear power functions on GF(2n): the Niho case, Inform. and Comput. 151 (1999) 57-72.]]

Digital Library

Google Scholar

[41]

{41} R. Gold, Maximal recursive sequences with 3-valued recursive cross correlation functions, IEEE Trans. Inform. Theory 14 (1968) 154-156.]]

Crossref

Google Scholar

[42]

{42} B. Gordon, W.H. Mills, L.R. Welch, Some new difference sets, Canad. J. Math. 14 (1962) 614-625.]]

Crossref

Google Scholar

[43]

{43} A.R. Hammons Jr., P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, P. Solé, The Z4-linearity of Kerdock, Preparata, Goethals and related codes, IEEE Trans. Inform. Theory 40 (2) (1994) 301-319.]]

Digital Library

Google Scholar

[44]

{44} T. Helleseth, C. Rong, D. Sandberg, New families of almost perfect nonlinear power mappings, IEEE Trans. Inform. Theory 45 (2) (1999) 475-485.]]

Digital Library

Google Scholar

[45]

{45} T. Helleseth, D. Sandberg, Some power mappings with low differential uniformity, Applicable Algebra Eng. Comm. Computing 8 (1997) 363-370.]]

Crossref

Google Scholar

[46]

{46} E. Hewitt, K. Ross, Abstract Harmonic Analysis, Springer, Heidelberg, 1970.]]

Google Scholar

[47]

{47} X.D. Hou, q-ary bent functions constructed from chain rings, Finite Fields Appl. 4 (1998) 55-61.]]

Digital Library

Google Scholar

[48]

{48} X.D. Hou, Bent functions, Partial difference sets, and quasi-Frobenius local rings, Designs, Codes and Cryptography 20 (2000) 251-268.]]

Digital Library

Google Scholar

[49]

{49} X.D. Hou, P. Langevin, Results on bent functions, J. Combin. Theory A 80 (1997) 232-246.]]

Digital Library

Google Scholar

[50]

{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.]]

Digital Library

Google Scholar

[51]

{51} D. Jungnickel, Difference sets, in: J. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory: A Collection of Surveys, Wiley, New York, 1992.]]

Google Scholar

[52]

{52} D. Jungnickel, A. Pott, Perfect and almost perfect sequences, Discrete Appl. Math. 95 (1999) 331-359.]]

Crossref

Google Scholar

[53]

{53} D. Jungnickel, A. Pott, Difference sets: an introduction, in: A. Pott, P.V. Kumar, T. Helleseth, D. Jungnickel (Eds.), Difference Sets, Sequences and their Correlation Properties, Kluwer, Amsterdam, 1999, pp. 259-295.]]

Google Scholar

[54]

{54} T. Kasami, The weight enumerates for several classes of subcodes of the second order binary Reed-Muller codes, Inform. and Control 18 (1971) 369-394.]]

Crossref

Google Scholar

[55]

{55} A.M. Kerdock, A class of low-rate nonlinear codes, Inform. and Control 20 (1972) 182-187.]]

Crossref

Google Scholar

[56]

{56} R.G. Kraemer, Proof of a conjecture on Hadamard 2-groups, J. Combin. Theory A 63 (1993) 1-10.]]

Digital Library

Google Scholar

[57]

{57} P.V. Kumar, R.A. Scholtz, L.R. Welch, Generalized bent functions and their properties, J. Combin. Theory A 40 (1985) 90-107.]]

Crossref

Google Scholar

[58]

{58} G. Lachaud, J. Wolfmann, The weights of the orthogonal of the extended quadratic binary Goppa codes, IEEE Trans. Inform. Theory 36 (1990) 686-692.]]

Digital Library

Google Scholar

[59]

{59} A. Lempel, M. Cohn, W.L. Eastman, A class of binary sequences with optimal autocorrelation properties, IEEE Trans. Inform. Theory 23 (1) (1977) 38-42.]]

Digital Library

Google Scholar

[60]

{60} O.A. Logachev, A.A. Salnikov, V.V. Yashchenko, Bent functions on a finite Abelian group, Discrete Math. Appl. 7 (6) (1997) 547-564.]]

Crossref

Google Scholar

[61]

{61} F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.]]

Google Scholar

[62]

{62} A. Maschietti, Difference sets and hypherovals, Designs, Codes and Cryptography 14 (1998) 89-98.]]

Digital Library

Google Scholar

[63]

{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.]]

Digital Library

Google Scholar

[64]

{64} A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press Series on Discrete Mathematics and Its Applications, CRC Press, Boca Raton, 1996.]]

Digital Library

Google Scholar

[65]

{65} J.-S. No, S.W. Golomb, G. Gong, H.-K. Lee, P. Gaal, Binary pseudorandom sequences of period 2m - 1 with ideal autocorrelation generated by the polynomial zd + (z + 1)d, IEEE Trans. Inform. Theory 44 (3) (1998) 1278-1282.]]

Crossref

Google Scholar

[66]

{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.]]

Google Scholar

[67]

{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.]]

Digital Library

Google Scholar

[68]

{68} J.D. Olsen, R.A. Scholtz, L.R. Welch, Bent function sequences, IEEE Trans. Inform. Theory 28 (6) (1982) 858-864.]]

Digital Library

Google Scholar

[69]

{69} V.S. Pless, W.C. Huffman, Handbook of Coding Theory, Elsevier, Amsterdam, 1998.]]

Digital Library

Google Scholar

[70]

{70} A. Pott, Finite Geometry and Character Theory, in: Lecture Notes in Mathematics, Vol. 1601, Springer, Berlin, 1995.]]

Google Scholar

[71]

{71} O.S. Rothaus, On bent functions, J. Combin. Theory A 20 (1976) 300-305.]]

Crossref

Google Scholar

[72]

{72} T. Storer, Cyclotomy and Difference Sets, Markham, Chicago, 1967.]]

Google Scholar

[73]

{73} T.W. Tze, S. Chanson, C. Ding, T. Helleseth, M. Parker, Logarithm authentication codes, Inform. and Comput. 184 (2003) 93-108.]]

Digital Library

Google Scholar

[74]

{74} R.J. Turyn, A special class of Williamson matrices and difference sets, J. Combin. Theory A 36 (1984) 111-115.]]

Crossref

Google Scholar

[75]

{75} J. Wolfmann, Bent functions and coding theory, in: A. Pott, P.V. Kumar, T. Helleseth, D. Jungnickel (Eds.), Difference Sets, Sequences and their Correlation Properties, Kluwer, Amsterdam, 1999, pp. 393-417.]]

Google Scholar

[76]

{76} M. Xia, Some infinite class of Williamson matrices and difference sets, J. Combin. Theory A 61 (1992) 230-242.]]

Digital Library

Google Scholar

[77]

{77} Q. Xiang, Recent results on difference sets with classical parameters, in: A. Pott, P.V. Kumar, T. Helleseth, D. Jungnickel (Eds.), Difference Sets, Sequences and their Correlation Properties, Kluwer, Amsterdam, 1999, pp. 419-434.]]

Google Scholar

[78]

R. Lidl, H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Vol. 20, Addison-Wesley, Reading, MA, 1983.]]

Google Scholar

Cited By

View all

Xiao HCao X(2024)Sequences with ideal auto-correlation derived from group actionsCryptography and Communications10.1007/s12095-024-00710-516:5(909-920)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s12095-024-00710-5
Kölsch LPolujan A(2024)Value Distributions of Perfect Nonlinear FunctionsCombinatorica10.1007/s00493-023-00067-y44:2(231-268)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00493-023-00067-y
Wu HYang JFeng K(2023)The Weight Distributions of Two Classes of Linear Codes From Perfect Nonlinear FunctionsIEEE Transactions on Information Theory10.1109/TIT.2023.334822870:6(4102-4109)Online publication date: 29-Dec-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3348228
Show More Cited By

Index Terms

Highly nonlinear mappings

Recommendations

A note on vectorial bent functions

In this paper we give three methods on the constructions of vectorial bent functions from F"2^n to F"2^n^2, where n is a positive even integer. The first two kinds of functions are based on monomial bent functions. The third kind of functions are based ...
Highly nonlinear plateaued functions

The authors describe a method for producing Boolean functions of degree d ≥ 3 in n = 2dk − 1 (k = 1, 2, …) variables, such that the functions are plateaued and balanced, have high nonlinearity and have no linear structures. The nonlinearity is 2^{n −1} −...
Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions

Studying algebraic immunity of Boolean functions is recently a very important research topic in cryptography. It is recently proved by Courtois and Meier that for any Boolean function of n-variable the maximum algebraic immunity is @__ __n2@__ __. We ...

Reviews

Reviewer: Jonathan Samuel Golan

Highly nonlinear mappings between additive abelian groups have important applications in cryptography and coding theory. The authors state that the purpose of their paper is "to give a well-rounded treatment of non-Boolean functions with optimum or almost optimum nonlinearity, ... to summarize the known results on the subject, ... [to] generalize several of them, ... [and to] prove new results." In this, they succeed admirably. Though often technical, the paper is well conceived, well and clearly written, and clearly authoritative. It also comes with a very useful and comprehensive bibliography. Serious researchers in the area of nonlinear mappings should undoubtedly read this, and take it very seriously. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Complexity Volume 20, Issue 2-3

Special issue on coding and cryptography

April/June 2004

340 pages

ISSN:0885-064X

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xiao HCao X(2024)Sequences with ideal auto-correlation derived from group actionsCryptography and Communications10.1007/s12095-024-00710-516:5(909-920)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s12095-024-00710-5
Kölsch LPolujan A(2024)Value Distributions of Perfect Nonlinear FunctionsCombinatorica10.1007/s00493-023-00067-y44:2(231-268)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00493-023-00067-y
Wu HYang JFeng K(2023)The Weight Distributions of Two Classes of Linear Codes From Perfect Nonlinear FunctionsIEEE Transactions on Information Theory10.1109/TIT.2023.334822870:6(4102-4109)Online publication date: 29-Dec-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3348228
Xu B(2023)Plateaued functions on finite nonabelian groupsJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-023-01266-y58:4(1019-1053)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s10801-023-01266-y
Kamlovskii OPankov K(2022)Some Classes of Balanced Functions over Finite Fields with a Small Value of the Linear CharacteristicProblems of Information Transmission10.1134/S003294602204009358:4(389-402)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1134/S0032946022040093
Fan YXu B(2022)Fourier transforms on finite group actions and bent functionsJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-021-01057-355:2(429-460)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10801-021-01057-3
Xu B(2022)Characterizations and constructions of plateaued functions on finite abelian groupsDesigns, Codes and Cryptography10.1007/s10623-022-01151-y91:4(1261-1292)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1007/s10623-022-01151-y
Wu YLi NZeng XCai Y(2022)Several Classes of Niho Type Boolean Functions with Few Walsh Transform ValuesInformation Security and Cryptology10.1007/978-3-031-26553-2_17(318-333)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-26553-2_17
Shao MMiao Y(2021)Algebraic manipulation detection codes via highly nonlinear functionsCryptography and Communications10.1007/s12095-020-00453-z13:1(53-69)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s12095-020-00453-z
Carlet CKim KMesnager S(2021)A direct proof of APN-ness of the Kasami functionsDesigns, Codes and Cryptography10.1007/s10623-020-00830-y89:3(441-446)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10623-020-00830-y
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A note on vectorial bent functions

Highly nonlinear plateaued functions

Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations