Anyway, now I need to figure out a protocol that can be done manually and in a reasonable timeframe for a following problem: there is a group of good and evil people. There's no more evil people than good people in this group. Evil people know each other, and only one good person knows who everyone is; the rest of the good people don't know who is in which group. How can that one good person pass their knowledge to everyone without revealing their own identity? Also, the protocol must resist the evil people trying to disrupt it.
Yes, I'm trying to stop people playing Avalon in my office in a very over-the-top, ultimately nerdy way - by literally providing a winning strategy and calling it GG.
Yes, but in some cases the probability is too small to consider.
For example, take digital signatures. These are in effect a proof that the person claiming to have signed it is in fact the holder of the private key behind them, without revealing the private key. But it is possible for someone to accidentally generate a valid signature without having the private key. Extremely unlikely. But possible.
-----
The problem you pose is interesting because most ZKPs involve a prover and a verifier. Here, there are many separate verifier entities each with different information that need to be convinced.
> Yes, but in some cases the probability is too small to consider.
Thanks!
> What kind of communication is allowed?
Any kind. People are free to say whatever, whenever - the question is, whether or not you believe them.
In the game, each person takes a turn to select a 'squad' for a 'mission'. Then, everyone votes whether or not to accept the squad, and if the squad is accepted, it goes on a mission. The mission consists of the entire squad voting in secret whether the mission is a "failure" or a "success". Good people can vote only "success", evil can vote either "success" or "failure". The votes are tallied (without revealing who voted which way), and if there's one or more failures, the mission fails. The good team wins the game if 3 missions end with success, the evil team wins if 3 missions end with failure (or if the general vote fails to accept the squad five times in a row). The twist is, if good team wins, evil team has one last chance to guess which of the good players was "Merlin", i.e. one who knows who is in which team. If they guess correctly, the evil team wins.
The game consists mostly of the good players trying to guess who is good (to avoid taking evil players on missions), and the evil players trying to confuse everyone. Merlin, who knows who is good and who is evil, can't be too obvious about revealing his/her knowledge, lest he/she gets sniped at the end.
So my question is - how can Merlin pass his knowledge about the composition of two teams to everyone without revealing his/her own identity? We can assume that whatever protocol there is, at least half of the players (i.e. the good team) will be willing to follow it, and the rest might want to disrupt it or maliciously insert false information.
I've been thinking about it for quite a while, but I don't have much experience or knowledge of the area, so any pointers would be appreciated.
You can upgrade the system to have private communication with a public-private key system. I thought about ways to make it work otherwise and I can't come up with any. I don't think that regular zkp techniques will work here. Interesting problem though.
Note that signatures do not constitute zero knowledge proofs, however, because I can transmit your signature to a third party and convince them of the same thing you convinced me of, namely the authenticity (or whatever) of a particular document. Of course, larger protocols built around signatures don't suffer, because at worst you just need to make sure you sign a sufficient collection of data (to avoid interpretation as a different message given a different context)... but it's not zero-knowledge.
> It is also a zkp in case of a scheme with a challenge nonce
This is my point - it is not zk because as verifier you can show the transcript to a 3rd party and convince them that the thing to be proved is true, even if the thing to be proved can't let you successfully impersonate the prover thanks to a nonce. In a zkp scheme, the transcript proves nothing - it's as if you took the signing scheme transcript and made it so you couldn't determine which pubkey was being signed for: the 3rd party would have no reason to believe you hadn't faked the transcript.
In short, zkp transcripts must be fakeable, as counterintuitive as that sounds.
Are all ZKP probabilistic in nature?
Anyway, now I need to figure out a protocol that can be done manually and in a reasonable timeframe for a following problem: there is a group of good and evil people. There's no more evil people than good people in this group. Evil people know each other, and only one good person knows who everyone is; the rest of the good people don't know who is in which group. How can that one good person pass their knowledge to everyone without revealing their own identity? Also, the protocol must resist the evil people trying to disrupt it.
Yes, I'm trying to stop people playing Avalon in my office in a very over-the-top, ultimately nerdy way - by literally providing a winning strategy and calling it GG.
https://en.wikipedia.org/wiki/The_Resistance_(game)#Avalon_v...