Security and searchability in secret sharing-based data outsourcing

A major challenge organizations face when hosting or moving their data to the Cloud is how to support complex queries over outsourced data while preserving their confidentiality. In principle, encryption-based systems can support querying encrypted data, but their high complexity has severely limited their practical use. In this paper, we propose an efficient yet secure secret sharing-based approach for outsourcing relational data to honest-but-curious data servers. The problem with using secret sharing in a data outsourcing scenario is how to efficiently search within randomly generated shares. We present multiple partitioning methods that enable clients to efficiently search among shared secrets while preventing inference attacks on the part of data servers, even if they can observe shares and queries. Also, we prove that with some of our partitioning methods the probability of finding a correspondence between a set of shares and their original values is almost equal to that of a random guess. We discuss query processing for different types of queries including equality, range, aggregation, projection, join, and update queries. Our extensive experimentation confirms the practicality and efficiency of our approach in terms of query execution time, storage, and communication overheads.