A building block: additive secret sharing

How can you compute on data that no one is supposed to see? One of the simplest building blocks of MPC is additive secret sharing. The idea: split each secret number into pieces that, on their own, tell you nothing.

Splitting a secret into random shares

Suppose Alice holds a secret salary s = 3200 and that there are three parties in total. Alice picks two numbers at random, for example r1 = 900 and r2 = 2500, then computes the last share so that the sum comes back to her secret:

part_1 = 900
part_2 = 2500
part_3 = s - r1 - r2 = 3200 - 900 - 2500 = -200

Check: 900 + 2500 + (-200) = 3200. Alice distributes one share to each party and keeps only one.

The crucial point: taken in isolation, a share like 900 is completely random. It reveals nothing about 3200. You need all the shares to reconstruct the secret.

Adding without ever recombining

The magic of additive sharing is that addition happens locally. Suppose three employees, each having shared their salary in the same way. Each party holds one share of each salary:

                  part de s_A   part de s_B   part de s_C
Partie 1 :           900           410           120
Partie 2 :          2500          1000           700
Partie 3 :          -200           190          1180

To obtain the sum of the salaries, each party simply adds up the shares it holds:

Partie 1 : 900 + 410 + 120  = 1430
Partie 2 : 2500 + 1000 + 700 = 4200
Partie 3 : -200 + 190 + 1180 = 1170

Then the three parties announce only these three totals and add them:

1430 + 4200 + 1170 = 6800

That is exactly the sum of the three salaries — without any individual salary ever having been revealed.

What is learned, what is hidden

In the end, everyone knows the sum 6800 (and therefore the average salary). But no one has seen the individual salaries: each share exchanged was a random number, and only the final sum was disclosed.

salaires privés --> parts aléatoires --> additions locales --> somme publique
   (cachés)           (rien visible)        (rien visible)       (résultat)

An honest limitation

Additive sharing makes addition trivial. The multiplication of two secret values, however, is far trickier and requires additional protocols (exchanges between parties). That is why more complex functions call for other techniques, covered in the next chapter.

In summary

Additive secret sharing splits each input into random shares distributed to the other parties. Addition is computed locally on the shares, and then only the result is recombined. This yields the sum of salaries without ever revealing the individual salaries.