# Why is this function bijective?

I cannot seem to understand why the function $$F$$ defined in Theorem 7.1 of the paper “Permutation rotation-symmetric Sboxes, liftings and affine equivalence” is described as “a bijection on $$\mathbb{F}_2^n$$”.

The input contains $$n$$ bits, yet the given definition seems to imply that the output contains $$k=n-2$$ bits: $$F(x_1, x_2, \ldots, x_n) = (f(x_1, \ldots, x_k), f(x_2, \ldots, x_{k+1}), \ldots, f(x_k, x_1, \ldots, x_{k-1})).$$

There is absolutely no way that such function can be bijective, so I must be missing some essential detail.

For example, can anyone demonstrate how to compute the value of, say, $$F(00001)$$?

• Note that being ’bijective’ doesn’t imply that there is an easy or even a known way to calculate both ways. Mar 11, 2022 at 20:55

It is simply a typo in the paper I believe. It should say: $$F(x_1, x_2, \ldots, x_n) = (f(x_1, \ldots, x_k), f(x_2, \ldots, x_{k+1}), \ldots, f(x_n, x_1, \ldots, x_{k-1})).$$
(Note the $$x_n$$ instead of $$x_k$$ in the final evaluation of $$f$$). This is what was written on page 1 of the paper, and has $$n$$-bit output.