Keep a Few: Outsourcing Data While Maintaining Confidentiality

The authors put forward a novel paradigm for preserving privacy in data outsourcing which departs from encryption. The basic idea behind their proposal is to involve the owner in storing a limited portion of the data, and maintaining all data (either at the owner or at external servers) in the clear. They assume a relational context, where the data to be outsourced is contained in a relational table. They then analyze how the relational table can be fragmented, minimizing the load for the data owner. They propose several metrics and present a general framework capturing all of them, with a corresponding algorithm finding a heuristic solution to a family of NP-hard problems.