Consider the following scenario:
We have two agents, A and B.
B needs to prove that they know a secret to A, without sharing the actual secret.
e.g.: A needs a way to de-duplicate the secrets they receive from B, but they don't need to know the actual secrets. (and B does not want them to know)
Think of it like sharing a hash of that secret, except: it's a very small, low entropy source (there's about 1 billion possible values). This means that a simple hash would be vulnerable to a dictionary attack.
Now, B could add a hidden "salt" to each secret they share and then hash it, and that would make it harder for A to do a dictionary attack. As far as I can tell, this would "solve" the problem for the 1-1 case.
However, let's now introduce a third agent, C. C is sending the same type of secrets to A. B and C cannot share their secrets between each other.
C can end up sending "duplicates" of secrets that B has, even though they don't know what B has on their end.
A, of course, now needs to de-duplicate not only the secrets from B, but also from C.
The hidden salt won't work anymore because now C would need to know the salt to be able to generate the same hashes. Otherwise A would not be able to de-duplicate between keys from B and C. Having a shared salt however means that C could do a dictionary attack on B or vice-versa.
Can A, B and C reach an agreement where B and C can share their "proofs" with A, in a way that A can de-duplicate them, but no one can reveal each other's secrets?
If so, can this be generalized to any number of consumers/producers?
Being far from an expert in cryptography (I only really know the very basics), I'm not sure if I'm using the proper terms here. Let me know if I can clarify any of it. Also, this is not homework or anything like it - while it was motivated by a concrete problem that I read recently, this is mostly just curiosity. A rough explanation on why it isn't possible (in the case that it is not) would most definitely be sufficient for me. Same for a brief description of a known algorithm, even if just the name - with proper direction I can do some research myself.
(Just to be clear if it already isn't: A, B and C do not trust each other)
(Contrived) example
Alice and Bob want to sell stamps to a stamp collector. Think of a stamp as being a 7-character string with only lowercase characters, and the stamp collector can't just fabricate them itself.
The stamp collector will buy any stamp that they currently do not have. However, it won't buy the stamp right away: it will wait to see how many sellers have it, so it can buy the stamp at the lowest price.
So before sending the actual stamp, Alice (or Bob) have to send a "bid" to the collector, so it can check if they already have the stamp, or if someone else offered it. They can't send the actual stamp with that bid, or the collector would just have it for free, which is no fun for anyone. The collector needs to know "which" stamp the bid is for, even if they don't know the actual 7-character string - or it won't be able to compare bids.
