Mafia

Mafia

Mafia - popular card game, that involves verbal communication.

First of all Game initialization is performed:

1. RSA handshakes
2. Role distribution
3. Creating Id's
4. Sharing secrets

Game consists of several rounds. One round can be divided in following phases:

1. Day Phase
   1. Communication Phase
   2. Open voting for person to kill
2. Night Phase
   1. Doctor(I)
   2. Detective
      1. Target Choice
      2. Role revealing
   3. Mafia
      1. Communication
      2. Voting
   4. Doctor(II)
3. [Round results]

let N denote total number of players

let M denote total number of mafia players

Game Initialization

At this stage roles should be distributed among players and some secrets are shared

RSA handshakes

Each player creates his own RSA key pair and broadcasts his public parameters. After this step all players have their own RSA engine.

Now player i can encode a message with RSA public key of user j and only latter can read the result. So, basically, each pair of users now has their own secure channel (when needed)

Role distribution

In the beginning players agree on set of Roles, where Roles[i] denote a single point on elliptic curve, that corresponds to some role (all innocents must have different roles). I.E Roles[0] - mafia, Roles[1] - doctor, Roles[2] - detective, all the rest are innocents

Now deck creation appears:

Vector of IV is created (process resembles this protocol):

• At first there is vector V[0] = (g, g, g, ..., g) - N times in total. Where g is the generator of our elliptic curve

• player i=1..N takes V[i-1] as input. generates his own vector of N random numbers X[i], which satisfies following condition:

  X[i][0] = X[i][1] = ... = X[i][M]

  and his cipher key s[i](Integer) and by his vector R[i] which. Then he outputs V[i] = s[i] (V[i-1] * X[i])

  also second vector of R keys encrypted with s[i] is formed

Player N outputs V[N] = sX, where s - is multiplication s[1]*s[1]...s[N], and X is a vector of random points on the curve

Now we shuffle roles:

Initial vector of roles is

• R[0] = (Roles[0] - repeated M times, Roles[1], Roles[2], .. Roles[N-M+1])

• each player multiplies R[i-1] by his values s[i] having R[i]. In the end we have R[N] = sR[0]

Now a card - is a pair Card[i] = (R[0][i], X[i])

Now algorithm pretty much follows this game primitive except following:

During cascaded shuffling each player not only encrypts card with a new keys s'[i], but also decrypts with key s[i].

NB: if at least one player was honest, after this we get a shuffled deck of cards, Card[i] is encrypted with N keys, split evenly among N players.

NB: if at least one player was honest, no one known X[i] part of Card[i].

Cards and dealt evenly and all users exchange keys. Now everyone knows his Role and IV. Now each player broadcasts his R[i]. with

NB: Better uses different set of keys for Roles and for IV

Creating Id's

Each player creates his own random Id[i] - 192-bit random number (approx. order of elliptic curve group).

Following conditions must hold:

• for all i, j: Id[i] != Id[j]
• for all i, j: Id[i] != 2*Id[j]

Sharing secrets

each player creates his own secret value t[i] - denoting, whether he is a mafia or not:

• t[i] = Id[i] if player is not mafia
• t[i] = 2Id[i] otherwise

Now player i splits t[i] into a shared secret: Random vector R[i], so, that

sum over j of R[i][j] = t[i]

Now a circular communication is performed, computing two vectors:

• In the beginning A[0] = B[0] = () - empty
• User i performs following actions:
  1. Appends R[i]g to the A[i-1]
  2. Appends to the B[i-1] value (Id[i]g, Id[i]g, ... Id[i]g) - Id[i]g repeated N times.
  3. picks random encryption key s[i]
  4. Encrypts everything in A[i], B[i] with s[i]

After this step we have two vector of length N^2. In each vector values (i-1)N..iN-1 are encrypted with s[i]s[i+1]...s[N]

Now we transform this vectors:

• At the beginning we have C[0] = A[N], D[0] = B[N]
• User i performs following actions:
  1. Decrypts elements (i-1)N..iN-1 of C[i-1] with s[i] storing T[i] as result
  2. Encrypts elements 0..N^2-1 of T[i] with new keys s'[i] which gives C[i]
  3. Decrypts elements (i-1)N..iN-1 of D[i-1] with s[i] resulting in Q[i]
  4. If user i is the detective - multiplies Q[i] by vector TK (see description below) storing result in U[i]
  5. Encrypts elements 0..N^2-1 of U[i] with new keys s'[i] which gives D[i]

Vector TK - basically encrypts all ids with keys only known to the detective. TK[iN+j] = K[i], where K - is a random vector of keys known only to the detective

Now we treat these secretes as cards and shuffle vector of pairs S[i] = (C[i], D[i]) the same way as we did with roles here . These secretes are dealt evenly among players (N to each player).

After that step each player knows N secrets. But he doesn't know, who do this parts belong to: he known only points Id[i] * K[i] * g

NB: there is a possibility, that all of secrets that were given to Detective belong to each player(so he gets sort of 'free check'). But possibility of this about (N^2 choose N) which is about 1 in 50000 for five players. If we split secret in 4N pices - possibility is less then 10^(-28)

NB: or we can give each player a secret for each key Id[i] * K[i] *g. This way each player holds a part of the secret for all other users, but doesn't know which secret corresponds to which player

Day Phase

During day phase players participate in open discussion, and then openly vote whom to kill

Comminication Phase

During that phase players exchange messages. Simpliest way is to use chat. Other option is to use [audio channel]

Open voting for person to kill

Players decide, whom to kill this day. Straight-forward commitment scheme: players choose, whom they want to kill, salt it and broadcast hash through open channel. After everyone received messages with hashes - reveal votes and salts

Night Phase

During night phase alot of decisions must be made in secret

Doctor(I)

Doctor - role that can heal a player. He must make a decision BEFORE mafia's choice is known, but reveal it AFTER. Also Doctor identity must remain unknown. To do that - we use Secure Multiplary Sum for anonimizatoin on EC for doctor to broadcast Id[c] - id of player, that doctor wants to heal.

To be precise - we won't finish algorithm here:

we only run first two steps of SMSfA

Algorithm is put on-hold and continued here

Detective

Detective is a role, that can check, wether target is mafia or not. Main challenges are to keep detective identity a secret as well as his target.

Target Choice

Absolutely the same as choosing target for Doctor, that is performing actions described here and here

Role Revealing

Using notation from here

1. Detective create a new RSA key-pair
2. Using SMSfA Detective broadcast to everyone public parameters created in step 1
3. Using SMSfAEC Detective broadcasts K[target] * Id[target], so all players receive gid = K[target] * Id[target] * g
4. Each player finds secrets marked with gid, that he holds, Encrypts them with rsa parameters aquired from step 2 and broadcasts result
5. Detective and only detective is able to decode messages sent on step 4. He decodes them, calculates the sum Q and checks, wether Q = Id[target] * g or Q = 2 * Id[taget] * g.

If both checks failed - someone tried to interfere(cheat)

NB: If each player holds at least one piece of each other player secret N - 1 players must cooperate to find out roles (At least looks like it).

Mafia

Mafia should decide whick player to kill.

TODO - there is a more reliable algorithm, but fon now this must suffice

Communication

Mafia night communication round consists of exchanging short messages and voting untill consensus is found

Each player, that is mafia holds the same value of IV. Which means, that have a common secretm that can now be user to instantiate a symmetric encryption scheme.

For example, they can use byte representation of IV as initializion seed of AES algorithm

Now communication round is simple

• Each mafia must broadcast some 4KB message encrypted with their common key
• Each non-mafia player must broadcast some sort of comprehended message encrypted with his own public RSA key (i.e current timestamp repeated as many times as possible in 4KB)

Mafia players are able to decode each other's messages and show ther

Voting

Mafias use SMSfAEC :

Algorithm is run over triples of ints:

• All innocents input three random values (r[i][0], r[i][1], r[i][2])
• Mafia use this to vote: if j is mafia he inputs (r[j][0] + Id[target], r[j][1] + Id[target], r[j][2] + Id[target])
• We get as a result R[0] = R[1] = R[2] = sum over i Id[target_i], where target_i - target chosen by i-th mafia
• We compute T[i] = R[i] * inv(m) - which gives us average vote of mafia
  • If all T[i] are equal to Id[k] for some k - all mafia agreed on killing user 'k'. If someone from mafia disagrees - cheat took place. Beacause if there are approx 10^77 point on our EC, the probability of two random vectors of three points colliding - extreemely low
  • If there is no such 'k' - then Mafia couln't agree. Communication step is repeated

Doctor(II)

After mafia choice is known, doctor can finally publish it's heal target.

Basically, we winish, what we started here

Steps 3-4 of SMSfA are performed, so now everyone can compute, whom did doctor heal. To be precide they know Id[target] * g, but target could be found using linear search

Other

Secure Multiparty Sum (SMS)

Simpliest of secure multiparty communications:

Each player has an integer input p[i], players want to compute sum over i of p[i].

Algorithm:

• Each player splits p[i] into set of N random integers p'[i][j] such, that sum over j of p'[i][j] = p[i]
• Player i sends p'[i][j] to player j over secure channel
• Each player computes sum of all values passed to him and broadcasts it
• Sum of breadcasted values is the final output

Secure Multiparty Sum for anonymization (SMSfA)

Asume, player c is supposed to broadcast some integer value X to everyone else, without them knowning his identity. Following protocol allows achieve this goal (sort of):

1. Each player generates a random int R[i], slats it and broadcasts Hash(R[i] + Salt[i])
2. Players run SMS, where c inputs R[c] + X and everyone else input R[i] and get V as output
3. They reveal R[i], Salt[i]
4. Each player computes broadcasted message X = V - R, where R = sum over i R[i]

NB: If c notices that V-R != c, that he claims, that someone cheated and game stops. For c - no reason to cheat in this protocol, he could've just give another X as input

Secure Multiparty Sum for anonymization on Elliptic curve (SMSfAEC)

Almost the same as this with a slight difference in SMS algorithm:

(notation from SMS)

instead of broadcasting p'[i][j] and computing sum over integer field, we broadcast p'[i][j] * g and compute sum over elliptic curve. As a result each player gets X*g as result value