1
$\begingroup$

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...

$\endgroup$
  • 2
    $\begingroup$ Spontaneously I'd say one could do that by committing to one's choice of numbers at the setup stage and then for each number drawn the sever could run a private set-membership test with each player and at the end the user who claims to have won has to open the commitment to prove that. (Of course this puts some amount of trust in the server which can probably be eliminated using proper Multi-Party Computation magic) $\endgroup$ – SEJPM Aug 22 '18 at 9:44
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How does the winner provide a zero-knowledge proof that their board contains the numbers? $\endgroup$ – Simon Shine Aug 22 '18 at 10:53
  • $\begingroup$ There is a zero knowledge proof for any problem in IP=PSPACE, and the problem here is obviously in NP. $\endgroup$ – Meir Maor Aug 22 '18 at 11:02
  • $\begingroup$ If you are looking for an elegant simple ZK proof like we have for Dlog or such, I'm not sure one exists. But it is sufficient for the prover to have a witness (the board) and for us to have a Polynomial time Turing machine to calculate the function $f$ described above. $\endgroup$ – Meir Maor Aug 22 '18 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.