Zero-Knowledge Bingo

Question

Bingo is the game of chance where each player matches the numbers on their card with the numbers that the caller draws at random. When the first player has collected enough called numbers on their card, they declare that they have won, and their card is verified.

Imagine this game being played online with players allowed to choose their own card.

Question: Is there a way to play Bingo online and assert that your card won, without revealing what your card is, only that you chose this card at the beginning and that it does contain the called numbers?

Sub-question: Is this a practical application of an existing, generalised problem?

Own thoughts: In the first iteration of this game, we could ask that players publish, signed, which card they chose at the beginning of the game. When the first player has collected enough called numbers, the winner will be apparent. But I don't want for players to publish their card at the start of the game.

In the second iteration of this game, we could ask that players publish, encrypted, which card they chose at the beginning of the game. We could include salt to avoid reverse lookups, and we could include a checksum to ensure that what they publish can't easily be decrypted into any card. But I don't want for players to publish their card at the end of the game, either!

Once a game is won, we know which subset of cards could have won. Perhaps it is possible to say that your card belongs to this subset (with some probability?) without saying what member it is? Perhaps this involves generating a large amount of winning cards, of which perhaps one is the actual winning one, and then prove that your card is one of them, without saying which one it is.

Clarification 1: This problem does not deal with calling numbers in a fair way. Assume that the players cannot predict what numbers are called.

Clarification 2: To prove that you have collected all the numbers, the subset of cards that could have won contains exactly that card, so the method of the first and second iteration are the same; this question applies to the subgoals of collecting one row, two rows...

Answer 1

I will build upon Meir Maor's answer, by constructing a simple $f$ for use in a R1CS like libsnark's or dalek's ``bulletproof'' library. Turns out this is pretty efficient!

1. Every player commits to the board. We assume the board $B(i,j)$ is of size $n\times m$. Make $nm$ Pedersen commitments, which we publish.

2. Numbers are called. Call these $l$ public numbers $B'(k):1<k<l$

3. When a player claims he won (bingo!) he can construct a proof. Note that a player wins iff he has a full row of matching numbers. We can say that for the winning row $i<m$:

$$\bigwedge^m_{j=1}\left(\bigvee^l_{k=1} B(i,j)=B'(k)\right)$$

and over the whole board, this becomes

$$f(B)=\bigvee^n_{i=1}\left[\bigwedge^m_{j=1}\left(\bigvee^l_{k=1} B(i,j)=B'(k)\right)\right].$$

This is quite a pretty form to put in an arithmetic circuit; it becomes $$\prod^n_{i=1}\left[\sum_{j=1}^m\left(\prod_{k=0}^l(B(i,j)-B'(k))\right)z^{j-1}\right]$$

for some random challenge $z$. Using a Fiat-Shamir transformation, this can be made non-interactive. This scheme needs $(l-1)(n-1)$ private multiplications, which means that a system like dalek's can create a non-interactive proof in $\log(n\cdot l)$ space, so logarithmic in the amount or rows and already-called numbers.

Answer 2

This seems entirely straight forward. Each player publishes a commitment, essentially a hash of their board. Possibly signed.

If the boards are not high enough entropy themselves we will tack on some random data to increase their entropy to make the result unguessable.

When a player declares victory he will provide a Zero Knowledge proof that he knows of a winning board matching his commitment.

Note Zero Knowledge proofs are very powerful stuff, but we need to open the black box of the functions we use (such as hashing) in order to use them. For any efficiently computeable predicate function $f$ we can prove we have $x$ so that $f(x)=true$ without revealing anything about $x$ beyond the statement.

In our case we would have $f(board)$ be the predicate which checks the board is a winning board and matches our commitment. Obviously trivial to compute.