# Characterizing the ANF of Single-Cycle Boolean Permutations

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?

• 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). – Fractalic Aug 20 '19 at 21:23