[Cryptography] Mapping numbers to permutations

[Viktor Dukhovni]

On Thu, Dec 04, 2014 at 11:02:48AM -0800, Ray Dillinger wrote:

> And the usual solution is....
> 
> > Whenever a forbidden state is reached, you throw
> > away your $k$ inputs and try another $k$.
> 
> To throw away any base-5 number you get that isn't also in the
> range of the highest binary power that's less than the quintenary
> power. But that throws away those base-5 digits, and the result
> is that you get a mapping from input stream to output stream which
> is a many-to-one mapping, ie, it's not invertible, so there are
> a bunch of useful operations that don't work with it as a keystream
> or a couple of other things.

Depends on one's perspective, one might consider that the original
stream simply never contained the discarded states, and then the
mapping is 1-to-1 on the restricted states.

> The technique I posted about was a way to get an unbiased stream
> of binary bits that has a one-to-one mapping to the input stream,
> ie, there is only a single sequence of base-5 digits that could
> result in a particular binary stream.

The technique you posted provably fails.  There is no function that
maps an odd number of uniformly random (unbiased) inputs to a
uniformly random (unbiased) even number of outputs.

This is a trivial counting argument.  The probability p(O) of any
output state O is equal to the fixed probability p of each input
state I multiplied by the number of input states N(O) that map to
O.

    p(O) = N(O) * p

If p(O) is independent of O (no bias) then N(O) = N(O') = N for
all output states O, O'.  Which means that the number of input
states #I = #O * N.  Which of course means that #O is a divisor of
#I.  Since no power of 2 divides any power of 5, no such function
exists.

Note that your generator cannot wait forever to see the entire
infinite stream of base 5 digits before it produces a corresponding
infinite stream of base 2 digits.  It needs to output at least one
bit after seeing a finite number of base 5 digits.

Suppose that finite number is bounded independently of the input
stream by some number K.  Then for each of the equvi-probable 5^K
input states you need to output either 0 or 1 as the first output
bit.  But with an odd number of equi-probable inputs you cannot
generate an equi-probable 1-bit output (partition an odd cardinality
set into two equi-numerous subsets).

So no procedure that outputs the first bit in bounded time can be
unbiased.  In particular there are arbitrarily long input streams
that produce no bits of output.  If output is never produced only
after seeing countably infinitely many input digits, then by Zorn's
Lemma there is an infinitely long input stream that produces no
output, and the mapping cannot be one-to-one.

I think I have proved that discards are required to avoid bias.
So either your scheme or the proof is incorrect.

-- 
	Viktor.