A new construction of highly nonlinear S-boxes

Peter Beelen, Gregor Leander

Cryptography and Communications Volume 4, Issue 1, pp 65-77


In this paper we give a new construction of highly nonlinear vectorial Boolean functions. This construction is based on coding theory, more precisely we use concatenation to construct Boolean functions from codes over Fq containing a first-order generalized Reed–Muller code. As it turns out this construction has a very compact description in terms of Boolean functions, which is of independent interest. The construction allows one to design functions with better nonlinearities than known before.


Tags: 06E30, 14G50, 65T50, 94A60, Boolean functions, Concatenation, Linear codes, nonlinearity, Reed–Muller codes