What's a good strategy for the game "spyfall"? https://boardgamegeek.com/boardgame/166384/spyfall

There are n players (n > 3), and n-1 of them know a secret string (the location). The nth player is the "spy", and does not know the location.

The non-spies has to guess which player is the spy, and the spy has to determine the location.

Players cannot communicate at arbitrary times. Only one person (the player who's turn it is) can communicate, all players will hear the information this person is communicating. The player who's turn it is also gets to choose the next player.

The tricky part is that there are only 30 locations, so it's easy to iterate over them all. This is why, for example this strategy will not work:

generate a random string r, and, when it's your turn to communicate, say  (r, Hash(r + location)). The person who is unable to say this is the spy.

This will not work because the spy can compute hash(r+location) for each location, and the location that matches the given hash value is the correct location. 

The spy can win with probability 1/30 by guessing a location and then acting as if that location is the correct location. Is there a protocol for the non-spies to find the spy with probability negligibly close to 29/30? (assuming that all non-spies follow this protocol but the spy can do whatever they want).
I think the following protocol works:

Let's take a group where discrete logarithm is hard (say, a classic elliptic curve); I'll note the curve law with additions. Let $q$ be the group order (prime). Let $G$ be a conventional generator for that group. Let $H$ be a hash function whose output is a group element (the value $H(x)$ for an input $x$ should be such that nobody has any clue as to the discrete logarithm of $H(x)$ in base $G$). Let $h$ be another hash function that produces bytes (like SHA-256).

Each player $i$ generates a random value $x_i$ modulo $q$, and publishes (i.e. announces) $P_i = x_iG+H(loc)$ (where $loc$ is the secret location).

Once all $P_i$ have been broadcasted, each player $i$ then computes, for all other players $j$, the values $s_{i,j} = x_i(P_j-H(loc)) = x_ix_jG$. The important point here is that $s_{i,j} = s_{j,i}$ for all pairs $(i,j)$.

Then, each player $i$ publishes the list of values $t_{i,j} = h(i||j||s_{i,j})$ for all $j\neq i$. Each value $t_{i,j}$ can be computed by the player $i$ and the player $j$.

Each player $i$ recomputes all the $t_{j,i}$ and compares them with the received values. If all players follow the protocol, then they should all match, except the one from the spy (if the spy did not guess the location correctly when computing his own point $P$). The player $i$ can then detect the spy, and, in that situation, all other honest players have also detected the spy, so they all agree when he is accused.

On the other hand, if the spy did guess the location properly, then he will notice that all the received $t_{j,i}$ match his own recomputed $t_{j,i}$, confirming his guess, and he can proceed to winning the round. I don't think this case can really be avoided, on a general basis: the spy can always get lucky with his initial guess, in which case he cannot be uncovered by any protocol, and thus he can infer the correctness of his guess by his own survival.



The protocol above is an extension of the Encrypted Key Exchange, the first PAKE protocol to be published, by Bellovin and Merritt in 1992.

It's clear that the $P_i$ points reveal no information on the secret location. If $h$ behaves like a random oracle, then the spy may extract information from any published $t_{i,j}$ value only by guessing exactly the value $s_{i,j}$, i.e. by breaking the EKE between $i$ and $j$.