Approximate distance-comparison-preserving symmetric encryption
We introduce approximate distance-comparison-preserving symmetric encryption (DCPE), a new type of function-preserving encryption that approximately preserves the relative distance between plain text vectors. DCPE is naturally suited for executing nearest-neighbor search on encrypted data.
We study what security DCPE can provide and how to construct it. We first show that, somewhat unsurprisingly, the 'ideal' security notion for DCPE is unachievable. But we propose by one-wayness and indistinguishability-style security notions that nevertheless capture meaningful guarantees. Based on a relation we uncover between approximate DCP functions and approximate distance-preserving functions, we design a DCPE scheme we call Transform Scale-And-Perturb (TSAP).
We then prove TSAP provides indistinguishability of sufficiently close arbitrary plaintexts and one-wayness of normally and uniformly distributed far plaintexts. In particular, TSAP hides frequency information, which is not possible even by 'ideal' order-revealing encryption (Boneh et al., EUROCRYPT 2015) which was a predecessor to DCPE.
Join via zoom
Riddhi Ghosal (ISI Kolkota)
Riddhi Ghosal is currently pursuing a Masters of Statistics from the Indian Statistical Institute, Kolkata, India. Prior to this he completed a Bachelor in Statistics from the same Institute. He's interested in the intersection between privacy, cryptography, theoretical statistics and machine learning. In particular, his research interests include functional encryption, differential privacy, privacy-preserving machine learning and foundations of cryptography.