Blind evaluation of nearest neighbor queries wherein locations of users are transformed into a transformed space using a plurality of keys

Abstract

Systems and techniques are described for blind evaluation of nearest neighbor queries. Locations of multiple users in an original space are received. The locations in the original space are encoded into encoded locations in a transformed space. A relative proximity of the encoded locations in the transformed space is maintained after the encoding. Multiple keys corresponding to the multiple users are generated. Each key enables a reverse transformation of an encoded user location in the transformed space to an original user location in the original space. The multiple keys are provided to the corresponding multiple users, and the encoded locations in the transformed space are provided to a device. An order of computations required to reverse transform the encoded locations in the transformed space to the locations in the original space in the absence of a key is greater than a computational threshold.