Syllabus Lesson 136 of 156 · Privacy tech beyond blocking
Privacy tech beyond blocking

Secure aggregation

Why it matters A fitness app wants the total steps walked in a city; a keyboard maker wants to know how often a word is typed across all phones. In each case the company needs one number from many devices. Secure aggregation lets it learn that total without ever seeing any single person's value, and it is surprisingly simple.

Teaching crypto, not secure: the numbers in this module's labs are small enough to read and the randomness is seeded so grading is repeatable. Real systems use vetted libraries and far larger numbers. Never copy teaching code into a product.

The salary trick

Three friends want their average salary without anyone revealing their own. The first adds a big random number to her salary and whispers the result to the second. He adds his salary and whispers on. The third adds hers and passes it back. The first subtracts her random number, and out comes the total. Each whisper looked like a random number to whoever heard it.

Secure aggregation: computing a total (or average) of many people's values so that no single value is revealed to anyone, including the server collecting them.

Additive secret sharing: cutting a secret number into several shares that look random on their own but add up to the secret. Any one share, or any group missing at least one share, reveals nothing about the secret.

How shares work

To split the number 7,350 into three shares, pick two random numbers and choose the third so that all three add up to 7,350. With wrap-round arithmetic (modulus M, here 2 to the 32, a bit over 4 billion), every share is a uniformly random number on its own:

M = 2 ** 32
s1, s2 = 3919211450, 120775123           # random
s3 = (7350 - s1 - s2) % M                # whatever makes it add up
print((s1 + s2 + s3) % M)                # 7350

Why wrap round? Without it, a share would sometimes be negative or suspiciously close to the secret. With it, every share value is equally likely whatever the secret is, so a single share carries no information.

Many devices, several servers

Now each phone splits its step count into one share per server and sends share 1 to server 1, share 2 to server 2, and so on. Each server adds up the shares it received. Each server's total still looks random. Only when the servers' totals are added together does the real city total appear. As long as the servers do not pool their raw shares for one phone, no phone's value is ever seen.

The real-world version

Systems used for training models across many phones (known as federated learning) use a cleverer variant with one server: pairs of devices agree on random masks that cancel out when everything is added up, plus extra steps to cope with phones that drop offline halfway. The core idea is the one you will build: random-looking pieces that only make sense together.

What secure aggregation does not do

The total is revealed exactly. If only two people contributed and one knows their own value, they can subtract it and learn the other's. If the total itself is sensitive, add differential privacy noise to it as well. The two tools work well together: aggregation hides the inputs, DP hides each person's effect on the output.

In other languages

Splitting in JavaScript, using 32-bit wrap-round with >>> 0 and the browser's secure random source:

function split(value, n) {
  const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
  const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
  shares.push((value - sum) >>> 0);
  return shares;
}

And in Rust, where wrapping_sub on a u32 does the wrap-round for you:

let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));

Recap

  • Secure aggregation reveals a total but no single contribution.
  • Additive secret sharing splits a value into random-looking shares that add up to it, using wrap-round arithmetic.
  • Each server sees only random-looking shares; only all server totals together give the answer.
  • The total itself is revealed exactly, so pair it with DP noise when the total could expose someone.
Your turn

Write three functions, using M (2 to the 32) from the practice world. split(value, n, rng) returns a list of n shares: the first n - 1 from rng.randrange(M), the last equal to (value - sum(shares)) % M. combine(shares) returns sum(shares) % M. aggregate(values, n_servers, rng) splits each value with split, adds share j into server_totals[j] (mod M), and returns a tuple (total, server_totals) where total = combine(server_totals).

Spotted a problem in this lesson? Report it

Code · runs in your browser
Output

        

      

      
      

        Back