What are the values of $w$ such that the corresponding $\text{Keccak-}f[25w]$ function is invertible (bijective)?

Question

From this answer, I see that from a mathematical point of view, one could define the $\text{Keccak-}f[25w]$ permutation for an arbitrary value of $w$.

I am interested in the following question: disregarding all properties of the resulting function except the invertibility (because $\text{Keccak-}f[25w]$ is required to be a permutation), is it true that if the value of $w$ is a multiple of $8$ and not a multiple of $5$, the corresponding $\text{Keccak-}f[25w]$ function is invertible (and bijective)? If the answer is “No”, then how to determine whether a particular $w$ is suitable (assuming that $w$ is required to be a multiple of $8$)?

Answer 1

$\operatorname{Keccak-}\!f[25w]$ is defined, by the Keccak specification, only when $w = 2^\ell$ for some $\ell$, and in all such cases it is a permutation. The choices 1, 2, and 4 for $w$ are not multiples of 8. No multiple of 5 is a power of 2 and consequently $w$ is never a multiple of 5.

Answer 2

Regarding Keccak-f[25w] I’m assuming that you’re referring to changing the total number of lanes (25 as outlined in the standard) and not changing the 64-bit lanes size. Changing the lane count, as stated in the previous answer regarding a change in the lane size, would also result in a non-standard version of Keccak. To the extent that modification of the source code would be required to execute the function.

Your question is directed specifically at the viability of inversion given a deviation from the 25 lane standard.

Is it true that if the value of w is a multiple of 8 and not a multiple of 5, the corresponding Keccak-f[25w] function is invertible?

The above statement is false. If the total lane count is a multiple of 5 Keccak-f[25w] will be invertible, with the understanding that arbitrary constants can be added at the pi, rho, and iota steps. Essentially a total lane count being a multiple of 5 is required to maintain continuity with steps theta and chi. If the total lane count is even there might be some issues with pi, because rotational symmetry might be broken.

Issues will be caused when there is a total lane count that is NOT a multiple of 5. If the total lane count is prime the s-box definition of chi will need to extend to the full lane count. I would probably write a test for the largest factor that isn’t equal to the total lane count. How this affects the statistical properties of chi after considering state truncation would require further analysis. With theta things started getting interesting. An arbitrary lane count change could be added to theta without affecting its forward derivation. By the bit-twisting definition of theta applied with the extension of the 1:11 indexing relationship. In the reverse direction you will encounter the same issue if the lane count is prime. Now even if the lane count is NOT prime and you leverage the largest factor not including itself, there will be a computational resource issue as a result of the nature with which theta is inverted. Then again my theta inversion implementation could be a black boxed version of something glaringly simple. And always remember the print() statement is not necessarily truth.

Addressing below comment:

Keccak can be inverted as long a the lane width is an even number so w=8,16,48,64... are all viable sizes assuming you're comfortable throwing in some random bits to account for the reduced size of iota. I however wouldn't be able to invert Keccak when w > 1000.