Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We can represent $F$ as a collection $[F_1(x), F_2(x), \ldots, F_n(x)]$ of boolean functions (i.e. each $F_i$ is a mapping from $\{0,1\}^n$ to $\{0, 1\}$). Let $f_i(x)$ denote the algebraic normal form (ANF) of $F_i(x)$. I am interested in the following questions:

Is there a way to characterize when $F$ is a single-cycle permutation by saying something about the $f_i$'s? I am looking for a statement of the form: $F$ is a single-cycle permutation if and only if some property about the $f_i$'s hold. If this isn't known, what about a similar statement relating $F$ with its $F_i$'s? In other words, under what conditions do $n$ boolean function $F_1(x), \ldots, F_n(x)$ induce a single-cycle permutation? If we only require $F$ to be a permutation, then the following characterization is known (Boolean Function Representation of S-Boxes and Boolean Permutations): $F$ is a boolean permutation if and only if for any non-zero vector $c = (c_1, c_2, \ldots, c_n) \in \{0, 1\}^n$, the boolean function defined by $F_c(x) = c_1 F_1(x) \oplus c_2F_2(x) \oplus \ldots \oplus c_nF_n(x)$ produces a one for $2^{n-1}$ different values of $x$. Can something similar be said for single-cycle permutations?

  • 1
    $\begingroup$ 5 cents: it can not be linear since F(0) = 0; also there is a unique (up to a constant) Boolean function $g$ such that $g(F(x)) = g(x) \oplus 1$ for all $x$. And there are no Boolean functions $h$ such that $h(F(x)) = h(x)$ for all $x$ (except $h=0$ and $h=1$ of course). $\endgroup$
    – Fractalic
    Aug 20, 2019 at 21:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.