Fuchsbauer, G., Ghosal, R., Hauke, N., & O’Neill, A. (2022). Approximate Distance-Comparison-Preserving Symmetric Encryption. In Security and Cryptography for Networks (pp. 117–144). https://doi.org/10.1007/978-3-031-14791-3_6
We introduce distance-comparison-preserving symmetric encryption (DCPE), a new type of property-preserving encryption that preserves relative distance between plaintext vectors. DCPE is naturally suited for nearest-neighbor search on encrypted data. To boost security, we divert from prior work on Property Preserving Encryption (PPE) and ask for approximate comparison, which is natural given the prevalence of approximate nearest neighbor (ANN) search. We study 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 for Euclidean distance we call Scale-And-Perturb (SAP ). The encryption algorithm of our core scheme processes plaintexts on-the-fly. To further enhance 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 that SAP achieves a suitable indistinguishability-based security notion we call real-or-replaced indistinguishability (RoR ). In particular, our RoR result implies that our scheme prevents a form of membership inference attack. 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 (OW) analysis. Finally, carefully combining our OW and RoR results, we are able characterize bit-security of SAP. Overall, we find that our DCPE scheme not only has superior bit-security to Order Preserving Encryption (OPE) but resists relevant attacks that even ideal order-revealing encryption (Boneh et al., EUROCRYPT 2015) does not.
