Extremal Generalized S-Boxes

Abstract

It is well known that there does not exist a Boolean function f: Z_2^m ightarrow Z_2^n satisfying both basic cryptologic criteria, balancedness and perfect nonlinearity. In /9/ it was shown that, if we use as a domain quasigroup G instead of the group Z_2^n, one can find functions which are at the same time balanced and perfectly nonlinear. Such functions have completely flat difference table. We continue in our previous work, but we turn our attention to the worst case when all lines of Cayley table of G define so called linear structure of f (/5/). We solve this problem in both directions: We describe all such bijections f:G ightarrow Z_2^n, for a given quasigroup |G|=2^n, and describe such quasigroups for a given function f.