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

| improve this answer | |
$\endgroup$
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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ And how do you make sure that the resulting $n$ bent functions in parallel is invertible? $\endgroup$ – poncho Jun 4 '17 at 22:52
  • $\begingroup$ Damn. I was just going to ask that... $\endgroup$ – Paul Uszak Jun 4 '17 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 '17 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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