Simple reversible algorithms that satisfies SAC

Question

What are some simple algorithms that …

1. operate on a block of fixed size (or can be easily made to do so), i.e. the input block has a fixed size, e.g. 256 bit, and the output is a block of the same size
2. are reversible (can't be a hash function)
3. satisfy the strict avalanche criterion (SAC)

I'm not interested in any other cryptographic properties. It doesn't have to be a secure cipher.

I use the word simple in a very general sense. I'm interested in anything that most engineers would call simple, easy to implement in software and/or hardware, although there is likely a correlation to well-defined measures like computational complexity.

I have considered AES or a hash function like SHA-256, which I believe exhibit a strong avalanche effect (not sure if they satisfy SAC), but a hash function is not reversible and AES seems unnecessarily complicated if you do not require the algorithm to be a secure cipher. I thought there must be something simpler. I could, of course, be mistaken.

Answer 1

One simple approach would be, if your input/output size is $n$ bits, is to select a representation of $GF(2^n)$, and a random nonzero value $v$, and have your function be $F(u) = u \times v$ (where $\times$ is multiplication within $GF(2^n)$)

• It operates on blocks of fixed size

• It is reversible (by multiplying by the value $v^{-1}$)

• It satisfies the SAC in this sense: for input bit $i$, and any output bit $j$, flipping bit $i$ of the input will flip bit $j$ of the output for almost exactly half, that is, $2^{n-1}/(2^n-1) \approx 1/2 + 2^{-(n+1)}$

Now, it doesn't satisfy the SAC for a fixed value $v$; for a fixed value, flipping bit $i$ will flip bit $j$ either always or never; so, it might not be the answer you're looking for (on the other hand, it may)

Answer 2

Rotate a block of bits by its population count. For four bits, this is

0000  0000
0001  0010
0010  0100
0011  1100
0100  1000
0101  0101
0110  1001
0111  1011
1000  0001
1001  0110
1010  1010
1011  1101
1100  0011
1101  1110
1110  0111
1111  1111

If you change bit 0, the changes are

0010
1000
1101
0010
0111
0111
1101
1000

and each column has four zeros and four ones.

Answer 3

A Boolean function $f:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$ which has Hadamard coefficients all equal to $\pm 2^{n/2}$ is called a bent function, clearly $n$ must be even.

Such a function satisfies a propagation criterion of maximum strength, i.e.,

for any nonzero vector $a$ the function $f(x \oplus a)+f(x)$ is balanced. But the function itself is not balanced.

Take $n$ bent functions in parallel, you have more than what you want. If all you want is SAC then only having the property above for vectors $a$ of Hamming weight 1 is sufficient.

The other properties of such functions have been explored, such as linear structures, nonlinearity etc. A good cryptographic starting point is this paperhere. There are hundreds of references to bent functions but most need not be crypto related.