Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Titandrake]

Analysis of Mafia assuming perfectly intelligent players, with no power roles or with 1 cop. Open access paper, so anyone can download it.

http://projecteuclid.org/euclid.aoap/1211819786

The proofs to show the strategies work are harder to read, but you can skip over it if you don't want to deal with all the probability.

[liopoil]

Before even reading this, I'm certain that this is everything I've ever wanted to know and more. It better not disappoint!

EDIT: Okay, so they allow Cryptography, and assume a very large number of players, but that just makes it cooler!

[popsofctown]

Cryptography is usually banned in forum mafia.

This raise a question, though, if a cryptography ban is actually enforceable in forum mafia, in games with unlimited amounts of data per post. Would the potential for information hiding in posts make it possible for two players to solicit eachother for a cryptographic exchange channel without the moderator who views the post knowing, and/or somehow being able to always have plausible deniability that they were soliciting a cryptographic channel of communication (I wasn't signalling him, my post just happened to have that pattern in it).

My knowledge of cryptography is limited enough that I'm not really for sure.  It would counterintuitive/surprising if you could do so under a moderator's nose, but I find unbreakable cryptography counterintuitive/suprising also so I can't just lean on that intuition.



Of course, in practice, forum mafia is more fun without cryptography, if you break the moderator's rule you are being a Sea Hag, and it's extra hard to find a second person that also wants to be a Sea Hag with you.

[Awaclus]

Cryptography is usually banned in forum mafia.

This raise a question, though, if a cryptography ban is actually enforceable in forum mafia, in games with unlimited amounts of data per post. Would the potential for information hiding in posts make it possible for two players to solicit eachother for a cryptographic exchange channel without the moderator who views the post knowing, and/or somehow being able to always have plausible deniability that they were soliciting a cryptographic channel of communication (I wasn't signalling him, my post just happened to have that pattern in it).

My knowledge of cryptography is limited enough that I'm not really for sure.  It would counterintuitive/surprising if you could do so under a moderator's nose, but I find unbreakable cryptography counterintuitive/suprising also so I can't just lean on that intuition.



Of course, in practice, forum mafia is more fun without cryptography, if you break the moderator's rule you are being a Sea Hag, and it's extra hard to find a second person that also wants to be a Sea Hag with you.

Well, AFAIK, cryptography isn't banned because of scum communicating with each other during the day, but because of town using cryptography D1 to breadcrumb their roles in a way which keeps the role hidden until they need to claim, and that's when they show how the code is broken to essentially confirm the claim (or at least their commitment to that claim since the beginning of the game). That kind of cryptography abuse can't possibly be hidden because the entire point is to reveal it sooner or later.

[UmbrageOfSnow]

Public Key cryptography, like what Awaclus is talking about, could be gamebreaking.

I've always wanted to have a game with actually breakable ciphers allowed/encouraged/post-restriction-required, but I suspect 90% of people would hate that.

[scott_pilgrim]

Public Key cryptography, like what Awaclus is talking about, could be gamebreaking.

I've always wanted to have a game with actually breakable ciphers allowed/encouraged/post-restriction-required, but I suspect 90% of people would hate that.

That could be fun, but you'd have to design the set-up for it, and it should probably be the main focus of the game.

[UmbrageOfSnow]

Definitely agreed.

And I have no idea how not to make it stupid.  But at least I'm over my fear of running games now, so my pondering it might be more likely to bear fruit one day.

[popsofctown]

Cryptography is usually banned in forum mafia.

This raise a question, though, if a cryptography ban is actually enforceable in forum mafia, in games with unlimited amounts of data per post. Would the potential for information hiding in posts make it possible for two players to solicit eachother for a cryptographic exchange channel without the moderator who views the post knowing, and/or somehow being able to always have plausible deniability that they were soliciting a cryptographic channel of communication (I wasn't signalling him, my post just happened to have that pattern in it).

My knowledge of cryptography is limited enough that I'm not really for sure.  It would counterintuitive/surprising if you could do so under a moderator's nose, but I find unbreakable cryptography counterintuitive/suprising also so I can't just lean on that intuition.



Of course, in practice, forum mafia is more fun without cryptography, if you break the moderator's rule you are being a Sea Hag, and it's extra hard to find a second person that also wants to be a Sea Hag with you.

Well, AFAIK, cryptography isn't banned because of scum communicating with each other during the day, but because of town using cryptography D1 to breadcrumb their roles in a way which keeps the role hidden until they need to claim, and that's when they show how the code is broken to essentially confirm the claim (or at least their commitment to that claim since the beginning of the game). That kind of cryptography abuse can't possibly be hidden because the entire point is to reveal it sooner or later.

I think we might be talking about different things, but cryptography is abstract and difficult enough that it is hard for me to express myself/what I want to say, so I am going to give up.  Plus what I am trying to say might itself be megaflawed since I don't understand crypto very well.  It's not you it's me.  I hope that makes sense.

[liopoil]

Cryptography effectively allows you send a PM to any subset of players at any time, and you choose when they receive the PM, but they still know when you wrote it. This changes the game dramatically.

If the players agree, they can all send messages to random people all the time, this way nobody knows when real messages are actually being sent. Most of the and messages can just be gibberish.

[Jimmmmm]

Cryptography effectively allows you send a PM to any subset of players at any time, and you choose when they receive the PM, but they still know when you wrote it. This changes the game dramatically.

Surely you can only send messages to a subset of players if you previously agreed on an encryption.

[liopoil]

Cryptography effectively allows you send a PM to any subset of players at any time, and you choose when they receive the PM, but they still know when you wrote it. This changes the game dramatically.

Surely you can only send messages to a subset of players if you previously agreed on an encryption.

Nope!

"Hey Jimmmmm, I want to send you a message, I'll encrypt in a way only I know how to decrypt okay? Here it is: --garbled nonsense--"
"Okay Liopoil, now I've encrypted it again in a different way that only I know. Now it's double encrypted: --different nonsense--"
"Cool, now I'll decrypt my encryption: --nonsense--"
"Thanks, now I've decrypted my bit and got your message"

None of the other players can figure out the message. The only requirement is that your encryption/decryptions be associative (it still works even though the decryptions are in the opposite order of the encryption), which standard ones are.

[UmbrageOfSnow]

To put it another way:

I create a public key and a private key.  I post the public key in thread.

Now anyone can encrypt a message by sending PlainText X PublicKey and post that in thread.  And the only person who can read it is me, because to decrypt you need to do CypherText X PrivateKey (because math is hard).

Everyone posts a public key, and we all have our own PMs without agreeing ahead of time.  We just junk up the thread with gibberish.

[Titandrake]

There's one strategy mentioned towards the end that doesn't involve crypto. That one is essentially Follow the Cop without a doctor - a perfectly intelligent cop is hard to find, so there's a decent chance the cop lives long enough to investigate a majority of living players. At that point town is guaranteed to win once cop claims, since mafia gets endgamed even when all verified town is public.

That's probably the most relevant part of the analysis for actual games, but odds are most games won't have time for cop to investigate enough people to do so.

[chairs]

tl;dr LITERALLY PGP.

[liopoil]

To put it another way:

I create a public key and a private key.  I post the public key in thread.

Now anyone can encrypt a message by sending PlainText X PublicKey and post that in thread.  And the only person who can read it is me, because to decrypt you need to do CypherText X PrivateKey (because math is hard).

Everyone posts a public key, and we all have our own PMs without agreeing ahead of time.  We just junk up the thread with gibberish.

Wait, this is not the same thing. Your involves an encryption system where you must know how to encrypt but not how to decrypt. Mine just insists that it not matter what order the encryptions are applied. At least if I'm understanding how these keys work:

The public key actually encrypts a message, which is not what I would expect if it's a 'key'. Should be called public locks.
The private key decrypts the message that the public key encrypts. Somehow you cannot figure out the private key from the public.

Now, I trust that your way is how things are actually done, since I've heard of public-private key encryption before. I've just always assumed it was done my way for no good reason, since I don't actually have much any cryptography experience. All I know is a little number theory and that one puzzle about sending a package through an insecure postal system where each person only has their own keys and locks.

[chairs]

To put it another way:

I create a public key and a private key.  I post the public key in thread.

Now anyone can encrypt a message by sending PlainText X PublicKey and post that in thread.  And the only person who can read it is me, because to decrypt you need to do CypherText X PrivateKey (because math is hard).

Everyone posts a public key, and we all have our own PMs without agreeing ahead of time.  We just junk up the thread with gibberish.

Wait, this is not the same thing. Your involves an encryption system where you must know how to encrypt but not how to decrypt. Mine just insists that it not matter what order the encryptions are applied. At least if I'm understanding how these keys work:

The public key actually encrypts a message, which is not what I would expect if it's a 'key'. Should be called public locks.
The private key decrypts the message that the public key encrypts. Somehow you cannot figure out the private key from the public.

Now, I trust that your way is how things are actually done, since I've heard of public-private key encryption before. I've just always assumed it was done my way for no good reason, since I don't actually have much any cryptography experience. All I know is a little number theory and that one puzzle about sending a package through an insecure postal system where each person only has their own keys and locks.

The crazy thing about the public/private keypair system? I can encrypt something with my private key, and you can then decrypt it with my public key.

So it's not just "encrypt with (target's) public key, they decrypt with their private key", it's also "I verify this is from me because I encrypted with my private key and you can decrypt with my public key".

[chairs]

And you can do both - I can encrypt a message with my private key, then encrypt that (encrypted) message with your public key. You'd then decrypt with your private key (verifying you're the only one who can receive it) and then decrypt the result with my public key (verifying I'm the one that sent it).

[scott_pilgrim]

To put it another way:

I create a public key and a private key.  I post the public key in thread.

Now anyone can encrypt a message by sending PlainText X PublicKey and post that in thread.  And the only person who can read it is me, because to decrypt you need to do CypherText X PrivateKey (because math is hard).

Everyone posts a public key, and we all have our own PMs without agreeing ahead of time.  We just junk up the thread with gibberish.

Wait, this is not the same thing. Your involves an encryption system where you must know how to encrypt but not how to decrypt. Mine just insists that it not matter what order the encryptions are applied. At least if I'm understanding how these keys work:

The public key actually encrypts a message, which is not what I would expect if it's a 'key'. Should be called public locks.
The private key decrypts the message that the public key encrypts. Somehow you cannot figure out the private key from the public.

Now, I trust that your way is how things are actually done, since I've heard of public-private key encryption before. I've just always assumed it was done my way for no good reason, since I don't actually have much any cryptography experience. All I know is a little number theory and that one puzzle about sending a package through an insecure postal system where each person only has their own keys and locks.

I think what you described (the discrete logarithm method) lets two people communicate secretly.  Each has to come up with a key.  The disadvantage to this method is that if you want to communicate with lots of people, you need to keep track of a separate key for each one.

What UmbrageOfSnow described I think (RSA encryption) lets a lot of people communicate with one person.  He comes up with a public key, tells it to everyone, and now anyone can send him messages that only he can decrypt.  The disadvantage is that the communication can only go one way (you can also send signed messages but that's a little different).  The advantage is that you only need one key to unlock messages from anyone.  This is why RSA encryption is so popular.  Websites can get encrypted data from thousands of users, and they only need one key to access all of it.

[Seprix]

To put it another way:

I create a public key and a private key.  I post the public key in thread.

Now anyone can encrypt a message by sending PlainText X PublicKey and post that in thread.  And the only person who can read it is me, because to decrypt you need to do CypherText X PrivateKey (because math is hard).

Everyone posts a public key, and we all have our own PMs without agreeing ahead of time.  We just junk up the thread with gibberish.

I like Cryptography, but no way I want to play a Mafia game with it.