Sorting and Searching Behind the Curtain

We propose a framework where a user can outsource his data to a cloud server in an encrypted form and then request the server to perform computations on this data and sort the result. Sorting is achieved via a novel protocol where the server is assisted by a secure coprocessor that is required to have only minimal computational and memory resources. The server and the coprocessor are assumed to be honest but curious, i.e., they honestly follow the protocol but are interested in learning more about the user data. We refer to the new protocol as private outsourced sorting since it guarantees that neither the server nor the coprocessor learn anything about user data as long as they are noncolluding. We formally define private outsourced sorting and present an efficient construction that is based on an encryption scheme with semi-homomorphic properties. As an application of our private sort we present MRSE: the first scheme for outsourced search over encrypted data that efficiently answers multi-term queries with the result ranked using frequency of query terms in the data, while maintaining data privacy.