[Cryptography] Real-world crypto/PRNG problem: Bridge

[Tom Mitchell]

On Mon, Aug 22, 2016 at 10:34 AM, Christian Huitema <huitema at huitema.net>
wrote:

> 48 bits of state is obviously not enough for generating decks of bridge.
>
> Given a 52 card deck, there are about 5.36E28 possible decks, 6.35E11
> possible hands, and 5.16E21 possible pairs of hands. This implies that each
> deck can reveal more than 95 bits of information.


Good stuff.
Since a player can organize their cards in their hand the order that they
are dealt would seem unimportant yet that order might signal the specifics
of all the other cards on the table once the PRNG and seed have been
discovered.
The difference between 5.36E28 possible decks & 6.35E11 possible hands
is quite large so the "signal" is possibly very large.

The generator should be able to generate all possible hands.  If not the
ability
to cheat changes.   A linear congruential generator PRNG will repeat after
N but knowing if all possible sets of hands would be presented is a more
difficult
question.  Generating each possible hand with equal probability is hard for
a PRNG.

Analysis of PRNGs would have focused on the distribution of bits and bytes.
Sequences that map to possible hands of cards not so much.  In any deck the
set of cards is fixed to 52 unique cards so a lot of bits will get tossed
while filling
in a deck/hand this discarding of bits further reduces the length of the
PRNG
series before it cycles.  The PRNG might be used to shuffle a deck more
efficiently
than generate a deck and could result in more efficiency.

The nature of the tourney play is important.   In some tournaments the
cards are presented
in a special bridge board so they can be played by many others.   In
filling the board the cards
can be physically shuffled in ways that limit the ability of a hand to
signal the
possible hands.  i.e. In tournaments the same hand is played on many tables
often at the same tome and player skill is tabulated.  Tell more about how
the tourney
play is conducted.  https://en.wikipedia.org/wiki/Duplicate_bridge

A machine that can see one hand can help a lot with bidding if there
is some prior analysis that discovers limits in the  deal.   Bidding and
play are
both part of the game... with quality players a small advantage could be
decisive.

The inability of a PRNG to generate all possible hands equally could insert
bias that if understood could lead to an advantage.

It sounds as if the methods are good enough for now but more work and
analysis is needed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160823/0c883b53/attachment.html>