Raziskovalni matematični seminar - Arhiv

In this talk, we address the algebraic method to design plateaued functions with desirable cryptographic properties (such as maximal algebraic degree and balancedness) by employing the generalized Maiorana-McFarland class (GMM) of Boolean functions. We consider functions in the GMM class of the form $f(x,y)=x \cdot \phi(y) \oplus h(y)$, where $x \in \F_2^{n/2+k}, y \in \F_2^{n/2 -k}$ and $\phi(y): \F_2^{n/2 -k} \rightarrow \F_2^{n/2 +k}$, and derive a set of sufficient conditions for designing optimal plateaued functions. We will show that under certain conditions designed optimal plateaued functions do not admit the linear structures. Furthermore, we will show that under specific conditions, the addition of an indicator ($1_{R}(x,y) = 1_{E_1}(x)1_{E_2}(y)$) to a function $g(x,y) = x \cdot \phi(y)$, we have that $f(x,y) = g(x,y) \oplus  1_{R}(x,y)$ is a plateaued function.

We introduce Boole's problem, and the reasonably large literature related to it. We then recall an old result of Renyi (1962) that we prefer to call "a zero-one lemma", and show that it can provide a simple, elementary (short, high school level) proof for most of the results in the extensive literature about this problem. We also derive a few new results with the help of this powerful lemma.