Can a service provide a hash/encryption key to others that it itself cannot use?

Question

Consider a service $S$ that receives hashes of documents from a number of providers. If two hashes match, it notifies the providers. We do not want anyone at the service to be able to identify the documents. However, the document space is actually quite small (~billions) so a dictionary attack is possible.

One solution would be the creation and provision of an HMAC key out of band between the data providers. If the service never has access to it, then it could not perform the dictionary attack. This is a bit cumbersome though and an automated approach would be preferred.

Is another way possible?

Answer 1

Basic logic would dictate that if any provider can use a non-secret method to generate a hash from a document, then the central service can also use that known method to perform the same hash in order to carry out the dictionary attack.

Therefore, to avoid this attack, there must be some secret shared between providers that is unknown to the central service.

Note that 10 billion 128-bit hashes would only require 150GB of storage. You might therefore decide that it is better for the providers to simply share their hashes directly with one another. You can use a Dandelion protocol so that when new hashes are announced, the provider originally announcing any particular hash has their identity concealed.

Answer 2

If the clients can share a secret key then we can use a Fully Homomorphic Schemes to achieve this. Let $k_{prv}$ the private key of the clients and $k_{pub}$ is the public key that the server has.

• Whenever a hash $h_i$ sent to server it is encrypted $e_i =E(k_{pub},h_i)$ ( preferable TFHE) by the client.
• The server, uses FHE Equality circuit $C$ that returns encrypted $E(1)$ if they are equal.

    res = E(k_pub,0)
    for each E(h_j) in range(1,i-1):
         cur = C(h_i, h_j,k_pub)           //compare
         res = FHE_Add(res,cur,k_pub)      //accumulate the result.

   return res

• Now, server sends the $res$ as the response to client(s).

• The client decrypt and check that

  • if $res=0$ this means that the hash is not exits on the server.
  • if $res\neq 0$ then the hash on the server.

---

Notes:

• This is similar to what Microsoft's Password Monitor.
• The clients can have standard public-key method to share the $k_{prv}$ and $k_{pub}$
• This protocol requires that the server is semi-honest.
• The server has a blind computation that they learn nothing from the encrypted, computed values, and from the result, however;
• If a client send a new data to upload without asking the existence, than the server can deduce that the previous hash was not existed.