2011 Reports : Cryptology ePrint Archive Forum

Discussion forum for Cryptology ePrint Archive reports posted in 2011.
Please put the report number in the subject.

Error in Report 2011/516: Protecting AES with Shamir's Secret Sharing Scheme by Louis Goubin and Ange Martinelli

Posted by: **JPulkus** (IP Logged)

Date: 26 September 2011 09:53

At the end of section 3.1 the authors claim that affine component A of the AES S-box (which is the composition of inversion in GF(256) with an GF(2)-affine map that is NOT affine over GF(256)) can be simply implemented by applying the affine map A on the shares $y_i$ (ignoring the constant term of the affine map making it linear for simplicity's sake).

This is wrong.

As proof the authors claim that A(P) is a polynomial of degree d. A(P) can be interpreted as such a polynomial, but NOT as a polynomial of one variable over GF(256), ONLY as a polynomial in 8 variables over GF(2) when choosing a basis of GF(256) over GF(2). It is not clear at all, how to convert such a polynomial back to the form the authors need.

An easy way to see that replacing $y_i$ by $A(y_i)$ does NOT correspond to applying the affine map A to the secret value is by taking equation (1) of section 2.2:

The secret $a_0$ can be reconstructed given the shares $y_i$ by evaluating the sum $\sum_0^d y_i \cdot \beta_i$. Applying the affine map A on both sides (for simplicity, we assume again A to be linear over GF(2)) one gets $A(a_0) = A(\sum_0^d y_i \cdot \beta_i) = \sum_0^d A(y_i \cdot \beta_i)$.

As $A$ is NOT affine/linear over GF(256), in general $A(y_i \cdot \beta_i)$ does NOT equal $A(y_i) \cdot \beta_i$ and having $A(a_0)$ equal to $\sum_0^d A(y_i) \cdot \beta_i$ would be pure coincidence.

This is wrong.

As proof the authors claim that A(P) is a polynomial of degree d. A(P) can be interpreted as such a polynomial, but NOT as a polynomial of one variable over GF(256), ONLY as a polynomial in 8 variables over GF(2) when choosing a basis of GF(256) over GF(2). It is not clear at all, how to convert such a polynomial back to the form the authors need.

An easy way to see that replacing $y_i$ by $A(y_i)$ does NOT correspond to applying the affine map A to the secret value is by taking equation (1) of section 2.2:

The secret $a_0$ can be reconstructed given the shares $y_i$ by evaluating the sum $\sum_0^d y_i \cdot \beta_i$. Applying the affine map A on both sides (for simplicity, we assume again A to be linear over GF(2)) one gets $A(a_0) = A(\sum_0^d y_i \cdot \beta_i) = \sum_0^d A(y_i \cdot \beta_i)$.

As $A$ is NOT affine/linear over GF(256), in general $A(y_i \cdot \beta_i)$ does NOT equal $A(y_i) \cdot \beta_i$ and having $A(a_0)$ equal to $\sum_0^d A(y_i) \cdot \beta_i$ would be pure coincidence.

Please log in for posting a message. Only registered users may post in this forum.