# How to determine if a generalized $\sigma$ function (similar to what is defined in SHA-2) is invertible?

Let $$ROTR^n(x)$$ and $$SHR^n(x)$$ denote the rotate right (circular right shift) and the right shift operations, as defined in SHA-2 standard.

Consider any function of the form $$f(x) = ROTR^{n_1}(x) \oplus ROTR^{n_2}(x) \oplus \ldots \oplus ROTR^{n_z}(x).$$

According to the fifth element of this list, such functions are reversible (and bijective) if and only if the set $$\{n_1, n_2, \ldots, n_{z-1}, n_z\}$$ contains an odd number of elements (assuming that $$0 \le n_i \le w-1$$, where $$w$$ denotes the length of a word $$x$$). For example, $$\Sigma$$ functions in SHA-2 are of this form ($$z=3$$).

But I want to ask about functions of the form $$g(x) = F^{n_1}(x) \oplus F^{n_2}(x) \oplus \ldots \oplus F^{n_z}(x),$$ where $$F^n(x)$$ is either $$ROTR^n(x)$$ or $$SHR^n(x)$$ (assuming that $$0 \le n_i \le w-1$$ and $$w$$ denotes the length of a word $$x$$). How to determine if such function is reversible (for example, $$\sigma$$ functions in SHA-2 are of this form)?

• Why don't you start with figuring out how to reverse $x \oplus (x \gg 1)$? – Squeamish Ossifrage Apr 17 '19 at 16:20
• @SqueamishOssifrage: I am not asking how to reverse anything. This question is the following: given the description of $g(x)$, how to determine if the function is reversible (bijective)? For example, SHA-2 uses $g(x) = ROTR^{7}(x) \oplus ROTR^{18}(x) \oplus SHR^{3}(x)$ for 32-bit words. How to determine if this function is reversible (I am not asking for an explanation of how to reverse it)? – lyrically wicked Apr 19 '19 at 6:08