21
$\begingroup$

I'm able to find a lot of scattered papers on the development of mental poker since RSA proposed the initial solution but no recent report (i.e. after 2005) on what is the status of the problem, eg:

  • What are the remaining open problems/challenges?
  • Can we call it solved? For example, has the "dropout" problem been solved (e.g. [1] suggests so, but has it been verified?)?
  • Have the performance problems been solved ?

  • Is there an implementation of the algorithms / protocols ?

  • What is the latest performance improvements (e.g. is [2] up to date to the fastest protocols known)?

[1] http://crises-deim.urv.cat/webCrises/publications/isijcr/lncs3592dropout.pdf
[2] http://www.nongnu.org/libtmcg/libTMCG.pdf

$\endgroup$

1 Answer 1

17
$\begingroup$

All the know problems have been solved and currently there is, at least, one practical and secure Mental Poker protocol.

Check this patent application:

The protocol described is called MPF (Mental Poker Framework).

Detailed answers to your points:

What are the remaining open problems/challenges?

The main problem still unsolved is how to enforce players to act (show a card, bet, pass) before a certain time limit, in a purely peer to peer network, since a timestamping service would add a TTP to the protocol.

Also I have my own unproven conjecture: Semantic security is incompatible with abrupt drop out tolerance (without a threshold scheme). Both cannot be present at the same time in a MP protocol.

Can we call it solved? For example, has the "dropout" problem been solved (e.g. 1 suggests so, but has it been verified?)?

Since a deck that is encrypted with players private keys cannot be recovered if a player quits (at least not without a threshold scheme), one way to solve the drop out problem (as shown in the patent) is to create a fresh new deck, where the cards that were in possession of the player that has left return to the new deck. This is done by creating a new shuffled deck and then removing the cards that were in possession of the players, without revealing which cards are removed. This is the best possible solution.

Have the performance problems been solved?

Yes, it takes less than 10 seconds to shuffle a 52 card deck by 6 players using the algorithm published in the patent.

Is there an implementation of the algorithms / protocols?

I have my own implementation, but it's not tidy enough to put in public domain. I should.

What is the latest performance improvements (e.g. is [2] up to date to the fastest protocols known)?

IMHO the last performance improvements come to what I called Simultaneous Zero Knowledge Proofs. In SimZNK all parties cooperate to prove their private operations (shuffle and re-encryption) are correct.

If a player tries to cheat, then the player having cheated is detected at the end of the shuffle stage (when all players have shuffled the deck, but before the game starts). Afterwards, the process can be restarted without having leaked any private information of any value.

This verification scheme is much faster than verification (either by interactive or non-interactive ZNPs) after each player shuffle and re-encrypts the cards.

$\endgroup$
1
  • $\begingroup$ Has this changed in the year and half since the reply ? Any word on ever so kindly releasing your implementation, SDL ? $\endgroup$
    – bobjandal
    Commented Jan 17, 2014 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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