4
$\begingroup$

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)$?

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

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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