Deterministic and Order-preserving Encryption (OPE)

Deterministic and Order-preserving Encryptions are sorts of partial encryptions that allow some types of operations (not all). These methods of encryption have been employed in academia in CryptDB and more recently in production in systems such as Unlike the methods mentioned above, these techniques are not truly secure in the way we define acceptable security for encryption and MPC, and they provide weaker guarantees. They are also limited in functionality. However, they are much easier to implement and are significantly faster.

To understand why these schemes are insecure, one needs to realize that they still leak a meaningful portion of the data. For example, OPE is defined as an encryption that preserves the ordering of the element. Specifically, given two ciphertexts c1, c2, corresponding to messages m1, m2 then if c1 < c2 so does m1 < m2. Now imagine that you have an encrypted column representing people’s age. Ages are integral types with a small range of typically 0–100. Given sufficiently many rows (even as little as 1000 should be enough), one could easily map back the encrypted values into integers with high accuracy and likelihood of being correct. Therefore, while tempting from an implementation perspective, these techniques are discouraged and are only brought here for completeness.


An Implementation of Order-Revealing Encryption

A prototype implementation of the order-revealing encryption (ORE) schemes described in the following papers: