Privacy-preserving data splitting is a technique that aims to protect data privacy by storing different fragments of data in different locations. In this work we give a new combinatorial formulation to the data splitting problem. We see the data splitting problem as a purely combinatorial problem, in which we have to split data attributes into different fragments in a way that satisfies certain combinatorial properties derived from processing and privacy constraints. Using this formulation, we develop new combinatorial and algebraic techniques to obtain solutions to the data splitting problem. We present an algebraic method which builds an optimal data splitting solution by using Gr " o bner bases. Since this method is not efficient in general, we also develop a greedy algorithm for finding solutions that are not necessarily minimal sized.
Existing approaches for protecting sensitive information outsourced at external “honest-but-curious” servers are typically based on an overlying layer of encryption applied to the whole database, or on the combined use of fragmentation and encryption. In this paper, we put forward a novel paradigm for preserving privacy in data outsourcing, which departs from encryption. The basic idea is to involve the owner in storing a limited portion of the data, while storing the remaining information in the clear at the external server. We analyze the problem of computing a fragmentation that minimizes the owner's workload, which is represented using different metrics and corresponding weight functions, and prove that this minimization problem is NP-hard. We then introduce the definition of locally minimal fragmentation that is used to efficiently compute a fragmentation via a heuristic algorithm. The algorithm translates the problem of finding a locally minimal fragmentation in terms of a hypergraph 2-coloring problem. Finally, we illustrate the execution of queries on fragments and provide experimental results comparing the fragmentations returned by our heuristics with respect to optimal fragmentations. The experiments show that the heuristics guarantees a low computation cost and is able to compute a fragmentation close to optimum.