International Association
for Cryptologic Research

We study the problem of private outsourced sorting of encrypted

data. We start by proposing a novel sorting protocol that allows a user to 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. To perform the sorting the server is assisted by a secure coprocessor with 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

non-colluding. We formally define private outsourced sorting and provide an efficient construction that is based on semi-homomorphic encryption.

As an application of our private sort, we present MSRE: 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. To construct MSRE we use searchable encryption techniques combined with our new private sort framework. Finally, although not discussed in this work, we believe that our private sort framework can turn out to be an important tool for more applications that require outsourced sorting while maintaining data privacy, e.g., database queries.