Problems on ANF equation?

Question

I tried to solve SBox as given in this link

I am trying to understand this paper SBox. In this on page no.4 the correct equation of given SBox is mentioned. I am not getting how to design ANF equation as given in paper.

Answer 1

Using the S-box package of SageMath used

S = SBox(1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14);

f0 = S.component_function(1)
f1 = S.component_function(2)
f2 = S.component_function(4)
f3 = S.component_function(8)

print ( "y0 = ", f0.algebraic_normal_form())
print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())

Return a Boolean function corresponding to the component function $b\cdot S(x)$.

and the output \begin{align} y_0 &= x_0 x_1 + x_0 + x_1 + x_2 + x_3 + 1\\ y_1 &= x_0 x_1 + x_0 x_2 + x_0 + x_2 + x_3\\ y_2 &= x_0 x_3 + x_1 x_2 x_3 + x_1 x_3 + x_1 + x_2\\ y_3 &= x_0 x_2 x_3 + x_0 + x_1 x_3\\ \end{align}

The blow the result of the article

\begin{align} s_0 &= 1 + a + b + ba + c + d \\ s_1 &= a + ba + c + ca + d\\ s_2 &= b + c + da + db + dcb\\ s_3 &= a + bd + dca\\ \end{align}

And the result form Conchild code \begin{align} y_0 &= 1 + x_0 + x_1 + x_0*x_1 + x_2 + x_3\\ y_1 &= x_0 + x_0*x_1 + x_2 + x_0*x_2 + x_3\\ y_2 &= x_1 + x_2 + x_0*x_3 + x_1*x_3 + x_1*x_2*x_3\\ y_3 &= x_0 + x_1*x_3 + x_0*x_2*x_3\\ \end{align}

Martin R. Albrecht provides another method with SageMath

from sage.crypto.sbox import SBox

S = SBox (1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14)
P.<y0 ,y1 , y2 ,y3 ,x0 , x1 ,x2 ,x3 > = PolynomialRing ( GF (2) , order ='lex')
X = [x0 ,x1 ,x2 , x3 ]
Y = [y0 ,y1 ,y2 , y3 ]
S. polynomials (X=X , Y=Y , degree =3 , groebner = True )

The result is compatible with the article but the $y_i$'s reversed.

[y0 + x0*x1*x3 + x0*x2 + x3,
 y1 + x0*x1*x2 + x0*x2 + x0*x3 + x1 + x2,
 y2 + x0 + x1*x3 + x1 + x2*x3 + x3,
 y3 + x0 + x1 + x2*x3 + x2 + x3 + 1]