[Haskell-cafe] Splittable random numbers
Richard Senington
sc06r2s at leeds.ac.uk
Thu Nov 4 14:27:36 EDT 2010
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
More information about the Haskell-Cafe
mailing list