3. Data Publishing: Trading Off Privacy with Utility Through the k-Jump Strategy

In this chapter, we study the side channel leak of sensitive micro-data in which adversaries combine the published data with their knowledge about the generalization algorithms used to produce such data, in order to refine their mental image about the sensitive data. Today, data owners are usually expected to disclose micro-data for research, analysis, and various other purposes. In disclosing micro-data with sensitive attributes, the goal is usually twofold. First, the data utility of disclosed data should be preserved to a certain level for analysis purposes. Second, the private information contained in such data must be sufficiently hidden. Typically, a disclosure algorithm would first sort potential generalization functions into a predetermined order (e.g., with decreasing utility), and then discloses data using the first generalization function that satisfies the desired privacy property. Knowledge about how such disclosure algorithms work can usually render the algorithm unsafe, because adversaries may refine their guesses of the sensitive data by “simulating” the algorithms and comparing with the disclosed data. In this chapter, we show that an existing unsafe algorithm can be transformed into a large family of safe algorithms, namely, k-jump algorithms. We then prove that the data utility of different k-jump algorithms is generally incomparable, which is independent of utility measures and privacy models. Finally, we analyze the computational complexity of k-jump algorithms, and confirm the necessity of safe algorithms even when a secret choice is made among algorithms.