I'm looking for an elegant solution to the might-seem-trivial problem of looking up for specific value in a known set of values without disclosing what value we look for. Let me describe it in a classical way:
Alice will soon celebrate her birthday and she wants to know if anyone in her class has the birthday on the same day as her. Unfortunately, the only person who knows the dates of birth of all the people in the class (except Alice's one) is Malory. How Alice could ask Malory if anyone has the birthday on the same day without disclosing her own date?
- Malory is open to helping Alice and she will answer any questions legitimately. Yet, she can only answer yes or no.
- Alice will ask Malory a single time. Malory cannot influence Alice to make her ask the same question once again. Though, in future Alice might on her own will ask about the different dates (e.g. Bob's birthday).
- Alice doesn't need and doesn't want to know the dates of birth of everyone in a class. She would like to get an answer from Malory asking a single question.
A pretty straightforward way to approach this problem is to apply hash. Alice hashes her birthday and passes this information to Malory, the same time asking her to hash the birthdays of all the people she knows and tell her if any match. The problem is that Malory, who would like to know Alice's birthday, can enumerate all possible dates (as the entropy of input is low) and check one by one if any matches with what Alice asked about. I would like to eliminate that threat.
I have thought about applying the one-to-many mapping to the birthday. As one date could be represented by multiple values, the enumeration attack would become unfeasible. The first problem is I don't see an easy way to let Malory do an atomic mathematical comparison with her set of dates. The second problem is if such comparison can be done, it is still possible for Malory to make a new set and do the lookup operation once again (what effectively translates to enumeration attack). Thus, the one-to-many mapping Alice applies should be parametrized by the unique feature of a set Malory will be searching in.
I do hope I haven't brought too much confusion and I'll appreciate any help, references, mentions of algorithms, or similar problems! I'll also appreciate your opinion if you think this problem is not solvable with given assumptions! If some of them are unclear, let me know and I'll do my best to clarify my intent.