An Ideal-Security Protocol for Order-Preserving Encoding

By Raluca Ada Popa, Frank H. Li, Nickolai Zeldovich. IEEE Symposium on Security and Privacy, 2013

407 citations recorded by the source corpus.

Order-preserving encryption - an encryption scheme where the sort order of ciphertexts matches the sort order of the corresponding plaintexts - allows databases and other applications to process queries involving order over encrypted data efficiently. The ideal security guarantee for order-preserving encryption put forth in the literature is for the ciphertexts to reveal no information about the plaintexts besides order. Even though more than a dozen schemes were proposed, all these schemes leak more information than order. This paper presents the first order-preserving scheme that achieves ideal security. Our main technique is mutable ciphertexts, meaning that over time, the ciphertexts for a small number of plaintext values change, and we prove that mutable ciphertexts are needed for ideal security. Our resulting protocol is interactive, with a small number of interactions. We implemented our scheme and evaluated it on microbenchmarks and in the context of an encrypted MySQL database application. We show that in addition to providing ideal security, our scheme achieves 1 - 2 orders of magnitude higher performance than the state-of-the-art order-preserving encryption scheme, which is less secure than our scheme.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/9cd446663741a069f23e7a544bece60b14205586

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Generic Attacks on Secure Outsourced Databases (2016, background): “…indexing (e.g. [27, 29, 28]), (ii) order-preserving encryption schemes that use deterministic encryption which ensures that the order of the cypher-texts is the same as the order of the plaintexts (e.g. [1, 7, 41]), and (iii) solutions that use specialized data structures (e.g. [35, 44, 17]).”
M2R: Enabling Stronger Privacy in MapReduce Computation (2015, background): “CryptDB [47] takes a purely cryptographic approach, showing the practicality of using partially homomorphic encryption schemes [3, 15, 45, 46, 54].”
Inference Attacks on Property-Preserving Encrypted Databases (2015, neutral): “Note that the attacks only make use of order information so they work even against columns encrypted with ORE [14] and interactive order-preserving protocols [29,34].”
All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption (2016, background): “Addressing these challenges may require exploring new directions, such as interactive protocols [17] or multiple servers.”