Some questions on building permutations from boolean functions

Question

I've seen multiple examples of boolean functions being used as a permutation.

For example the Keccak Chi : 2.3.1 function:

from https://keccak.team/figures.html

Or as a formula: for $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ with indexes calculated modulo 5

The first question would be, what is the rationale (or proof) why this is a permutation?

The second, related one: What are the properties, the boolean function has to satisfy that it results in a permutation?

---

And now regarding the inverse of such a permutation.

Are there any generic methods/algorithms to find the inverse of such a construction?

Also, what are the major contributing factors for the complexity of the inverse (number of variables, algebraic degree etc.)?

And if such a method is applied to a larger input - say $i=\{0..127\}$, is the inverse more difficult to calculate, if the function has only a few (like the 3 for Chi) or many, say 128, input variables?

Any answers/pointers are appreciated.

Answer 1

The $\chi$ function is defined and analyzed in Joan Daemen Ph.D. Thesis

• Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis, 1995

Chapter 6: Shift-Invariant Transformations (SIT) is where the theory is mentioned. I'll provide a glimpse of it (lots of definitions and results).

The properties of SIT that make them useful;

• In hardware, these transformations can be implemented as an interconnected array of identical 1-bit output “processors.”
• The shift-invariance ensures that the computational load is optimally distributed.
• In software, their regularity allows efficient implementations by employing bitwise logical operations.
• Moreover, binary shift-invariant transformations can be specified by a single Boolean function.

SITs are very related to finite cellular automata which focus on long-term structure and pattern over time this work concentrate on the short term aspects of invertibility and local propagation and correlation properties.

Definition 6.1: A transformation $\phi: \mathcal{A} \to \mathcal{A}$ is shift-invariant if

$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ where $\mathcal{A}$ is all possible states.

Then it defined the local maps where the image only depends on some of the inputs.

Theorem 6.1 (D. Richardson ) If a transformation $\phi$ with finite $\nu$ is invertible, then its inverse $\phi^{−1}$ is a shift-invariant transformation with finite $\nu$.

Where $\nu$ defines the neighborhood, see 6.3 Local Maps. This theorem doesn't provide a construction of the inverse explicitly.

Section 6.6 Nonlinear transformations with finite $\nu$ is where the action is started.

Here the local map is specified by a set of patterns, called the complementing landscapes (CL). The value of a component is complemented if its neighborhood takes on one of these patterns. A landscape is a pattern consisting of symbols $1, 0$, and $\textbf{-}$ denoting “don’t care,” positioned relative to an origin, denoted by $∗$. In this context, the all-zero state will be denoted by $0^*$ and the all-one state by $1^*$.

The inverse of $\chi$ is talked in local and global invertibility sections that require a deeper in theory. A nice read to learn if you want.

So, As I said in the comments, either one can look for all possible permutations to see the desired property, or look in the theory as Daemen, did. They used this theory years later in the Sponge construction where $\chi$ is the only non-linear part of the SHA-3.

Answer 2

The general algebraic question is multifaceted and can be quite complicated. Some depend on vector space, some on extension field properties.

As mentioned in the comments checking the property can be simpler.

I answered a related question Examples of multi output bit balanced Boolean functions

Nyberg’s articles mentioned there are

K. Nyberg, Differentially uniform mappings for cryptography, 1993 and

K Nyberg, Perfect nonlinear S-boxes, 1992

both easily locatable on google scholar.

Edit: The keccak $\chi$ maps $\{0,1\}^5$ to itself.

I will use $a_i$ as input and $A_i$ as output variables as in the edited question.

Counting indices modulo 5, if there is no $i$ such that $(a_i,a_{i+2})=(0,1)$ then $\chi$ has a fixed point for that input. Let $W=\{i: (a_i,a_{i+2})=(0,1)\},$ then the general mapping just inverts the bits belonging to $i.$

Note that the sets $J_i,J_j$ where $J_i=\{i,i+2\}$ are disjoint except when $j=i+2$ or $i=j+2.$ So there is no ambiguity for determining the inverse unless we are in this special case, thus the inverse exists except in this special case. But even in this case the patterns $(a_i,a_{i+2},a_{i+4})$ which result in bitflips are unambiguous.

If $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ then $a_{i+1}$ will be flipped but not $a_{i+3}$. So $A_{i+1}=1\oplus a_{i+1},$ and $A_{i+3}=a_{i+3}.$

If $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ then $a_{i+1}$ will be flipped but not necessarily $a_{i+3}$, that will depend on the value of $a_{i+6}=a_{i+1}$. But that bit is not impacted by the previous argument since $J_i$ and $J_j$ are disjoint if $i=j+1\pmod 2.$

So a unique inverse mapping exists.

Remark: In general going between "basis independent" extension field formulations of permutations vs "basis dependent" bit vector permutations is hardly straightforward. I don't see an immediate basis independent extension field formulation for this permutation, and as pointed out in the comments to the question such formulations obtained (say) by Lagrange interpolation, can be quite complicated and high degree.

Answer 3

As my first question has been answered in detail in the answers of kodlu and kelalaka, I wanted to share the results I gathered on my second question since posting:

What are the properties, the boolean function has to satisfy that it results in a permutation?

During lots of additional reading I discovered, that this seems to be a well (but not widely) known property. For example stated and proven in Vectorial Boolean Functions for Cryptography chapter 2.3.1 as Proposition 2:

An (n, m)-function is balanced if and only if its component functions are balanced, that is, if and only if, for every nonzero v ∈ $F^2_m$, the Boolean function v · F is balanced.

with the additional fact from chapter 2.3:

balanced (n, n)-functions are the permutations on $F^2_n$

So, an (n, n)-function is a permutation, if and only if it is balanced according to the above definition.

In other words, every component function has to be balanced, as well as any possible combination of component functions, incl. all functions at once, have to be balanced.

By the way, this property is also stated, less obviously, in Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis, 1995 Theorem 5.1

This also means, checking this property for the general case for larger functions, e.g. 64bit wide (n=64), is not feasible as it would require checking balancedness for 2^64 - 1 different combinations (for 2^64 possible inputs each). So some tricks or shortcuts will likely be required.