combining entropy

[Leichter, Jerry]

On Sat, 25 Oct 2008, John Denker wrote:

| On 10/25/2008 04:40 AM, IanG gave us some additional information.
| 
| Even so, it appears there is still some uncertainty as to
| interpretation, i.e. some uncertainty as to the requirements
| and objectives.
| 
| I hereby propose a new scenario.  It is detailed enough to
| be amenable to formal analysis.  The hope is that it will
| satisfy the requirements and objectives ... or at least
| promote a more precise discussion thereof.
| 
| We start with a group comprising N members (machines or 
| persons).  Each of them, on demand, puts out a 160 bit 
| word, called a "member" word.  We wish to combine these 
| to form a single word, the "group" word, also 160 bits 
| in length.
This isn't enough.  Somehow, you have to state that the values emitted
on demand in any given round i (where a round consists of exactly one
demand on all N member and produces a single output result) cannot
receive any input from any other members.  Otherwise, if N=2 and member
0 produces true random values that member 1 can see before it responds
to the demand it received, then member 1 can cause the final result to
be anything it likes.

This is an attack that must be considered because you already want to
consider the case:

|  b) Some of [the members] are malicious.  Their outputs may appear
|   random, but are in fact predictable by our adversary.

Stating this requirement formally seems to be quite difficult.  You can
easily make it very strong - the members are to be modeled as
probabilistic TM's with no input.  Then, certainly, no one can see
anyone else's value, since they can't see *anything*.  But you really
want to say something along the lines of "no malicious member can see
the value output by any non-malicious member", which gets you into
requiring an explicit failure model - which doesn't fit comfortably with
the underlying problem.

If the issue is how to make sure you get out at least all the randomness
that was there, where the only failures are that some of your sources
become predictable, the XOR is fine.  But once you allow for more
complicated failure/attack modes, it's really not clear what is going on
and what the model should to be.
							-- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com