Is there an algorithm that allows verification that 2 encrypted or hashed bits of data are the same, given that I may only know half of the key/ salt?

Question

We have an interesting problem.

Currently, we store a salted hash of some secret key known only to the clients of our clients to allow us (and our clients) to find other records that were generated by the client's clients, without either us or our clients being able to identify the client's client or know their secret key. We know the salt.

We now have a requirement to change the salt every 12 months, but we still need to be able to match the last year's records.

The only way I can see to do this is by keeping the current salt and the previous salt, and storing every record with both hashes, then when we want to find other records, look for either of the two stored hashes in either of the two stored hashes on the other records, which is double the computation on storage, double the storage and up to 4 times the search time.

I think we need something like a 2-part key, so every 6 months we can generate a new half-key, and delete the oldest half key, so if the key is $k_1k_2$, in 6 months I can throw away $k_1$ and generate $k_3$, so the new full key is $k_2k_3$.

So what I'm looking for is a function where the client's client passes in their key, $s$, and we pass in a 2 part key, $k_n$ and $k_{n+1}$, and receive a digest, such that there is another function where we can pass in two digests and the current $k_nk_{n+1}$ and get true if the two digests were generated with the same $s$ and share at least one of $k_n$ and $k_{n+1}$, without us ever being able to tell what $s$ is.

If it's not possible, then we will have to go with the double hash storage, but what I'm describing sounds like something that is possible with commutative operations...

Answer 1

I ran into a situation with a similar requirement, and here's the idea I came up with:

We don't use a conventional 'salted hash', instead to encode a user's password, we first hash it (optionally with the user's id, but without a salt) to form a value $h$, and then you select a random Elliptic Curve point $X$, you compute the point $Y = hX$ (where $hX$ is point multiplication), and then you encode store it as the pair of points $(X, Y)$. To validate the password that the user enters, you again hash the password the user gave you, and then check if $hX \overset{?}= Y$; if it is, you accept the password.

This encoding is effectively one-way, given $(X, Y)$, it's infeasible to recover the password hash $h$ that would match it (assuming that we use a strong curve); this is the ECDLP problem.

$X$ effectively acts as salt; given a pair of encoded passwords $(X, Y)$ and $(Z, W)$, it is infeasible to determine whether they encode the same password; this is the dECDH problem.

And, finally (here's why it is of interest to you), it's updatable; at any time (be it once a year, or more often if we choose), we can select a random integer $r$, and replace $(X, Y)$ with $(rX, rY)$; effectively changing the salt we use without changing the password it matches.

Depending on your actual requirements, something like this might be adaptable to your situation.