Assume an anonymous communication system in which anonymous parties randomly meet in pairs to exchange information.
How could two anonymous parties determine whether they have interacted before, without being able to re-identify each other?
(I can only tell whether or not we met before, but I cannot link this meeting to any specific anonymous meeting in the past or future)
Some parties may be dishonest. In that case, we can tolerate false negatives (an honest party thinking that they haven't yet interacted with someone when they in fact have), but we cannot tolerate leaking the number of times they interacted (because this might make a party re-identifiable). In other words, honest parties should be able to tell whether they have met, but no party should be able to re-identify a given party.
The following protocol does not fulfill these requirements because it could leak the number of previous meetings to a dishonest party (see Maeher's comments):
- every party has a store of secrets (which starts empty)
- whenever two parties meet they use private set intersection to determine whether they share a secret. If they don't, then they haven't met before and they establish a shared secret. If they do then they met before and they do not share additional secrets.
EDITED in reponse to Maeher's comments