[Haskell-cafe] Splittable random numbers

[Lauri Alanko]

On Sat, Jan 22, 2011 at 12:40:04AM -0500, Ryan Newton wrote:
> On Wed, Nov 10, 2010 at 11:33 AM, Lauri Alanko <la at iki.fi> wrote:
> > So a naive implementation of split would be:
> >
> > split g = (mkGen seed, g')
> >  where (seed, g') = random g
> 
> Just to be clear, that is the same as Burton Smith's original proposal that
> Simon mentioned at the outset, right?  Specifically, Smith's proposal is
> yours instantiated with a crypto based PRNG?

Yes, I realized this in hindsight. I hadn't read Smith's proposal
fully and didn't expect it to be so simple.

My own interest in this discussion actually came from an OCaml
project, where I needed an operation to generate new RNGs:

val split : Random.State.t -> Random.State.t

The obvious idea was just to create a new RNG by using a randomly
generated seed:

let split s =
  Random.State.make (Array.init 55 (fun _ -> Random.State.bits s))

However, I remembered years ago reading in the source of the Haskell
Random module that splitting RNGs robustly is supposed to be an open
problem so I wondered what the issue is. Since random numbers came up
on the Haskell mailing list at the same time, I decided to ask. But
since Burton apparently came up with the same solution, using AES in
counter mode as the RNG, maybe there is no issue after all. Except
perhaps performance? Is this approach less robust with a faster,
non-cryptographic RNG?

> So, except for the silliness of generating 128 random bits to make an Int,
> the following would implement the strategy using the "crypto" package on
> Hackage, correct?

> next128 (RNG k c) = (encrypt k c, RNG k (c+1))

To my understandind that's indeed using AES in counter mode, but I'm
no crypto expert.


Lauri