Order-Revealing Encryption
crypto.stanford.edu
crypto.stanford.edu
But be very very careful about ever using it ( and really any cryptography that does more than standard encryption/ signing) in practice without understanding the security it provides. Revealing element order can in fact reveal most of your data set in some cases. There are cases where leaking order is safe and very useful and there are cases where it is not safe despite there being nothing cryptographically "wrong" with the scheme.
(Edited) To give an example: although not the exact same primitive,some Order Preserving Encryption schemes leak square root(n) bits where n is the bit length of your plaintext[0]. For social security numbers, this would mean you loose about 5 bits of entropy and there are only 10 or 11 bits to start with in many cases[1].
And as they say, attacks only get better and people are actively working on attacks using order leakage[2].
Just because something is provably secure doesn't mean it is the right kind of secure for your application. Crypto is not pixie dust. You actually need to understand the exact guarantees something provides.
[0]http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf [1]http://www.pnas.org/content/106/27/10975.full.pdf [2]https://twitter.com/hackermath/status/741054948612308992
A contrived example to demonstrate this is if you published some kind of database about behavior observed from IP addresses, but using ORE-encrypted IP addresses instead of plaintext ones. If the database explicitly contains all 2³² IPv4 addresses, someone can then perform a series of comparisons to sort the entire database (which is an explicit goal of ORE), which then reveals the plaintext values because they're exactly equal to the positions of the entries in the sorted list!
A subtler case could arise if the database is complete for some range of IP addresses and an attacker happens to know the plaintext values at the bottom and top of that range. Then the attacker can learn the plaintext values of everyone else in the range.
An even subtler case could arise if the attacker simply knows a bunch of specific plaintext values. In that case, the attacker can learn constraints on the numeric values of other database entries, which could mean, for example, learning the first 1-2 bytes of a particular IP address, which could confirm or disconfirm hypotheses about a user's ISP or geographic location.
Edit: I'd like to see some of the more subtle attack ideas that the people you linked to are developing!
The bottom line is beware of academics baring leakage functions. Their work often has considerable merit, but one must be very careful about how it's used in practice.
In the mean time, here's a paper from some folks in Norway that shows attacks against two prefix-preserving IP address anonymization schemes:
- the things you are encrypting are not numbers, or
- your scheme is not as secure as you would like it to be,
where the second point means that necessarily there is some information leakage: that is, more than just their order can be derived from ciphertexts. This is not necessarily bad; the questions is what it is that is leaked, and if that is harmful to your situation.
The website links to two papers, one for each of the above categories, of which only the second one is sufficiently efficient to be of any use. Apart from the order of two ciphertexts, it reveals the index of the first bit at which the ciphertexts differ.
I do not believe there's any data that cannot be represented as a number, so this point confuses me.
I also wonder if there's a way to make that statement of when this causes something to be revealed more mathematically precise... maybe it's something that could even be automatically detected by someone with access to the original data?
Unfortunately, that turned out not to be a hard-and-fast distinction because things that are not unique in isolation are often unique in combination.
https://en.wikipedia.org/wiki/Quasi-identifier
The Netflix deanonymization paper discusses how things (how much you like a movie) that are very non-unique in isolation can be very unique when you have an extremely large number of them. Arvind Narayanan (one of the authors) has given a few discussions of the problem of dimensionality for privacy; one way of thinking of it is that there's an unfathomably large amount of volume in a very high-dimensional space, so there's an extremely large amount of opportunity for points in it to be very far away from each other, even if there's nothing especially "atypical" about the individual points.
This is closely related to the "curse of dimensionality"
https://en.wikipedia.org/wiki/Curse_of_dimensionality
although the curse is often stated from the analyst's perspective when hoping to find patterns, whereas the phenomenon Narayanan is describing is more from the perspective of the individual whose data are in a database and who hopes to appear similar to other individuals in order to retain anonymity, yet turns out to be very distinctive merely because of the number of dimensions.
This would be a very, very popular web site.
I've been thinking for a while now about what could be accomplished with partial steps towards homomorphic encryption. ORE is an interesting twist on homomorphic encryption that I hadn't thought of before --- one can merely sort encrypted data. I wonder what sorts of unexpected things one might be able to do with the ability to sort encrypted data?
> In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else.
It's not clear that this is "efficient"; it might be somewhat computationally intensive. But you can do it using only public information and without being able to decrypt the data.