2
$\begingroup$

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and the output z of the rijndael sbox.

Then they say in A.1 that it is possible to get "not only" 23 bi-affine but 39 fully quadratic equations. And they further describe that the additional 16 equations come from a) $x^4y = x^3$ and b) $y^4x = y^3$. ($y = x^{-1}$ is the result of the inversion in the sbox)

I assume they produce these 16 equations in the very same way how they generated the 23 bi-affine equations (which is described here providing more details):

  1. They transform/rearrange the equations a) and b) to have 0 on one side.
  2. Then they "split" each equation a) and b) in 8 equations for each coefficient, so we have 16 equations in total for both a) and b).
  3. Then they substitute all the $y_i$ using the affine transformation of the sbox: $$ z = M\cdot y + \textrm{63}_{16} \\ y = M^{-1}\cdot z + M^{-1} \cdot \textrm{63}_{16} \\ = M^{-1}\cdot z + \textrm{05}_{16} \\ $$ which resolves to: $$\begin{cases} y_7 = z_{1} + z_{4} + z_{6} \\ y_6 = z_{0} + z_{3} + z_{5} \\ y_5 = z_{2} + z_{4} + z_{7} \\ y_4 = z_{1} + z_{3} + z_{6} \\ y_3 = z_{0} + z_{2} + z_{5} \\ y_2 = z_{1} + z_{4} + z_{7} + 1 \\ y_1 = z_{0} + z_{3} + z_{6} \\ y_0 = z_{2} + z_{5} + z_{7} + 1 \\ \end{cases} $$

I hope these steps are correct, but this way I get to the same 23 bi-affine equations as listed in the papers 1 and 2.

If I do this with a) and b) I get the following result (only one equation out of 16 as example): $$ 0 = x_{1}^{4} z_{0} + x_{6}^{4} z_{0} + x_{0}^{4} z_{1} + x_{1}^{4} z_{1} + x_{2}^{4} z_{1} + x_{7}^{4} z_{1} + x_{1}^{4} z_{2} + x_{2}^{4} z_{2} + x_{4}^{4} z_{2} + x_{6}^{4} z_{2} + x_{6}^{4} z_{3} + x_{7}^{4} z_{3} + x_{0}^{4} z_{4} + x_{1}^{4} z_{4} + x_{3}^{4} z_{4} + x_{4}^{4} z_{4} + x_{5}^{4} z_{4} + x_{7}^{4} z_{4} + x_{1}^{4} z_{5} + x_{3}^{4} z_{5} + x_{4}^{4} z_{5} + x_{5}^{4} z_{5} + x_{0}^{4} z_{6} + x_{1}^{4} z_{6} + x_{2}^{4} z_{6} + x_{3}^{4} z_{6} + x_{4}^{4} z_{6} + x_{6}^{4} z_{6} + x_{3}^{4} z_{7} + x_{5}^{4} z_{7} + x_{6}^{4} z_{7} + x_{5}^{4} + x_{7}^{4} + x_{2}^{2} x_{3} + x_{1} x_{3}^{2} + x_{3} x_{4}^{2} + x_{4}^{3} + x_{1}^{2} x_{5} + x_{3}^{2} x_{5} + x_{1} x_{5}^{2} + x_{2} x_{5}^{2} + x_{4} x_{5}^{2} + x_{3}^{2} x_{6} + x_{4}^{2} x_{6} + x_{0} x_{6}^{2} + x_{2} x_{6}^{2} + x_{5} x_{6}^{2} + x_{0}^{2} x_{7} + x_{2}^{2} x_{7} + x_{5}^{2} x_{7} + x_{6}^{2} x_{7} + x_{0} x_{7}^{2} + x_{3} x_{7}^{2} + x_{5} x_{7}^{2} + x_{6} x_{7}^{2}\\ $$

I would assume that every exponent $\neq 0$ of any $x_i$ and $z_i$ can be ignored because those variables representent coefficients in $GF(2)$ and can be either $0$ or $1$. *

So when I ignore the exponents this looks very similar to the bi-affine equations (a sum of combinations of $x_i$ and $y_i$, sometimes with terms of only $x_i$ or $y_i$ - the only thing which is new is that there are terms of $x_i$ and $x_j$ multiplied together) and I would like to understand the difference!

So how are these equations "fully quadratic" and what does it mean exactly? What is the difference to the bi-affine equations besides the number of the equations?


*: This was also necessary in the process of generating the 23 bi-affine equations, where the equation $x^{128} = y^{128} x$ was used. This led to $x_i^{128}$ in the result which to my understanding can also be shortened to $x_i$.

$\endgroup$
2
$\begingroup$

Looking at appendix A of the eprint I'd say that the authors call a polynomial of algebraic degree at most $2$ bi-affine, if it contains some terms of algebraic degree $1$, and fully quadratic, if there are no such terms.

(Working over fields of characteristic $2$ the map $x\mapsto x^2$ is linear over the field with two elements and of algebraic degree $1$.)

$\endgroup$
  • $\begingroup$ Thank you, this makes sense to me. But when I calculate all the 16 "fully quadratic" equations in GF(2) like mentioned above, I also find a constant term in the very last equation - so it still confuses me. $\endgroup$ – rlsw Mar 11 at 10:06

Your Answer

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

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