[Haskell-cafe] Splittable random numbers

[Richard Senington]

I might have a use for this, so I could give it a go.
I'll have a look through this post in detail tomorrow morning.

RS

On 04/11/10 17:38, Simon Peyton-Jones wrote:
>
> Hi Cafe
>
> A while back there was a thread 
> <http://www.mail-archive.com/haskell-cafe@haskell.org/msg79633.html> 
> about a good implementation of a (pseudo) random number generator with 
> a good "split" operation.  There's lots of material on generators that 
> generate a linear *sequence* of random numbers, but much less on how 
> to generate a *tree* of random numbers, which is what Haskell's 
> System.Random API requires.
>
> I happened to meet Burton Smith recently, who wrote some early papers 
> about this stuff (eg "Pseudo random trees in Monte-Carlo 
> <http://portal.acm.org/citation.cfm?id=1746034>"), so I asked him.
>
> His reply is below, along with some follow-up comments from his 
> colleagues Tolga Acar and Gideon Yuval.   The generator uses crypto 
> functions, so it's probably more computationally expensive than common 
> linear-sequence generators, but in exchange you get robust splitting.
>
> Does anyone feel like taking the idea and turning it into a Haskell 
> library?   (Or even a Haskell Wiki page?)  I'm taking the liberty of 
> cross-posting to the libraries list.
>
> Simon
>
> *From:* Burton Smith
> *Sent:* Tuesday, November 02, 2010 3:58 PM
> *To:* Simon Peyton-Jones
> *Cc:* Gideon Yuval (Gideon Yuval); Tolga Acar
> *Subject:* Random number generation
>
> With some help from Gideon and Tolga, I think the solution to the 
> "arbitrary tree of random numbers problem" is as follows:
>
> The generator G is a pair comprising a crypto key G.k and an integer 
> counter (the "message") G.c.  The (next G) operation returns a pair: 
> 1. a random integer r obtained by encrypting G.c with G.k, and 2. a 
> new generator G' such that G'.k = G.k and G'.c = G.c + 1.  The (split 
> G) operation is similar, returning the same G', except that instead of 
> returning a random integer r it returns a third generator G'' such 
> that G''.k = r and G''.c = 0.
>
> A suitable block cipher system might be 128-bit AES (Rijndael).  
> Unencumbered implementations exist in a variety of languages, and 
> performance is pretty good and will improve dramatically as hardware 
> support improves.  I'd pick both crypto key size and the size of the 
> result r to be 128 bits, and employ a  64 bit counter c.  Other crypto 
> options exist.
>
> *From:* Simon Peyton-Jones
> *Sent:* Wednesday, November 03, 2010 3:11 AM
> *To:* Burton Smith; Gideon Yuval (Gideon Yuval)
> *Cc:* Tolga Acar; Simon Peyton-Jones
> *Subject:* RE: Random number generation
>
> Burton, Gideon, Tolga
>
> Aha, that's interesting.   I'd never seen a random number generator 
> based on crypto, but it seems like an attractive idea.  As I 
> understand it, successive calls to 'next' will give you
>
>           encrypt(0), encrypt(1), encrypt(2), encrypt(3),....
>
> Is this standard?  Does it have provably good randomness properties, 
> (cycle length, what else?) like other RNGs?  Or does it simply seem 
> very plausible?
>
> Can I send it round to the Haskell mailing list, in the hope that 
> someone will turn the idea into a library?   (Ideally I'd like to make 
> claims about the randomness properties in doing so, hence my qns above.)
>
> *From:* Gideon Yuval (Gideon Yuval)
> *Sent:* Wednesday, November 03, 2010 7:15 AM
> *To:* Simon Peyton-Jones; Burton Smith
> *Cc:* Tolga Acar
> *Subject:* RE: Random number generation
>
> As long as the key, and the non-counting part of the counter, are 
> kept" secret", anyone who can distinguish these pseudorandoms from 
> real random, in less than 2^128 steps, has a nice paper for 
> crypto-2011 (this is known as "provable security") concerning a 
> weakness in AES128.
>
> One exception: real randoms have a birthday paradox; the pseudorandoms 
> suggested do not. If you care, you can:
>
> (1) Limit the counter to 2^32 steps (paradox has 2^-64 probability) or 
> even 2^16 (2^-96), then rekey; or
>
> (2) XOR 2 such encrypted counters, with different keys; or
>
> (3) XOR *_3_* successive values for the same counter (just possibly 
> cheaper; top-of-head idea).
>
> More hard-core: swap the position of key & message: encrypting a 
> constant "secret" with 1,2,3,4.... Gives pseudorandoms with *_no_* 
> birthday paradox.
>
> *From:* Tolga Acar
> *Sent:* 03 November 2010 15:50
> *To:* Gideon Yuval (Gideon Yuval); Simon Peyton-Jones; Burton Smith
> *Subject:* RE: Random number generation
>
> Simon,
>
> The general idea is not really that new in the crypto area with 
> constraints Gideon describes, of course. That is typically called a 
> PRNG -- Pseudo Random Number Generator, or in another parlance, 
> Deterministic Random Bit Generators (DRBG). The DRBG constructions 
> based on hash functions and block ciphers are even standardized in 
> NIST publication SP800-90 (even though I may not recommend every one 
> of them).
>
> As for the construction below, that is based on the AES block cipher, 
> that essentially takes advantage of the PRP (Pseudo Random 
> Permutation) property of the AES block cipher, as each block cipher 
> ought to be. So, as Gideon outlines below, if you fix the key, the PRP 
> gives you a random-looking (or, in other terms, indistinguishable from 
> random) output that no one without the secret key and the "state" can 
> generate or easily predict. Assuming an ideal cipher (and AES is a 
> close approximation to it), the probability is believed to be the 
> birthday paradox - no counterexample or a proof exists without 
> assumptions; so we stick to the birthday bound.
>
> There ought to be papers on this somewhere. If not, that condensed 
> information is spread across many papers and is part of the crypto 
> folklore, I'd say.
>
> *From:* Burton Smith
> *Sent:* 03 November 2010 19:03
> *To:* Simon Peyton-Jones
> *Cc:* Gideon Yuval (Gideon Yuval); Tolga Acar
> *Subject:* RE: Random number generation
>
> Just two points of further clarification:
>
> 1.  All PRNGs used in the technical computing space fail the birthday 
> paradox criterion (/i.e. /have full period), so we really need not 
> worry about this.  Also, there are other mitigating factors, /e.g./ 
> suppose we are using the PRNG to generate pseudorandom residues mod n 
> << 2^128; the paradox is happily present there.
>
> 2. The big innovation in this scheme is that the rekeying operation 
> done by split creates a new generator with  independence guaranteed by 
> "provable security" in the sense Gideon mentioned -- if someone can 
> find something nonrandom in the correlation between G' and G'', say, 
> then it amounts to a weakness in AES128 and is publishable.  So it's 
> yet another example of reducibility, common in our field: "if you can 
> easily transform a known/famous hard problem P into this other problem 
> Q, Q must be hard".
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>    

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20101104/78f4132d/attachment-0001.html