Secure randomized data matching?

Question

This might be a dumb question but I will go for it.

Let's say we have a data set $D$ consisting of sensitive data, and we want to be able to match if a new piece of data $S$ already exists in $D$ ($S\stackrel{?}{\in} D$) or not, and we want to be able to know which of the entries matches $S$ in $D$.

Our approach consisted of a 1-way cryptographic hash such as SHA256. However, since the dataset is relatively small (about 4 million rows) we can easily reproduce the full dataset and in effect "decode" the original meaning of the hash.

So I was wondering if it exists and algorithm that takes two parameters

• $d,b$: is a pair of some sensitive data and
• $s_i$: a random salt $i$

a cryptographic algorithm $C$ and a comparator $M$ such that

$M(C(d, s_1), C(b, s_2)) = \text{true}$, if $d == b$,

and

$M(C(d, s_1), C(b, s_2)) = \text{false}$, if $d != b$

So does such an algorithm or anything similar exist?

Answer 1

I don't believe that it is possible given the requirements you've listed.

Let us consider an arbitrary $C, M$ that meets the requirement. To reveal the entire database, what an attacker can do is compute $C(d,s)$ for every possible $d$ (about 4 million, as you said); then, he can use $M$ to compare that to every value you actually have - this reveals everything.

To make this a solvable problem, you need to modify some assumption somewhere.

One way to address this is to prohibit an attacker from evaluating $C$ himself; we can define $C(d) = HMAC_k(d)$ for some secret key $k$. This is determanistic (and so $M$ is a simple bitstring compare; we're assuming that we want to publicly reveal precise matches anyways, and so that's not an issue).

Another way to address this is to prohibit an attacker from evaluating $M$ himself;. One way to do this is, for some large prime $p$ and generator of a large prime subgroup $g$, we can pick a secret exponent $k$; we'd publish $g$, $p$ and $K = g^k \bmod p$. We'd define $C(d, s) = (K^s, g^{s+d})$; we can't check if a particular $C$ corresponds to a specific $d$ if the Diffie-Hellman problem is hard. And, the comparison function $M( (K^s, g^{s+d}), (K^t, g^{t+b}))$ (which is the comparison of an encoded $d$ and an encoded $b$) would check if $(g^{s+d})^k \cdot K^t = (g^{t+b})^k \cdot K^s$; as $K=g^k$, this is equivalent to $g^{ks+kd} g^{kt} = g^{kt+kb}g^{ks}$ or $K^d = K^b$

Answer 2

If I understand the question correctly, you have some sensitive data -- say, a list L of social security numbers in some order -- and you want to somehow create and publish a file D from that list such that

• If the person has a piece of data S, to query a database D to see if S is in L and if so, the row number where S occurs in L.
• You don't want some attacker who obtains D to be able to reproduce the entire dataset.

If each piece of independently-queryable data is small (say, a 9-digit social-security number), then this can't be done. The attacker can simply query every possible social security number from 000-00-0000 to 999-99-9999, get back its position in the database, and then sort the (position, number) by position to recreate the original list of data.

As poncho mentioned, to turn this into a solvable problem you need to modify the criteria somehow.

If each piece of independently-queryable data is large enough -- say, each piece is a randomly-generated 128-bit encryption key -- then "going through every possible key" is not possible in this universe. (Seth Lloyd, "Computational Capacity of the Universe"). Then hashing each 128-bit random key (the SHA256 hash is a good choice) to create the database D looks like it would work for you.

Another approach is to somehow keep the list L and the database D behind a firewall, and only allow people who have already been authenticated and who you trust not to misuse the list L to query the list.

Another approach is to use a probabilistic test, perhaps a Bloom filter or something similar, that allows a person with some public file D to work out that his piece of data S is either "possibly in the list L" or "definitely not in the list L". Perhaps in your specific application allowing most people to definitely confirm that their data S is definitely not in list L would be worth the risk of allowing an attacker to construct a list of "possible" social security numbers that includes 1/100 of all possible social security numbers, including all the numbers from your original list L, but with no way for the attacker to distinguish between numbers in the original list L and millions of other irrelevant numbers.