Approximate distance-comparison-preserving symmetric encryption

This event has now finished.
  • Date and time: Tuesday 23 June 2020, 3.30pm to 4.30pm
  • Location: Online
  • Admission: Free admission

Event details

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.

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.

Contact us

+44 (0)1904 325501
Department of Computer Science, University of York, York YO10 5GH