Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

From what I've been reading, Keccak's round function is reversible. That's pretty obvious for the $\rho$, $\pi$ and $\iota$ transforms. For $\chi$ to be reversible, $x$'s range has to be odd — but that's alright since Keccak's $x$ has a range of 5. Yet, what criteria make the theta step reversible?

Checking some small $x$, $y$ and $z$ ranges, it shows that:

  • where [x][y][z]'s ranges are [3][3][2], $\theta$ is not reversible, and
  • where [x][y][z]'s ranges are [3][3][3], $\theta$ is not reversible either.

So, what makes the $\theta$ for (eg) [5][5][64] reversible?

share|improve this question
1  
Playing around with it, I've come to the suspicion that $\theta$ is invertible except when $x$ is odd and $y$ is a multiple of 3. I don't have a proof of that, though... –  poncho Aug 14 '13 at 16:57
    
@poncho I was tending towards the same suspicion, but am also lacking proof or at least some reasonable hints. In fact, that was the reason why I asked. ;) Thanks anyway… as always — appreciate your feedback. [+1] –  e-sushi Aug 14 '13 at 17:02
1  
Nope, it turns out to be more subtle than I thought: $x$ odd, $y=5$ and $z=15$ also turns out to be noninvertible. I'm pretty sure I can prove that, in the $y=5$ case, that $\theta$ is invertible unless $x$ is odd and $z$ is a multiple of 15. –  poncho Aug 14 '13 at 20:58
add comment

1 Answer

up vote 7 down vote accepted

I went through it, and while this isn't a complete answer, which should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index)

First rule: if $x$ is even, then $\theta$ is invertible. The proof of that is actually fairly elegant; however it's also rather irrelevant to Keccak (because even if you were going to tweak Keccak, the $\chi$ step requires $x$ to be odd).

Now, from here on down, we'll assume $x$ is odd.

Here is how it works; there is a function $L(y)$ that maps the range of $y$ into a set of integers; $\theta$ with the parameters $(x, y, z)$ is invertible iff $z$ is not a multiple of any of the integers within the set $L(y)$

$L(y)$ also has the property that $L(a) \cup L(b) \subset L(ab)$

Here is the list of $L(y)$ for $y<38$:

$L(2^n) = \emptyset$

That is, if $y$ is a power of 2, $\theta$ is always invertible

$L(3n) = \{ 1 \}$

What that means is that, since all values of $z$ are multiples of 1, then $\theta$ is never invertible if $y$ is a multiple of 3.

$L(5) = \{ 15 \}$

In the Keccak case, the actual value of $z = 64$ is not a multiple of 15, and hence $\theta$ is invertible.

$L(7) = \{ 7 \}$

$L(10) = \{ 15 \}$

$L(11) = \{ 341 \}$

$L(13) = \{ 819 \}$

$L(14) = \{ 7 \}$

$L(17) = \{ 85 \}$

$L(19) = \{ 9709 \}$

$L(20) = \{ 15 \}$

$L(22) = \{ 341 \}$

$L(23) = \{ 2047 \}$

$L(25) = \{ 15 \}$

$L(26) = \{ 819 \}$

$L(28) = \{ 7 \}$

$L(29) = \{ 475107 \}$

$L(31) = \{ 31 \}$

$L(34) = \{ 85 \}$

$L(35) = \{ 7, 15 \}$

$L(37) = \{ 3233097 \}$

Now, there are certain obvious regularities with above listed $L$ function values; for example, if $y$ is prime other than 2, then every $L(y)$ listed consists of a single element which is a divisor of $2^{y-1}-1$; and in every case listed, we have $L(ab) = L(a) \cup L(b)$; however I cannot prove either of those observations hold in general.

share|improve this answer
    
Personally, I can live without that proof. Your answer provides ample base for me to fiddle out the rest of it. Thanks - I've gladly accepted this answer. Oh, and a [+1] for the time you've invested. –  e-sushi Aug 16 '13 at 2:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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