Institute of Electrical & Electronic Engineers
In this paper, the authors present the first order-preserving scheme that achieves ideal security. Their main technique is mutable cipher-texts, meaning that over time, the cipher-texts for a small number of plaintext values changes, and they prove that mutable cipher-texts are needed for ideal security. Their resulting protocol is interactive, with a small number of interactions. They implemented their scheme and evaluated it on micro-benchmarks and in the context of an encrypted MySQL database application. They show that in addition to providing ideal security, their scheme achieves 1 - 2 orders of magnitude higher performance than the state-of-the-art order-preserving encryption scheme, which is less secure than their scheme.