Theoretical Backgrounds of Applied Discrete Mathematics

Construction of balanced functions with high nonlinearity and other cryptographic properties

A. S. Shaporenko

Novosibirsk State University, Novosibirsk, Russia

Abstract: We present an iterative construction that can be used to construct balanced functions with high nonlinearity. Using this construction, we obtained Boolean functions in an even number $n\geqslant 18$ of variables which have no linear structures with nonlinearity $2^{n-1}-(2^{{n}/{2}-1}+2^{{n}/{2}-3}+2^{{n}/{2}-5}+2^{{n}/{2}-7})$. Additional conditions are given under which the functions obtained using the construction will be correlation immune. We also present results concerning “bent sum decomposition problem”.

Keywords: balanced Boolean functions, nonlinear Boolean functions, bent functions.

UDC: 519.7

DOI: 10.17223/20710410/63/1