Paper 2014/1017

Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data

Foteini Baldimtsi and Olga Ohrimenko

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Financial Cryptography and Data Security (FC) 2015
Contact author(s)
foteini @ baldimtsi com
History
2014-12-29: received
Short URL
https://ia.cr/2014/1017
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/1017,
      author = {Foteini Baldimtsi and Olga Ohrimenko},
      title = {Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/1017},
      year = {2014},
      url = {https://eprint.iacr.org/2014/1017}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.