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.
The concept of k-anonymity was first described by Sweeney . 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 : 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” . 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).