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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Ella Rose Nov 8 '16 at 20:55
  • $\begingroup$ 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 $\endgroup$ – Mikhail Goltvanitsa Nov 9 '16 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.