[Cryptography] Say 'unguessable' not random

[Ray Dillinger]

On 08/25/2016 07:19 AM, Phillip Hallam-Baker wrote:

> So for the bridge contest, why not get rid of the random numbers altogether
> and instead employ a commitment scheme in which each of the players
> introduce as much unguessability into the seed as they like? There would
> have to be some form of trusted party that would take in the encrypted
> seeds, decrypt them, prepare the hands and then release the seeds at the
> end so the process can be audited. But the seeds themselves need not be
> 'random'.

The Poker Protocol keeps getting reinvented.  I thought I invented it,
but Adam Back got there before me and Bruce Schneier got there before
he.

Each participant chooses a key and derives a long sequence from it
by hashing.  Play starts with each player revealing the last element
of their sequence.  After that, "random" elements are determined by
having all the participants reveal the hash preimage of the number
they most recently revealed.  These elements are combined (usually
via XOR) to determine the choice.

Because nobody can find a preimage of anybody else's hash function,
nobody can predict what the forthcoming numbers from anybody else's
sequence of preimages will be (and therefore discover what the next
'random' element is).

Because nobody can prevent the other players from noticing any
number they present which isn't a correct preimage of the last
number they presented, nobody gets a chance to pick a number
giving their preferred output, even if they have already seen
the numbers presented by all the other players before they give
theirs.

Because everybody knows when placing bets (or whatever) that they
haven't yet revealed the number that will be used for *their*
contribution to the next choice, yet, nobody else has looked at
it before placing their own bet (or whatever).

And after the fact anybody can audit the preimage chains and make
sure they all match up.

No Trent is required; bandwidth requirements are minimal.  The
requirements for cheating amount to finding the preimages for
everybody's most recent revealed sequence element.  Or breaking
into everybody's computer and stealing the next preimage without
their knowledge.  But if there is a single player out there who
can keep you out of their system and whose hash you can't
preimage, it doesn't work.

It's even suitable for a pure serverless P2P implementation.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160825/60263b95/attachment.sig>