# Are there methods for finding not optimal but good linear approximations for functions?

I'm interested in finding the best, or maybe just a good linear approximation of the function $F^{(19)}: V_{56}\to V_8$, where $$\begin{array}{l} F^{(1)}(x_1,x_2,\ldots, x_7) = P(x_2+x_6); \\ F^{(2)}(x_1,\ldots,x_7) = F^{(1)}(x_2,\ldots,x_7,F^{(1)}(x_1,\ldots,x_7)), \\ F^{(3)}(x_1,\ldots,x_7) = F^{(1)}\left(x_3,\ldots,x_7, F^{(1)}(x_1,\ldots,x_7), F^{(2)}(x_1,\ldots, x_7) \right) \ldots \end{array}$$ Here $x_j\in V_8$, $P$ is a byte permutation and by $+$ we denote addition in $V_8$.

Are there methods for finding not optimal but good linear approximations for such a function?

• I am having some difficult determining exactly what your function is/how your function works. It looks like it maps a 56 bit input to an 8 bit output? – Ella Rose Nov 8 '16 at 20:55
• Ella Rose, you are right. The best linear approximation means finding $l' \in V_{56}, l'' \in V_8$ such that $P \{l'x + l''F^{(19)}(x) = 0\}$ is high – Mikhail Goltvanitsa Nov 9 '16 at 6:33