Provable Security for Outsourcing Database Operations

Database outsourcing, whilst becoming more popular in recent years, is creating substantial security and privacy risks. In this paper, we assess cryptographic solutions to the problem that some client party (Alex) wants to outsource database operations on sensitive data sets to a service provider (Eve) without having to trust her. Contracts are an option, but for various reasons their effectiveness is limited [2]. Alex would rather like to use privacy homomorphisms [6], i.e., encryption schemes that transform relational data sets and queries into ciphertext such that (i) the data is securely hidden from Eve; and (ii) Eve computes hidden results from hidden queries that Alex can efficiently decrypt. Unfortunately, all privacy homomorphisms we know of lack a rigorous security analysis. Before they can be used in practice, we need formal definitions that are both sound and practical to assess their effectiveness.