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).