5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Does it have to be length preserving, or can the output be longer than the input? $\endgroup$ May 26, 2017 at 11:20
  • $\begingroup$ @CodesInChaos: the output should be a block of the same size as the input block. $\endgroup$
    – mistercake
    May 26, 2017 at 11:24
  • $\begingroup$ 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? $\endgroup$
    – e-sushi
    May 26, 2017 at 18:05
  • $\begingroup$ I edited the question in an attempt to clarify. $\endgroup$
    – mistercake
    Jun 4, 2017 at 12:20
  • $\begingroup$ Given your needs keccak with an output that hasn't been truncated might work. $\endgroup$
    – Q-Club
    Jun 4, 2017 at 23:09

3 Answers 3

3
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Can you indicate how this satisfies the SAC? If you flip one bit of the input (e.g. say that it has only a few bits set) then it doesn't flip all the other bits with 50% certainty, right? $\endgroup$
    – Maarten Bodewes
    Apr 12, 2023 at 1:06
  • 1
    $\begingroup$ Flipping one input bit flips each output bit half the time. It doesn't flip the other input bits. The numbers 0010, 1000, etc. are the output bits that flip; the first 0111, for instance, is 0001 xor 0110, from flipping 1000 to 1001. Rotating by the pop count is rotationally symmetric, so bit 0 is wlog. $\endgroup$ Apr 12, 2023 at 4:11
0
$\begingroup$

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.