1
$\begingroup$

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

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ I don't think your protocol achieved your goal "without finding out how often or when". ( It depends on formal definitions which you did not provide) One party could choose to use the empty set in the first n interactions. In the n+1st interaction she would use the set of all secrets exchanged so far. The intersection's cardinality leaks the number of interactions with the honest party. Similarly a party could choose to split their set and learn whether they interacted with the honest party before a certain point in time. $\endgroup$ – Maeher Apr 12 at 13:13
  • $\begingroup$ Thanks for bringing this up. I adjusted the question accordingly. We cannot leak information on previous meetings. Achievable? $\endgroup$ – oc512 Apr 12 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.