Is it possible to encrypt data points but still be able to select the ones "near" a given value? We have an application where we would like to store "encrypted" data points (as in, not being able to know the original - plaintext - data just by looking at the stored - encrypted - version of it) but still be able to ask the running system for all data points up to a certain distance from a given point. We don't want to decrypt the whole dataset and compute distances on plaintext data, of course. On the other hand, we don't even need a way to actually decrypt data and get back at the original data points.

Practical monodimensional example:


let A=2, B=5, C=8 (numbers are our "plaintext", letters are just identifiers)
we store encrypted versions of the data, so if you stole our persistent storage you know we have three points A, B, C but you can't know they actually have values 2, 5, 8
we want to ask the system for "all data points up to a distance of 3 starting from an origin point = 6" and the answer should be [B, C]
we won't ever need to be able to go back from A,B,C to 2,5,8
ideally this should be possible to extend to n dimensions, or at least two or three dimensions


About the purpose: improve security of our system in case of any successful attack. We don't need to actually know that data (as long as we can compute which data points are inside a maximum distance from a given, known point) but it's also not a problem if we do know them. What we're trying to improve on is what data an attacker would have access to if he ever succeed in compromising our systems (either getting copies of data at rest on persistent storage - a simple disk encryption would take care of that - or by getting access to an actually running system).

Speed is not a problem, we're not in an hurry. We want to minimize as much as possible the cleartext we have on the running system.
Ideally: receive data, encrypt and store it, forget about cleartext and do not need to see it again to compute its distance from a center point.

Is there any technique that allows that? Is it even theoretically  possible?
No, a cryptosystem can't do what's asked.

Proof: if one can precisely answer queries of the form "how many data points up to a distance of $3$ starting from an origin point = $n$" (a subset of what's wanted) for any value of $n$ with $|n|\le m+3$, and each point has integer value $v$ with $|v|\le m$, then one can find exactly the value of all the points in the set with at most $2m+1$ queries (with $n$ going from $m+3$ down to $-m+3$, each revealing if $v=n-3$ belongs to the set).

Thus in order to make the problem in the question tractable, one must use much larger integers (so that the necessary number of queries or work becomes infeasible), or/and heavily limit the number of queries an adversary can make, or/and introduce some fuzziness in the answers, or/and (as pointed by otus in comment) introduce the notion that some of the query is sent somewhat "enciphered" to the holder of the database. And it might well be that no practical system is possible.