Codes, graphs, and schemes from nonlinear functions
type: Item
instance of: scholarly article
title: Codes, graphs, and schemes from nonlinear functions
zbMATH Open document ID: 1015.05093
DOI: 10.1016/S0195-6698(02)00116-6
author: Dmitry G. Fon-Der-Flaass
author: Edwin R. Van Dam
published in: European Journal of Combinatorics
publication date: 2003-04-09T00:00:00Z
review text: The main object of the paper are functions which in some sense are far from being linear, in particular the hierarchy CR (crooked functions) -- AB (almost bent functions) -- APN (almost perfect nonlinear functions) defined on binary vector spaces (CR implies AB, which implies APN). These functions have applications in cryptography because of their resistance to certain types of attacks. They can be described combinatorially, algebraically (in terms of the number of solutions of certain equations) and in terms of the Fourier coefficients. These characterizations are reviewed or proved in the present paper. A gap remains: no combinatorial characterization of AB functions is known. In the final section the known functions belonging to these families are described. They all map \(x\) to \(x^t\) for a suitable exponent \(t.\) The names attached to these functions are Gold, Kasami, Welch, Niho, Dobbertin. In the bulk of the paper it is described how other combinatorial objects can be constructed from functions of those families. This includes semi-biplanes, linear codes with minimum distance \(5,\) distance-regular graphs, nonlinear codes with the same parameters as the Preparata codes, Hadamard difference sets and certain association schemes.
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1895801
zbMATH Keywords: nonlinear functions
zbMATH Keywords: codes
zbMATH Keywords: Fourier transform
reviewed by: Jürgen Bierbrauer
MaRDI profile type: Publication
cites work: Crooked functions, bent functions, and distance regular graphs
cites work: Q3992965
cites work: A sharpening of the Johnson bound for binary linear codes and the nonexistence of linear codes with Preparata parameters
cites work: Association schemes related to Kasami codes and Kerdock sets
cites work: A family of antipodal distance-regular graphs related to the classical Preparata codes
cites work: Q4000288
cites work: Binary m-sequences with three-valued crosscorrelation: a proof of Welch's conjecture
cites work: Codes, bent functions and permutations suitable for DES-like cryptosystems
cites work: Q4365754
cites work: Q4242018
cites work: A class of functions and their application in constructing semi-biplanes and association schemes
cites work: Uniformly packed codes and more distance regular graphs from crooked functions
cites work: Q2712106
cites work: Maximal recursive sequences with 3-valued recursive cross-correlation functions (Corresp.)
cites work: Q4242028
cites work: A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences
cites work: The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes
cites work: Q3946078
cites work: Q4934708
cites work: Character sums and difference sets
cites work: Maximally nonlinear functions and bent functions.
Recommended article: The graphs of non-degenerate linear codes
Recommended article: On the constructions of constant-composition codes from perfect nonlinear functions
Recommended article: Q5013042
Recommended article: Two classes of linear codes based on perfect nonlinear functions
Recommended article: A New Construction of Nonlinear Codes via Rational Function Fields
Recommended article: Asymptotically Good Nonlinear Codes From Algebraic Curves
Recommended article: Q3221878
Recommended article: Q4736422
Recommended article: Excellent Nonlinear Codes From Algebraic Function Fields
Recommended article: On the Covering Structures of Two Classes of Linear Codes From Perfect Nonlinear Functions
description: scientific article; zbMATH DE number 1895801