Simple reversible algorithms that satisfies SAC

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.

• Does it have to be length preserving, or can the output be longer than the input? May 26 '17 at 11:20
• @CodesInChaos: the output should be a block of the same size as the input block. May 26 '17 at 11:24
• Since the term allows for the most diverse interpretations, could you please clarify how you define "simplest"? Also, to avoid users repeating the obvious and/or posting answers about what you might already know… What research have you done? What did you find? And — last but not least — why didn't your findings satisfy your needs? May 26 '17 at 18:05
• I edited the question in an attempt to clarify. Jun 4 '17 at 12:20
• Given your needs keccak with an output that hasn't been truncated might work. Jun 4 '17 at 23:09

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)

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.

• And how do you make sure that the resulting $n$ bent functions in parallel is invertible? Jun 4 '17 at 22:52
• Damn. I was just going to ask that... Jun 4 '17 at 22:57
• of course! I'll try and prove/disprove it's possible in about 8 hours I should have time. Jun 4 '17 at 23:55