Leakage-free order-preserving encryption

Abstract

Embodiments implement leakage-free order-preserving encryption by assigning a distinct ciphertext for each plaintext, including repeated plaintext whose ciphertext is randomly inserted. In order to conceal insertion order, the randomized ciphertexts are compressed to minimal ciphertext space. A uniform distribution is achieved by rotating about a modulus on the ciphertexts rather than the plaintexts. The resulting ciphertext distribution has no leakage from the ciphertexts—even if an adversary has perfect background knowledge on the distribution of plaintexts. The encryption may be further secured even against passive query monitoring attacks by hiding the access pattern using ϵ, δ-differential privacy, such that the adversary observing a sequence of queries will not learn the frequency of plaintext. The leakage-free order-preserving encryption may be converted into an adjustable encryption scheme to allow querying (e.g., on a remote server).