What criteria make the theta step of Keccak's round function reversible?

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?

-
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
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

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.

-
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