# Building blocks

This section introduces the main building blocks used in this chapter. They do not constitute an original contribution of this work but serve as prerequisites for our constructions.

## K-anonymity

The concept of k-anonymity was first described by Sweeney [186]. A subject is k-anonymous if it cannot be distinguished from at least *k —* 1 other subjects based on the information they reveal. Gruteser and Grunwald apply the concept to location information [92]: An individual is k-anonymous if it cannot be distinguished from at least *k —* 1 other subject based on the location samples (location and time) they reveal. They describe that k-anonymity can be achieved by reducing the spatial and temporal accuracy of the information revealed, until it applies to at least *k* parties.

## Shamir’s secret sharing

Shamir introduces the concept of a (k, n) threshold scheme, commonly known as “Shamir’s secret sharing” [173]. It allows to split a common secret *s* among *n *parties such that any *k* of them can reconstruct it. The secret *s* is only known to a central trusted party, which generates the shares and distributes them among the participants. The construction is based on a polynomial *f* (x) of degree *k —* 1 with random coefficients *a,i* such that *f* (0) = s:

Each of the *n* parties (n > k) is given one point of the polynomial (xi, *f (xi)) *while the polynomial itself is kept secret. When at least *k* of the *n* parties collaborate and contribute their share, they can reconstruct the polynomial using Lagrange interpolation and obtain *s* by evaluating *f* (0).