Privacy-preserving data splitting: a combinatorial approach

摘要

Privacy-preserving data splitting is a technique that aims to protect dataprivacy by storing different fragments of data in different locations. In thiswork we give a new combinatorial formulation to the data splitting problem. Wesee the data splitting problem as a purely combinatorial problem, in which wehave to split data attributes into different fragments in a way that satisfiescertain combinatorial properties derived from processing and privacyconstraints. Using this formulation, we develop new combinatorial and algebraictechniques to obtain solutions to the data splitting problem. We present analgebraic method which builds an optimal data splitting solution by usingGr"{o}bner bases. Since this method is not efficient in general, we alsodevelop a greedy algorithm for finding solutions that are not necessarilyminimal sized.