Score:4

Hiding/Obscuring position information in a board game

jp flag
fho

There has been a question on the BoardGameGeek forums that basically boils down to this:

  1. There is a player character on a regular rectangle map at position (px,py).
  2. There is one "AI" character that moves across this map according to some function or pattern (e.g. one field per turn (t), (ax,ay) = (ax0,ay0) + t * (vx,vy)).
  3. The player needs to determine if the two characters are within (L1/Manhattan) distance D.

The question here is if there is some scheme that allows the player to calculate the distance to the AI without the game having to disclose the actual location to the player.

To me this sounds like there may be some solution to be found in the cryptography community.

The restriction here is that, this being a board game, no computer should be involved. So "complex" calculations or just storing the positions digitally is not wanted. But apart from that every utility is fair game (ie, (big) lookup tables or code books).


edit: @bmm6o is right, of course. The scheme proposed by @PaulUszak does not really take into account that somebody has to calculate $H(p_x || p_y || a_x || a_y)$ and in the case of a (solo) board game that is the player.

I derived a scheme from Pauls answer and posted that on BGG. The critique there was that I hard coded the AIs positions which reduces replayability. Once the player figures out the $ai_{hash} \rightarrow (ai_x, ai_y)$ relationship the AIs position is not hidden anymore.

With that in mind, the question becomes if there is a scheme to disclose the current distance [2] between player and AI to the player that carries out the calculation while disclosing as little information as possible about the current position of the AI.


[2] If it makes a difference the original poster on BGG was mostly interested in if the AI and the player occupy the same place ($d=0$) or if the AI is "close" (e.g. $d<3$). Distances further than that are irrelevant.

Paul Uszak avatar
cn flag
What is the cardinality of the set of map coordinates? I.e. how many possible positions are there on the map?
jp flag
fho
@PaulUszak That was not specified in the original question, but I guess we can assume a board of around 10x10 fields.
jp flag
fho
@kelalaka I am not sure I understand your question, but I think you assume I am talking about a computer game? If that were the case, it would be easy to let the computer handle any hidden information and calculations. But the question was about a scheme to hide and only disclose part of information in a board game.
kelalaka avatar
in flag
Ok, can the user see where is the AI player? Isn't it Manhattan D is easy to calculate except the obstacles...
Mark avatar
ng flag
It's worth mentioning that if one is ok with some relaxations (probabilistic, and only guarantees when the player is close, meaning $\lVert \vec v-\vec v'\rVert_1 < d$, or far, meaning $> dc$ for $c > 1$), one can likely do *much* better than the current answer with locality-sensitive hashing. This doesn't give a cryptographic guarantee, but that doesn't seem needed. Additionally, existing LSH schemes are (close to) linear, so one could likely simply store $(h, h(ax_0, ay_0), h(v_x, v_y))$, a (relatively) tiny amount of data. The "gap" mean this may not be suitable for the application though.
jp flag
fho
@Mark What "gap"?
Mark avatar
ng flag
The $c > 1$. Concretely, LSH can be guaranteed to work for "close" ($<d$) and "far" ($>cd$) distances, but has no guarantees for "medium" ($\in (d, cd)$) distances.
jp flag
fho
Follow-up question here: https://crypto.stackexchange.com/questions/98313/hiding-obscuring-position-information-in-a-board-game-part-2
Score:2
cn flag

Good instinct coming here. Fair warning, I don't know what this game is, but. Let the player live at $(p_x, p_y)$ and the AI lives at $(a_x, a_y)$. And we assume a grid of 10 by 10 cells.

Thus there are 100 possible positions per player, and so 10,000 possible combinations of the two players. I'm assuming that the AI can be on top of the player, otherwise you'd have 10,000 - 100 possible combinations if they can't share a cell.

For all games, pre-calculate $H(p_x||p_y||a_x||a_y)$, and also Manhattan distance $D$ between $(p_x, p_y)$ and $(a_x, a_y)$. $H$ is a cryptographic hash function. I suggest SHA-1 as the 40 character hexadecimal values are not overly long for manual searching. Sort $H$ into numeric order to further ease the search. Then publish the $(H, D)$ pairs in a thick book. At 50 hashes per page, that's ~200 pages.

When the AI or the player moves, the 'game' outputs $H$ which can be looked up in the thick book to obtain $D$. You didn't want digital storage, otherwise the game could just compute and output $D$ directly. The player will know the distance, but it is computationally infeasible to invert $H$ to obtain the AI's position without brute forcing/cheating. This technique also allows uni-lateral re-computation of $(H, D)$ pairs if necessary to audit the process and prevent cheating.

This should be doable for a 10 by 10 board, but clearly gets ridiculous for much larger ones.


Note1: Be aware the granularity of a 10 by 10 board. Since you know your own position, any $D$ creates a circle of potential locations of the AI around the player. If the distance calculation was based on the cell centres, only a few cells will exactly match $D$. So there is some positional information leakage. This weakness is not a feature exclusively of my solution, but maths and the small grid.

Note2: Inversion comment. Yes you could create a cheat code book yourself and find all $H$ preimages. That's cheating though. If there was an independent unbiased arbiter for the game, a dungeon master (???) if you will, you could adapt the hash as $H = \text{SHA-1}(p_x||p_y||a_x||a_y||pepper)$ where the pepper is only known to the arbiter. That would still facilitate audit during a dispute. Could the AI hold the pepper if you trust it to play a fair game?

Note3: It should be statistically possible to truncate $|H|$ from 40 hexadecimal characters to much less. 10,000 combinations only occupies 14 bits. If we choose a game position security level of another 10,000, we could use 28 bits for the published hashes. That would publish as seven hexadecimal characters; eight if you want pairs. And therefore less pages.

Aman Grewal avatar
gb flag
The question says Manhattan distance, so the references to Pythagoras don't apply. And if this actually needs to be a pen-and-paper calucation, I would not suggest SHA-1.
Paul Uszak avatar
cn flag
@AmanGrewal Manhattan:sorted, thanks. The hashes are precomputed into a lookup book. I understood that code books/look up tables are allowed.
ph flag
How does this step happen: "the 'game' outputs H"?
us flag
"it is computationally infeasible to invert $H$" --> it would take mere milliseconds to compute all 10,000 hashes yourself to build an inverted index. There are no high-entropy inputs to $H$ in your proposal, so it does not make sense to talk about the one-wayness of $H$.
jp flag
fho
Great response! I am not too concerned about the in-feasibility to invert $H$, if players want to break the game they will. Does this work thou? Eg just computing $a_x || a_y$ for the first fields will produce [[0,1],[1,1]] and looking at the output for a 10x10 field has a lot of repeating numbers.
jp flag
fho
Continuing that thought: I guess that could be avoided by uniquely identifying each individual field. That is not calculating $H(a_x || a_y || p_x || p_y)$ but $H( (a_x + 10 * a_y) || (p_x + 10 * p_y))$ (for a 10x10 playing field).
jp flag
fho
(I think we have to do the same "trick" twice, else we have the very same problem gain ... so it would be $H((a_x + 10 * a_y) + (p_x + 10 * p_y) * 100)$. The question now becomes if any hash function is still needed (except for maybe obfuscating the output).
jp flag
fho
@PaulUszak Could you please comment on $p_x || p_y$ being the same for several combinations of $p_x$ and $p_y$ (e.g. $p_x = 1, p_y = 0$ and $p_y = 0, p_y = 1$)?
Morrolan avatar
ng flag
@fho $||$ is the concatenation operation. As such $0 || 1 = 01$, yet $1 || 0 = 10$. Thus the inputs to the hash function are not equal.
jp flag
fho
@Morrolan That makes more sense. I was not familiar with that notation and assumed it must be an OR or XOR.
Paul Uszak avatar
cn flag
@fho Oh God, sorry. It's concatenation. Which is slightly ambiguous - see https://crypto.stackexchange.com/a/71784/23115
jp flag
fho
@PaulUszak Thanks for your answer! I'll play around this a bit. I guess it would be quite easy to "pre-scramble" the positions on the board (just to obfuscate things) and not use any (calculation intensive) hash function. Then it is just $p_{fid} + a_{fid} * 100$ ($x_{fid}$ standing for field identifier) to get a (somewhat) random number to look up in the booklet. That is, if you do not have a hash function in mind that would be trivial to calculate multiple times by hand.
ph flag
I really don't get how this solves the problem. Who is computing this hash, and why don't they just perform the distance calculation on the inputs instead?
jp flag
fho
@bmm6o The goal is to obfuscate the actual position of the AI on the game board. So there is no figure/marker on the map that represents it. The hash would have to be computed when the game is produced to fill in a code book with (hash(player, ai), distance) tuplets. Then by the player to check whether he is close to the AI. Using Manuel Blums HCMU this might actually be feasible.
ph flag
I get that the book would be produced ahead of time. Who is producing the hash to lookup during play?
jp flag
fho
@bmm6o Ideally the player(s). You can reduce the calculations to one addition and the aplication of the hash function. HCMU is actually pretty simple to compute especially if the input is short.
ph flag
If you think this solves your problem, I'm not going to argue with you. But this answer does not make clear how the players will calculate a function whose input includes the adversary's position, without them knowing the adversary's position. Isn't the procedure that someone has to calculate $H(p_x||p_y||a_x||a_y)$ each turn?
jp flag
fho
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/133414/discussion-between-fho-and-bmm6o).
jp flag
fho
@PaulUszak Sorry for unaccepting your answer. I was convinced that I should clarify my question instead of opening a new one.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.