How to do unmasked addition on SSS masked shares?

Question

I'm trying to understand how Shamir's Secret Sharing algorithm is applied to AES when doing threshold masking.

I understand how the secrets are created and the secret is calculated and I'm now trying to figure out how the math operations (that are needed for AES) work when you have the shares. To do that I'm reading this source: Goubin et al, Protecting AES with Shamir's Secret Sharing Scheme. (pages 79-94 in isbn 978-3-642-23951-9)

It says: addition of shares with an unmasked value: $$\{(x_i', y_i') \leftarrow (x_i,y_i \oplus u) | \forall (x_i, y_i) \in shares\}$$ Where $u$ is the to be added value and $(x_i, y_i)$ is an original share. Addition results in a new $(x_i', y_i')$ share.

I've implemented this in python (not in a finite field) in this way:

def add_unmasked(self, shares, value):
    return [{'x': share['x'], 'y': share['y'] ^ value} for share in shares]

However I don't see the correct results, if I have a secret of 20 being shared and unshared results it in 20, but if I add 1, I get the wrong result 80% of the time.

For completeness sake my code:

def create_shares(self, to_create):
    if to_create < self.degree + 1:
        raise Exception('shares don\'t cover the order')

    coefficients = self.generate_polynomial(self.degree, self.secret)

    points = random.sample(range(self.finite_field), to_create)
    shares = [{'x': point, 'y': sum(coefficient * point ** n for n, coefficient in enumerate(coefficients))} for
              point in points]

    return shares

def tell_secret(self, shares):
    # doing a polynomial interpolation using the basic definition. sum y * l where l is the product of x - xi / xm - xi. x is 0 in our case
    xs = [share['x'] for share in shares]

    y = 0
    for share in shares:
        l = 1
        for x in xs:
            if x != share['x']:
                l *= (- x) / (share['x'] - x)
        y += share['y'] * l
    return int(round(y))

---

edit: Reading wikipedia about the definitions of operators in a finite field, I've found this:

A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND.

AES uses a $GF(2)$ finite field, the Galois field $GF(2^8)$ So when my paper says: $\oplus$ they mean the addition operator for the finite field GF(2). This is confirmed by my test when doing an addition in my non finite field program.

---

edit 2:

As such I read this as doing a $GF(2^8)$ addition to all the shares. It is using the word XOR and I've read that it should be XOR in the finite field but when I do this in my testing program, I don't get the correct result. This seems to be because of at least one share having an y value which overflows with the addition.

---

edit 3:

So I've found the following lines in the referenced paper:

Our scheme maintains the same compatibility as Boolean masking with the linear transformations of the algorithm

So it seems that the paper proposes some kind of SSS mixed with boolean masking on an AES implementation. I still don't get it completely but I'm moving on and maybe if I come back to it later my understanding will have improved.

Answer 1

It seems that the question you're asking is about how to add a public (unmasked?) value to a secret-shared value. I suggest you edit the question a bit to clarify that this is not related to AES directly.

With that aside, adding a public value to a secret-shared value depends heavily on what secret-sharing scheme you're using, and also the algebraic structure where you're doing it, of course.

To secret-share a single bit $b$ using additive secret sharing, you sample random bits $b_1$ and $b_2$ constrained to $b=b_1\oplus b_2$. The pair of shares is then $(b_1,b_2)$. To add a publicly known bit $u$, you only need to add it to one of the shares, say to $b_2$, so the new shares are $(b_1, b_2\oplus u)$. You can check that if you add (i.e. XOR) these together then you get $b\oplus u$, so you effectively added $u$ to the secret.

If you're additively secret-sharing elements of $\mathsf{GF}(2^8)$ instead of single bits the principle is the same, except that XOR is replaced with addition in $\mathsf{GF}(2^8)$. Quite coincidentally though, addition in $\mathsf{GF}(2^8)$ is precisely component-wise XOR, but this didn't need to be the case, specially if you used instead, say, $\mathsf{GF}(3^8)$.

Now, all of this was for additive secret-sharing, but this is not how Shamir secret-sharing works. In this scheme, secret-sharing a value $s$ among $n$ parties with threshold $t$ consists of sampling a random polynomial $f(\mathtt{X})$ of degree at most $t$, constrained to $f(0)=s$, and letting the $i$-th share be $s_i=f(i)$.¹ With this secret-sharing scheme, adding a public value $u$ is done by letting each party (not only one) add this value to its share, getting $(f(1)+u,\ldots,f(n)+u)$ as the vector of shares. I encourage you to check why this is a valid Shamir sharing of $s+u$.

To sum up from the discussion above, I think you are mixing additive with Shamir secret-sharing. The method you described and implemented is for adding a public value to an additive sharing, yet you mention in the title and the text Shamir secret-sharing.

---

¹ Here, the "numbers" $0,1,\ldots,n$ that we are evaluating into the polynomial are simply symbols to represent different elements of the field you're considering, e.g. $\mathsf{GF}(2^8)$.