<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Verdana","sans-serif";
color:windowtext;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:582643434;
mso-list-type:hybrid;
mso-list-template-ids:153270398 949516180 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:"\(%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level2
{mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level3
{mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level4
{mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level5
{mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level6
{mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level7
{mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level8
{mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">Hi Cafe<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">A while back there was a
<a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg79633.html">thread</a> 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
<b>sequence</b> of random numbers, but much less on how to generate a <b>tree</b> of random numbers, which is what Haskell’s System.Random API requires.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">I happened to meet Burton Smith recently, who wrote some early papers about this stuff (eg “<a href="http://portal.acm.org/citation.cfm?id=1746034">Pseudo random trees in Monte-Carlo</a>”),
so I asked him. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:
"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:"Tahoma","sans-serif""> Burton Smith
<br>
<b>Sent:</b> Tuesday, November 02, 2010 3:58 PM<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> Gideon Yuval (Gideon Yuval); Tolga Acar<br>
<b>Subject:</b> Random number generation<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">With some help from Gideon and Tolga, I think the solution to the “arbitrary tree of random numbers problem” is as follows:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:
"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:"Tahoma","sans-serif""> Simon Peyton-Jones
<br>
<b>Sent:</b> Wednesday, November 03, 2010 3:11 AM<br>
<b>To:</b> Burton Smith; Gideon Yuval (Gideon Yuval)<br>
<b>Cc:</b> Tolga Acar; Simon Peyton-Jones<br>
<b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D">Burton, Gideon, Tolga<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D">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<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D"> encrypt(0), encrypt(1), encrypt(2), encrypt(3),....<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D">Is this standard? Does it have provably good randomness properties, (cycle length, what else?) like other RNGs? Or does it simply seem very plausible?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Verdana","sans-serif";
color:#1F497D">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.)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:
"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:"Tahoma","sans-serif""> Gideon Yuval (Gideon Yuval)
<br>
<b>Sent:</b> Wednesday, November 03, 2010 7:15 AM<br>
<b>To:</b> Simon Peyton-Jones; Burton Smith<br>
<b>Cc:</b> Tolga Acar<br>
<b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">One exception: real randoms have a birthday paradox; the pseudorandoms suggested do not. If you care, you can:<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo1"><![if !supportLists]><span lang="EN-US" style="color:#1F497D"><span style="mso-list:Ignore">(1)<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span lang="EN-US" style="color:#1F497D">Limit the counter to 2^32 steps (paradox has 2^-64 probability) or even 2^16 (2^-96), then rekey; or<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo1"><![if !supportLists]><span lang="EN-US" style="color:#1F497D"><span style="mso-list:Ignore">(2)<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span lang="EN-US" style="color:#1F497D">XOR 2 such encrypted counters, with different keys; or<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo1"><![if !supportLists]><span lang="EN-US" style="color:#1F497D"><span style="mso-list:Ignore">(3)<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span lang="EN-US" style="color:#1F497D">XOR </span>
<b><u><span lang="EN-US" style="color:red">3</span></u></b><span lang="EN-US" style="color:#1F497D"> successive values for the same counter (just possibly cheaper; top-of-head idea).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">More hard-core: swap the position of key & message: encrypting a constant “secret” with 1,2,3,4…. Gives pseudorandoms with
</span><b><u><span lang="EN-US" style="color:red">no</span></u></b><span lang="EN-US" style="color:#1F497D"> birthday paradox.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:
"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:"Tahoma","sans-serif""> Tolga Acar
<br>
<b>Sent:</b> 03 November 2010 15:50<br>
<b>To:</b> Gideon Yuval (Gideon Yuval); Simon Peyton-Jones; Burton Smith<br>
<b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Simon,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">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).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:
"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:"Tahoma","sans-serif""> Burton Smith
<br>
<b>Sent:</b> 03 November 2010 19:03<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> Gideon Yuval (Gideon Yuval); Tolga Acar<br>
<b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Just two points of further clarification:<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt"><span lang="EN-US" style="color:#1F497D">1.</span><span lang="EN-US" style="font-size:7.0pt;
font-family:"Times New Roman","serif";color:#1F497D">
</span><span lang="EN-US" style="color:#1F497D"> All PRNGs used in the technical computing space fail the birthday paradox criterion (<i>i.e.
</i>have full period), so we really need not worry about this. Also, there are other mitigating factors,
<i>e.g.</i> suppose we are using the PRNG to generate pseudorandom residues mod n << 2^128; the paradox is happily present there.<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt"><span lang="EN-US" style="color:#1F497D">2.</span><span lang="EN-US" style="font-size:7.0pt;
font-family:"Times New Roman","serif";color:#1F497D">
</span><span lang="EN-US" style="color:#1F497D">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”.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""><o:p> </o:p></span></p>
</div>
</body>
</html>