Paper 2021/1666

Approximate Distance-Comparison-Preserving Symmetric Encryption

Georg Fuchsbauer, Riddhi Ghosal, Nathan Hauke, and Adam O'Neill

Abstract

We introduce distance-comparison-preserving symmetric encryption (DCPE), a new type of property-preserving encryption (PPE) that preserves relative distance between plaintext vectors. DCPE is naturally suited for nearest-neighbor search on encrypted data. To achieve meaningful security, we divert from prior work on PPE and ask for approximate correctness, which is natural given the prevalence of approximate nearest neighbor (ANN) search. We conduct a thorough study of what security approximate DCPE can provide and how to construct it. Based on a relation we prove between approximate DCP and approximate distance-preserving functions, we design our core approximate DCPE scheme we call Scale-And-Perturb ($\mathsf{SAP}$). The encryption algorithm of $\mathsf{SAP}$ processes data on-the-fly. To boost security, we also introduce two preprocessing techniques: (1) normalizing the plaintext distribution, and (2) shuffling, wherein the component-wise encrypted dataset is randomly permuted. We prove (under suitable restrictions) that $\mathsf{SAP}$ achieves an indistinguishability-based security notion we call Real-or-Replaced ($\mathsf{RoR}$). In particular, our $\mathsf{RoR}$ result implies that our scheme prevents membership inference attacks by Yeom et al. (CSF 2018). Moreover, we show for i.i.d. multivariate normal plaintexts, we get security against approximate frequency-finding attacks, the main line of attacks against property-preserving encryption. This follows from a one-wayness $(\mathsf{OW})$ analysis. Finally, carefully combining our $\mathsf{OW}$ and $\mathsf{RoR}$ results, we are able characterize bit-security of $\mathsf{SAP}$. Our overall findings are that our scheme not only has superior bit-security to OPE but resists specific attacks that even ideal order-revealing encryption (Boneh et al., EUROCRYPT 2015) does not. This suggests it could be sufficient for certain ANN applications, a subject on which we encourage further study.