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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
