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?