English: PDF

Abstract

We present algorithms for solving the restricted extended affine equivalence (REA-equivalence) problem for any \( m \)-dimensional vectorial Boolean function in \( n \) variables. The best of them has complexity \( O(2^{2n+1}) \) for REA-equivalence \( F(x) = M_1 \cdot G(x \oplus V_2) \oplus M_3 \cdot x \oplus V_1 \). The algorithms are compared with previous effective algorithms for solving the linear and the affine equivalence problem for permutations by Biryukov et. al.