4
$\begingroup$

I was thinking of the problem of naming&shaming, victims don't want to reveal themselves. Yet the public wants to know, and have some confidence in the veracity of statements. Such confidence could arise for instance from multiple victims naming the same person. I was thinking cryptography could come to the rescue.

I'm having trouble even in the formal definition part. Initially I though multi party computation could allow a group of people to each name (or not) and only if a name passes a threshold is it revealed, and all members of the group could attest the name passed the threshold. But thinking of practice issues, we may want a async process, where after setup different people submit their testimony separately with minimal back and forth. We may not know in advance who will participate and want to be able to work with a subset members. The minimal number of people to ensure reasonable anonymity is rather small say 100, but we may want to increase the requirement significantly if we are thinking about minimum number of colluding members to reveal which specific member named someone.

I quickly run into impossibilities, If we allow ad-hoc groups to form and vote together then a not so large malicious group could break anonymity. I'm looking for a solvable variant of this problem.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ So, how is this different from voting? You want the votes to disappear if they don't pass a threshold? $\endgroup$
    – Elias
    Commented Jan 23, 2018 at 10:29
  • $\begingroup$ yes, we want the votes to disappear if they don't have a threshold. $\endgroup$
    – Meir Maor
    Commented Jan 23, 2018 at 11:17

1 Answer 1

Reset to default
5
$\begingroup$

There is a very recent paper that solves this problem at a large scale using secure computation techniques:

How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior: Moni Naor, Benny Pinkas, Eyal Ronen

They motivate the problem from the point of view of passwords (they want to identify passwords that are too common), but it seems like the same problem you propose.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This isn't much more than a link only answer. Can you add more details? $\endgroup$
    – mikeazo
    Commented Jan 23, 2018 at 21:10
  • $\begingroup$ It took me a bit to find time to read the paper itself, almost too good to be true. Very cool result. $\endgroup$
    – Meir Maor
    Commented Jan 24, 2018 at 19:34
  • 1
    $\begingroup$ It does however allow for low probavility false positives,more problematic for shaming the password heavy hitters. But it also gives some relevant references I haven't yet gone through. $\endgroup$
    – Meir Maor
    Commented Jan 24, 2018 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.