11 ms·

On Melissa O’Neill’s PCG random number generator

104 points by ozanonay 9y ago

lisper 9y ago
This is an interesting article, but it's more about the changing landscape of academic publishing than it is about random number generators. [EDIT] The actual paper is here: http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
- pedrocr 9y ago
  Only if it turns out the work is actually good. If not this is exactly what should happen in peer review.
  - lisper 9y ago
    You don't think the peer review process ever produces false negatives?
    - tptacek 9y ago
      You didn't ask me, but I'll confirm that it definitely does.
    - deleted 9y ago
      [deleted]
    - dsacco 9y ago
      The peer review process absolutely produces false negatives, but that doesn't really change the fact that this paper doesn't need to be nearly 60 pages, doesn't sufficiently analyze one of its central premises (6.2.2 Security Considerations) and in general focuses on treatise and levity rather than rigor.
      - User23 9y ago
        Peer review is basically just proof-reading, and taking 60 pages to present 10 pages of findings is exactly the kind of thing a proof-reader should catch.
  - CalChris 9y ago
    That is exactly what peer review should do, to determine whether the idea has merit. But that isn't what has happened. Peer review which is a cornerstone to the academic/scientific community stumbled on style and didn't get to merit.
    - dsacco 9y ago
      I disagree, I think the peer review functioned exactly as it was supposed to. Her paper doesn't pass the sniff test for me whatsoever when it comes to security analysis. She spent close to no time analyzing the primitives she introduced (and with no proofs or rigor!), meanwhile the thing is 58 pages because she takes the time to explain what "determinism" and "seeds" are to her audience. "Exposition" is, in my opinion, a fully valid reason to reject a paper. I'm not going to sit and read your 60 page paper that could have been compressed to 10 pages if you just got to the point and assumed your audience understood the field well enough to assess your results. Rewrite it and send it back without the assumption that your audience needs to be reminded of everything they'd need to learn just to properly assess your result. It's not as though they rejected the paper on empirical grounds without a meritocratic review; they rejected it because they have a finite amount of time and (speaking as someone in the field) it's sort of annoying to read after page 10. I think academia frequently gets lost in the ivory tower and loses touch with what an accessible paper looks like; this is not an answer to that, it's a swing in the other direction, where papers with truly novel results will suddenly be hundreds of pages and tens of pages of setup.
      - CalChris 9y ago
        If you don't like it then don't read it or don't publish it. But sniff test and exposition are style. Ding it for not analyzing her primitives but don't then call that security analysis. Do the security analysis. In patents there's the concept of enablement: did the inventor enable/teach the idea? Yes she did. Did she flesh out every idea? No she didn't. This was rejected on style grounds. Ignoring it then on 'security analysis' is not improving matters; it certainly isn't helping security. Do the security analysis.
        9y ago
lowmagnet 9y ago
I like this because she is a professor at Harvey Mudd. They took steps to make CS more inclusive, with great results. I appreciate her attitude on accessibility, which is in keeping with that institution's philosophy. That she ran into a paper wall doesn't bother her because she's openly publishing is even better.
- CalChris 9y ago
  I watched her EE380 talk [1] and thought she was a fine professor for a difficult (to me) subject. That she didn't get published for at best stylistic reasons means nothing. [1] https://ee.stanford.edu/event/seminar/ee380-computer-systems-colloquium-family-better-random-number-generators https://ee.stanford.edu/event/seminar/ee380-computer-systems...
- dsacco 9y ago
  Regardless of her attitude on academic accessibility, it is inappropriate for a paper introducing a novel primitive with proposed security considerations to spend the time explaining why determinism is a concern in functions dealing with randomness. This paper could have been 10 pages. If you want to make your research more accessible, there are ways to do that without assuming that your reader is coming in from a dead start on the field.
  - mathperson 9y ago
    I am not sure why you are being downvoted. I think this is clearly true. An easy way to make research accessible is to write a monograph!
- thanatropism 9y ago
  There's room for accessible and for abstruse literature. Usually what happens with novel work is that initial publications are abstruse but met with excitement by the scholarly community and gradually more accessible works (as the number of collaborators/coauthors grows too) are published. That said, even if multi-culti math means that top-line researchers are going to be spending time with song-and-dance introductions, she should still have put a grad student onto the task of making the short paper that experts will actually read. If the whole thing is a matter of style and not of obfuscation, this would have given a grad student an easy, cool first publication.
deleted 9y ago
[deleted]
mjb 9y ago
> I wonder whether the academic publications are growing ever less relevant to practice. I think there are two topics here. One is whether academic research and work is becoming less relevant to practice. The other is whether the formalism of academic-style publishing are becoming less relevant to the modern world where more and more venues for publishing, rating, and discovering work. On the former, I believe that academic work is as relevant as ever. There are some areas (like systems) where I'm doubtful about relevance from the point of view of a practitioner, but other areas (like hardware and ML where work remains extremely relevant). I haven't noticed a trend there over the last decade, except in some areas of systems where the industrial practice tends to happen on cluster sizes that are often not approachable for academia. On the latter, academic publication does indeed seem to be getting less relevant. There are other (often better) ways to discover work. There are other ways to tell whether a piece of work is relevant, or credible. There are other, definitely better, ways to publish and distribute work. In some sense I think this is a pity: as an academic-turned-practitioner I like academic-style publications. Still, I think they are going to either change substantially or die. This article raises another very good point: sometimes the formalism of academic publication makes the work harder to understand, less approachable, or less valuable. That's clear harm, and it seems like this professor was right to avoid that.
FRIEDCHICKEN 9y ago
I wouldn't trust any PRNG written by a girl.
drallison 9y ago
Melissa O'Neill gave a talk describing the PCG random number generator at Stanford in EE380. https://www.youtube.com/watch?v=45Oet5qjlms https://www.youtube.com/watch?v=45Oet5qjlms
Animats 9y ago
Here's the site for the random number generator.[1] It's basically a simple linear congruential random number generator (well known, but not very good) fed into a mixer. The mixer is new. Most of the analysis is about the LCG or the final output. The suggested mixer is just output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122); That's simple, and the insight in this paper is that something that simple helps a lot. I would have thought that you'd want a mixer where changing one bit of the input changes, on average, half the bits of the output. The mixer above won't do that. DES as a mixer would probably be better, but it's slower. The new result here is that something this simple passes many statistical tests. This isn't crypto-grade; both that mixer and a LCG generator are reversible with enough work. [1] http://www.pcg-random.org/ http://www.pcg-random.org/
- tptacek 9y ago
  It's a weird paper. It's quite long and takes an eternity to reach this simple point. It's also littered with "security concerns" which are confusing at best and misleading at worst; in reality, none of the generators it discusses are suitable for "sensitive applications", even in the corner-case scenario it discusses of needing permutations of all the b-bit integers, a problem we already have cryptographic tools to solve. But I'll confess to not really understanding what all the fuss is about insecure generators.
  - Animats 9y ago
    Linear congruential generators (x = k1*x + k2, unsigned with truncation on overflow) have some strange properties, some of which the paper explores. If you repeatedly take three sequential values from one and treat them as 3D coordinates, the points line up in parallel planes. (There's an explanation of why in Knuth.) Something has to be done to destroy that order. The solution here is to XOR the upper and lower halves of the 128-bit state to get 64 bits, then circular shift that by the high 6 bits of the 128-bit input. This passes most of the classic tests for random number generators. That's the paper, basically.
    - DonbunEf7 9y ago
FabHK 9y ago
A few notes: The author writes "Meanwhile, at least one influential researcher (whose work I respect) had harsh words publicly for her result", and then quotes some of these words: Note that (smartly enough) the PCG author avoids carefully to compare with xorshift128+ or xorshift1024*. However, the author fails to note that said "influential researcher", Sebastiano Vigna, is the author of xorshift128+ and related PRNG. In the linked test [2] by John D. Cook (who uses PactRand, a test similar to the (obsolete) DIEHARD), xorshift128+ and xoroshir0128+ fail within 3 seconds, while PCG ran 16 hours producing 2 TB of pseudo-random numbers without any suspicious p-value detected. On the other hand, Vigna claims that the xoroshiro family does "pass" PactRand. I've submitted an answer to StackOverflow a while ago [1], recommending xoroshiro and PCG, thus I'd be concerned if PCG turns out to be flawed. It's actually quite hard to get academics in the field to give an authoritative recommendation (I've tried) - their response is typically along the line "It's complicated"... [1] https://stackoverflow.com/questions/4720822/best-pseudo-random-number-generator/38202922#38202922 https://stackoverflow.com/questions/4720822/best-pseudo-rand... [2] https://www.johndcook.com/blog/2017/08/14/testing-rngs-with-practrand/ https://www.johndcook.com/blog/2017/08/14/testing-rngs-with-... Edit: remove italics due to asterisk in PRNG name, & add link to John. D Cook's test.
- MiceWithYaffle 9y ago
  I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) O'Neill has instructions on how to test with PractRand and with TestU01 on her blog (http://www.pcg-random.org/blog/ http://www.pcg-random.org/blog/). I had a go with TestU01 on Vigna's generators, and when you test the low 32 bits reversed (for 64-bit PRNGs, you have to test the high 32, the low 32, both forwards and reversed), I found that all Vigna's generators fail. Given the PractRand results it makes sense, I guess, but I had read that Vigna's generators were supposed to pass TestU01. Does anyone else wants to have a go at testing so I can know if I screwed up somehow?
  - rockdoe 9y ago
    I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) The code does explain exactly what the issue is, i.e. that the last bit isn't random: This generator passes the PractRand test suite up to (and included) 16TB, with the exception of binary rank tests, which fail due to the lowest bit being an LFSR; all other bits pass all tests. We suggest to use a sign test to extract a random Boolean value. But I'm tempted to agree this isn't a desirable property for a generic RNG. How many users of JavaScript know about this property? (it's the default RNG for most browser engines) Or does it not matter because they return 53-bit floats?
the_stc 9y ago
As a general comment, I dislike deliberately obtuse writing in papers. In my current work, I came across a very in-depth survey of our industry (sex work). Excellent study, very helpful. But some of the sentences seemed to over-complicate the math. Example: "Consider the set P {p1, p2, ... pN} representing providers and the set C {c1, c2, ... cN} representing customers". I am pretty sure this kind of stuff is filler or pretends to make things look more rigorous than they are. On the other hand, maybe spending more than a line explaining what the birthday paradox is should be cut out and put in a backgrounder paper or appendix so that the paper can focus on the actual novel ideas.
- dsacco 9y ago
  > On the other hand, maybe spending more than a line explaining what the birthday paradox is should be cut out and put in a backgrounder paper or appendix so that the paper can focus on the actual novel ideas. That was my annoyance with the paper as well. Add to that explanations that amount to, "What even is determinism?" or "What's a seed?" and I'm unsurprised it's nearly 60 pages.
- mathperson 9y ago
  are you joking? That is your example of abstruse mathematical notation? Some variables with names?!
  - the_stc 9y ago
    No. I am saying that giving the definition of a set each time is just extra verbosity. The whole paper had that extra verbiage, everywhere. Kind of why-use-one-word-when-ten-will-do feeling.
    - mathperson 9y ago
      Could you share the paper? I mean if they were making a mathematical argument...it is kind of hard to do that without defining things..
      - 9y ago
bmm6o 9y ago
It sounds like an interesting result, I look forward to reading the paper more carefully. That said, it's clearly not written for an academic journal. Section 2.4.3 is entitled "The Importance of Code Size", and explains why shorter code is better. I think you can argue that some academic papers are excessively concise, but this is a 58-page paper about an RNG. It is clearly not a journal paper and has a ton of extraneous content. I have to sympathize with the commenter that the author has made a trade-off and written a paper that's less rigorous than it should be (for peer review). I wonder why she didn't write 2 versions.
- wadkar 9y ago
  > I wonder why she didn't write [two] versions. Because the reviewers took over 10 months to respond with a rejection mainly citing the length of the paper. And more importantly, "By that point, everyone who might have wanted to read it had almost certainly found it here and done so, so I saw little merit in drastically shortening the paper."[1] She has updated the blog post which discusses all the nuanced details of the whole affair last month (2017-07-25)[2]. [1] http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html [2] http://www.pcg-random.org/posts/history-of-the-pcg-paper.html http://www.pcg-random.org/posts/history-of-the-pcg-paper.htm...
  - bmm6o 9y ago
    There is no excuse for the journal to take so long to provide a response. At the same time, it seems to me that their response was entirely predictable. Or does the journal usually post such long articles directed at a general audience?
dsacco 9y ago
I have a few comments: 1. The paper itself[1] is extremely readable by the standards of most cryptography research. On one hand, this is great because I was able to follow the whole thing in essentially one pass. On the other hand, the paper is very long for its result (58 pages!), and it could easily do without passages like this one: Yet because the algorithms that we are concerned with are deterministic, their behavior is governed by their inputs, thus they will produce the same stream of “random” numbers from the same initial conditions—we might therefore say that they are only random to an observer unaware of those initial conditions or unaware of how the algorithm has iterated its state since that point. This deterministic behavior is valuable in a number of fields, as it makes experiments reproducible. As a result, the parameters that set the initial state of the generator are usually known as the seed. If we want reproducible results we should pick an arbitrary seed and remember it to reproduce the same random sequence later, whereas if we want results that cannot be easily reproduced, we should select the seed in some inscrutable (and, ideally, nondeterministic) way, and keep it secret. Knowing the seed, we can predict the output, but for many generators even without the seed it is possible to infer the current state of the generator from its output. This property is trivially true for any generator where its output is its entire internal state—a strategy used by a number of simple random number generators. For some other generators, such as the Mersenne Twister [35], we have to go to a little more trouble and invert its tempering function (which is a bijection; see Section 5), but nevertheless after only 624 outputs, we will have captured its entire internal state. That's a lot of setup for what is frankly a very basic idea. A cryptographer being verbose in their writing might briefly remind the reader of these properties with the first sentence, but they'd still likely do that with much more brevity than this. I understand wanting to make your research accessible, but for people who understand the field this detracts from getting to the "meat." It might make it harder to get through, but a 10-30 page result is preferable to a nearly 60-page one that assumes I know nearly nothing about the field. If I don't know these details very well, how can I properly assess the author's results? 2. The author's tone in her writing is something I take issue with. For example, passages like this one... Suppose that, excited by the idea of permutation functions, you decide to always improve the random number generators you use with a multiplicative step. You turn to L’Ecuyer’s excellent paper [25], and without reading it closely (who has time to read papers these days!), you grab the last 32-bit constant he lists, 204209821. You are then surprised to discover that your “improvement” makes things worse! The problem is that you were using XorShift 32/32, a generator that already includes multiplication by 747796405 as an improving step. Unfortunately, 204209821 is the multiplicative inverse of 747796405 (mod 2 32), so you have just turned it back into the far-worse–performing XorShift generator! Oops.* ...go a bit beyond levity. If you're trying to establish rigorous definitions and use cases to distinguish between generators, functions and permutations, this isn't the way to do it. This isn't appropriate because it doesn't go far enough to formalize the point. It makes it intuitive, sure, and that's a great educational tool! But it's a poor scenario to use as the basis for a problem statement - research is not motivated by the failure of an engineer to properly read and understand existing primitives, it's motivated by novel results that exhibit superior qualities over existing primitives. 3. The biggest grievance I have with this paper is the way in which it analyzes its primitives for cryptographic security. For example, this passage under 6.2.2 Security Considerations: In addition, most of the PCG variations presented in the next section have an output function that returns only half as many bits as there are in the generator state. But the mere use of a 2 b/2-to -1 function does not guarantee that an adversary cannot reconstruct generator state from the output. For example, Frieze et al. [12] showed that if we simply drop the low-order bits, it is possible for an adversary to discover what they are. Our output functions are much more complex than mere bit dropping, however, with each adding at least some element of additional challenge. In addition, one of the generators, PCG-XSL-RR (described in Section 6.3.3), is explicitly designed to make any attempt at state reconstruction especially difficult, using xor folding to minimize the amount of information about internal state that leaks out.17 It should be used when a fast general-purpose generator is needed but enhanced security would also be desirable. It is also the default generator for 64-bit output. That's not a rigorous analysis of a primitive's security. It is an informal explanation of why the primitive may be secure, but it so high level that there is no proof based on a significant hardness assumption. Compare this with Dan Boneh's recent paper, "Constrained Keys for Invertible Pseudorandom Functions"[2]. Appendices A and B after the list of references occupy nearly 20 pages of theorems used to analyze and prove the security of primitives explored in the paper under various assumptions. Novel research exploring functions with (pseudo)random properties is inherently mathematical; it's absolutely insufficient to use a bunch of statistical tests, then informally assess the security of a primitive based on the abbreviated references to one or two papers. _________ 1. http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf 2. https://eprint.iacr.org/2017/477.pdf https://eprint.iacr.org/2017/477.pdf
fwdpropaganda 9y ago
Physicist here. Off-topic > And it is not even entirely clear what “really random” would mean. It is not clear that we live in a randomized universe… At the quantum level it really is clear that we live in a really random universe. What's the meaning of really random? The outcome of a quantum process. On-topic. Yeah, you have to know your audience. As OP mentions, just because the paper wasn't published doesn't prevent anyone from thinking about it and even building on it. On the other hand these scientific publications have styles and target audiences, and maybe she got rejected not due to lack of relevance or rigor, but because the paper didn't match the publication's non-scientific criteria for publication.
- eridius 9y ago
  A quantum process is a random process, but isn't it still an open philosophical question as to whether the "random process" we observe is truly random, or is instead governed by deterministic hidden state?
  - fwdpropaganda 9y ago
    No, all theories of (local) hidden variables have been experimentally ruled out. https://en.wikipedia.org/wiki/Bell%27s_theorem https://en.wikipedia.org/wiki/Bell%27s_theorem > Bell's theorem states that any physical theory that incorporates local realism cannot reproduce all the predictions of quantum mechanical theory. Because numerous experiments agree with the predictions of quantum mechanical theory, and show differences between correlations that could not be explained by local hidden variables, the experimental results have been taken by many as refuting the concept of local realism as an explanation of the physical phenomena under test. For a hidden variable theory, if Bell's conditions are correct, the results that agree with quantum mechanical theory appear to indicate superluminal effects, in contradiction to the principle of locality.
    - eridius 9y ago
      Interesting. But it sounds like non-local hidden variables are still possible. My assumption is that non-local hidden variables is non-falsifiable, which is why I said this was a philosophical question.
sulizilxia 9y ago
I love O'Neill's work on PCG, and loved the talks by her I watched online. As a tenured professor I want to say two things about this piece: 1. I think academic publishing will be forced to change. I'm not sure what it's going to look like in the end, but traditional journals are starting to seem really quaint and outdated now. 2. As far as I can tell from what she's written on the PCG page, the submission to TOMS is a poor example, because no one I know expects to be done with one submission. That is, no one I know submits a paper to one journal, even one reputable journal, and is done. They submit and it gets rejected and revise it and resubmit it, maybe three or even four times. After the fourth or fifth time, you might give up, but not necessarily even then. I have mixed feelings about the PCG paper as an example, because in some ways it's great: an example of how something very influential has superceded traditional academic publishing. In other ways, though, it's horrible, because it's misleading about the typical academic publishing experience. Yes, academic publishing is full of random nonsense, and corruption, but yes, you can also get past it (usually) with just a little persistence. In still other ways, it's a good example of what we might see increasingly, which is a researcher having a lower threshold for the typical bullshit out there.
Houshalter 9y ago
I once tried to develop my own fast random number generate using nothing but bitwise operations. On the theory they were the fastest/simplest. I had a program generate thousands of random combinations of bitwise functions. And then used statistical tests to see which ones produced the most "random" seeming behavior. It worked as far as I can tell. But I don't trust the statistical tests. Who is to say there isn't a very obvious pattern in the numbers that I didn't test for or notice? How do you prove a random number generator is good?
- thaumasiotes 9y ago
  > How do you prove a random number generator is good? You can't; that's the nature of randomness. You can prove they're bad, though.
- carapace 9y ago
  > How do you prove a random number generator is good? Compress its output.
- cgmg 9y ago
  A theoretical approach based on computability theory is https://en.m.wikipedia.org/wiki/Algorithmically_random_sequence https://en.m.wikipedia.org/wiki/Algorithmically_random_seque....
starmole 9y ago
As an engineer who switched to PCG: - PCG is not crypto, everybody should understand that. It's for simulation and rendering. - PCG mainly replaces Mersenne Twister which is in c++11. The Twister has a LOT more state and is a LOT slower for less randomness. - In rendering and simulation speed really matters, and PCG excels there. - Xorshift is another algorithm in the same class. I would really like to see an objective comparison. In my cursory engineering look PCG seemed better. - Fast PRNG is almost a new field again: It's not crypto, but immensely useful. How did the Twister get into C++11 while it is so much worse than PCG or Xorshift? Nobody cared! - Maybe PCG should have been a paper at SigGraph. - For the style of the paper, I think one contribution is rethinking PRNG outside crypto. That deserves and requires a lot of exposition.
- MiceWithYaffle 9y ago
  Yeah, it's not for crypto. But I think it's for more than simulation and rendering. It's meant as a general purpose PRNG. It's just as good for randomized algorithms like picking the pivot in quicksort, or playing games, procedural content generation (PCG!), or whatever you want to use it for. I think that the whole point of the prediction difficulty stuff is that a library (e.g., C++11's) with general purpose PRNGs can't know how they'll be used. Maybe some idiot write code for a gambling machine in C++ and use whatever PRNG is to hand. There was a story in the news the other week about people going around casinos predicting slot machines, so maybe this has already happened! PCG is trying to make your simulation and rendering code fast while trying to offer at least some defense against egregious misuse. Basically PCG is trying to be a good all rounder. As you say, it's meant as a replacement for the Mersenne Twister.
  - starmole 9y ago
    I found the story: https://www.wired.com/2017/02/russians-engineer-brilliant-slot-machine-cheat-casinos-no-fix/ https://www.wired.com/2017/02/russians-engineer-brilliant-sl... And yes, PCG is harder to exploit in this way than the Twister, but you still really should not bet money on it!

104 points by ozanonay 9y ago

This is an interesting article, but it's more about the changing landscape of academic publishing than it is about random number generators. [EDIT] The actual paper is here: http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

pedrocr 9y ago
Only if it turns out the work is actually good. If not this is exactly what should happen in peer review.
- lisper 9y ago
  You don't think the peer review process ever produces false negatives?
  - tptacek 9y ago
    You didn't ask me, but I'll confirm that it definitely does.
  - deleted 9y ago
    [deleted]
  - dsacco 9y ago
    The peer review process absolutely produces false negatives, but that doesn't really change the fact that this paper doesn't need to be nearly 60 pages, doesn't sufficiently analyze one of its central premises (6.2.2 Security Considerations) and in general focuses on treatise and levity rather than rigor.
    - User23 9y ago
      Peer review is basically just proof-reading, and taking 60 pages to present 10 pages of findings is exactly the kind of thing a proof-reader should catch.
- CalChris 9y ago
  That is exactly what peer review should do, to determine whether the idea has merit. But that isn't what has happened. Peer review which is a cornerstone to the academic/scientific community stumbled on style and didn't get to merit.
  - dsacco 9y ago
    I disagree, I think the peer review functioned exactly as it was supposed to. Her paper doesn't pass the sniff test for me whatsoever when it comes to security analysis. She spent close to no time analyzing the primitives she introduced (and with no proofs or rigor!), meanwhile the thing is 58 pages because she takes the time to explain what "determinism" and "seeds" are to her audience. "Exposition" is, in my opinion, a fully valid reason to reject a paper. I'm not going to sit and read your 60 page paper that could have been compressed to 10 pages if you just got to the point and assumed your audience understood the field well enough to assess your results. Rewrite it and send it back without the assumption that your audience needs to be reminded of everything they'd need to learn just to properly assess your result. It's not as though they rejected the paper on empirical grounds without a meritocratic review; they rejected it because they have a finite amount of time and (speaking as someone in the field) it's sort of annoying to read after page 10. I think academia frequently gets lost in the ivory tower and loses touch with what an accessible paper looks like; this is not an answer to that, it's a swing in the other direction, where papers with truly novel results will suddenly be hundreds of pages and tens of pages of setup.
    - CalChris 9y ago
      If you don't like it then don't read it or don't publish it. But sniff test and exposition are style. Ding it for not analyzing her primitives but don't then call that security analysis. Do the security analysis. In patents there's the concept of enablement: did the inventor enable/teach the idea? Yes she did. Did she flesh out every idea? No she didn't. This was rejected on style grounds. Ignoring it then on 'security analysis' is not improving matters; it certainly isn't helping security. Do the security analysis.
      - 9y ago

lowmagnet 9y ago

I like this because she is a professor at Harvey Mudd. They took steps to make CS more inclusive, with great results. I appreciate her attitude on accessibility, which is in keeping with that institution's philosophy. That she ran into a paper wall doesn't bother her because she's openly publishing is even better.

CalChris 9y ago
I watched her EE380 talk [1] and thought she was a fine professor for a difficult (to me) subject. That she didn't get published for at best stylistic reasons means nothing. [1] https://ee.stanford.edu/event/seminar/ee380-computer-systems-colloquium-family-better-random-number-generators https://ee.stanford.edu/event/seminar/ee380-computer-systems...
dsacco 9y ago
Regardless of her attitude on academic accessibility, it is inappropriate for a paper introducing a novel primitive with proposed security considerations to spend the time explaining why determinism is a concern in functions dealing with randomness. This paper could have been 10 pages. If you want to make your research more accessible, there are ways to do that without assuming that your reader is coming in from a dead start on the field.
- mathperson 9y ago
  I am not sure why you are being downvoted. I think this is clearly true. An easy way to make research accessible is to write a monograph!
thanatropism 9y ago
There's room for accessible and for abstruse literature. Usually what happens with novel work is that initial publications are abstruse but met with excitement by the scholarly community and gradually more accessible works (as the number of collaborators/coauthors grows too) are published. That said, even if multi-culti math means that top-line researchers are going to be spending time with song-and-dance introductions, she should still have put a grad student onto the task of making the short paper that experts will actually read. If the whole thing is a matter of style and not of obfuscation, this would have given a grad student an easy, cool first publication.

deleted 9y ago

[deleted]

mjb 9y ago

> I wonder whether the academic publications are growing ever less relevant to practice. I think there are two topics here. One is whether academic research and work is becoming less relevant to practice. The other is whether the formalism of academic-style publishing are becoming less relevant to the modern world where more and more venues for publishing, rating, and discovering work. On the former, I believe that academic work is as relevant as ever. There are some areas (like systems) where I'm doubtful about relevance from the point of view of a practitioner, but other areas (like hardware and ML where work remains extremely relevant). I haven't noticed a trend there over the last decade, except in some areas of systems where the industrial practice tends to happen on cluster sizes that are often not approachable for academia. On the latter, academic publication does indeed seem to be getting less relevant. There are other (often better) ways to discover work. There are other ways to tell whether a piece of work is relevant, or credible. There are other, definitely better, ways to publish and distribute work. In some sense I think this is a pity: as an academic-turned-practitioner I like academic-style publications. Still, I think they are going to either change substantially or die. This article raises another very good point: sometimes the formalism of academic publication makes the work harder to understand, less approachable, or less valuable. That's clear harm, and it seems like this professor was right to avoid that.

FRIEDCHICKEN 9y ago

I wouldn't trust any PRNG written by a girl.

drallison 9y ago

Melissa O'Neill gave a talk describing the PCG random number generator at Stanford in EE380. https://www.youtube.com/watch?v=45Oet5qjlms https://www.youtube.com/watch?v=45Oet5qjlms

Animats 9y ago

Here's the site for the random number generator.[1] It's basically a simple linear congruential random number generator (well known, but not very good) fed into a mixer. The mixer is new. Most of the analysis is about the LCG or the final output. The suggested mixer is just output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122); That's simple, and the insight in this paper is that something that simple helps a lot. I would have thought that you'd want a mixer where changing one bit of the input changes, on average, half the bits of the output. The mixer above won't do that. DES as a mixer would probably be better, but it's slower. The new result here is that something this simple passes many statistical tests. This isn't crypto-grade; both that mixer and a LCG generator are reversible with enough work. [1] http://www.pcg-random.org/ http://www.pcg-random.org/

tptacek 9y ago
It's a weird paper. It's quite long and takes an eternity to reach this simple point. It's also littered with "security concerns" which are confusing at best and misleading at worst; in reality, none of the generators it discusses are suitable for "sensitive applications", even in the corner-case scenario it discusses of needing permutations of all the b-bit integers, a problem we already have cryptographic tools to solve. But I'll confess to not really understanding what all the fuss is about insecure generators.
- Animats 9y ago
  Linear congruential generators (x = k1*x + k2, unsigned with truncation on overflow) have some strange properties, some of which the paper explores. If you repeatedly take three sequential values from one and treat them as 3D coordinates, the points line up in parallel planes. (There's an explanation of why in Knuth.) Something has to be done to destroy that order. The solution here is to XOR the upper and lower halves of the 128-bit state to get 64 bits, then circular shift that by the high 6 bits of the 128-bit input. This passes most of the classic tests for random number generators. That's the paper, basically.
  - DonbunEf7 9y ago

FabHK 9y ago

A few notes: The author writes "Meanwhile, at least one influential researcher (whose work I respect) had harsh words publicly for her result", and then quotes some of these words: Note that (smartly enough) the PCG author avoids carefully to compare with xorshift128+ or xorshift1024*. However, the author fails to note that said "influential researcher", Sebastiano Vigna, is the author of xorshift128+ and related PRNG. In the linked test [2] by John D. Cook (who uses PactRand, a test similar to the (obsolete) DIEHARD), xorshift128+ and xoroshir0128+ fail within 3 seconds, while PCG ran 16 hours producing 2 TB of pseudo-random numbers without any suspicious p-value detected. On the other hand, Vigna claims that the xoroshiro family does "pass" PactRand. I've submitted an answer to StackOverflow a while ago [1], recommending xoroshiro and PCG, thus I'd be concerned if PCG turns out to be flawed. It's actually quite hard to get academics in the field to give an authoritative recommendation (I've tried) - their response is typically along the line "It's complicated"... [1] https://stackoverflow.com/questions/4720822/best-pseudo-random-number-generator/38202922#38202922 https://stackoverflow.com/questions/4720822/best-pseudo-rand... [2] https://www.johndcook.com/blog/2017/08/14/testing-rngs-with-practrand/ https://www.johndcook.com/blog/2017/08/14/testing-rngs-with-... Edit: remove italics due to asterisk in PRNG name, & add link to John. D Cook's test.

MiceWithYaffle 9y ago
I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) O'Neill has instructions on how to test with PractRand and with TestU01 on her blog (http://www.pcg-random.org/blog/ http://www.pcg-random.org/blog/). I had a go with TestU01 on Vigna's generators, and when you test the low 32 bits reversed (for 64-bit PRNGs, you have to test the high 32, the low 32, both forwards and reversed), I found that all Vigna's generators fail. Given the PractRand results it makes sense, I guess, but I had read that Vigna's generators were supposed to pass TestU01. Does anyone else wants to have a go at testing so I can know if I screwed up somehow?
- rockdoe 9y ago
  I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) The code does explain exactly what the issue is, i.e. that the last bit isn't random: This generator passes the PractRand test suite up to (and included) 16TB, with the exception of binary rank tests, which fail due to the lowest bit being an LFSR; all other bits pass all tests. We suggest to use a sign test to extract a random Boolean value. But I'm tempted to agree this isn't a desirable property for a generic RNG. How many users of JavaScript know about this property? (it's the default RNG for most browser engines) Or does it not matter because they return 53-bit floats?

the_stc 9y ago

As a general comment, I dislike deliberately obtuse writing in papers. In my current work, I came across a very in-depth survey of our industry (sex work). Excellent study, very helpful. But some of the sentences seemed to over-complicate the math. Example: "Consider the set P {p1, p2, ... pN} representing providers and the set C {c1, c2, ... cN} representing customers". I am pretty sure this kind of stuff is filler or pretends to make things look more rigorous than they are. On the other hand, maybe spending more than a line explaining what the birthday paradox is should be cut out and put in a backgrounder paper or appendix so that the paper can focus on the actual novel ideas.

dsacco 9y ago
> On the other hand, maybe spending more than a line explaining what the birthday paradox is should be cut out and put in a backgrounder paper or appendix so that the paper can focus on the actual novel ideas. That was my annoyance with the paper as well. Add to that explanations that amount to, "What even is determinism?" or "What's a seed?" and I'm unsurprised it's nearly 60 pages.
mathperson 9y ago
are you joking? That is your example of abstruse mathematical notation? Some variables with names?!
- the_stc 9y ago
  No. I am saying that giving the definition of a set each time is just extra verbosity. The whole paper had that extra verbiage, everywhere. Kind of why-use-one-word-when-ten-will-do feeling.
  - mathperson 9y ago
    Could you share the paper? I mean if they were making a mathematical argument...it is kind of hard to do that without defining things..
    - 9y ago

bmm6o 9y ago

It sounds like an interesting result, I look forward to reading the paper more carefully. That said, it's clearly not written for an academic journal. Section 2.4.3 is entitled "The Importance of Code Size", and explains why shorter code is better. I think you can argue that some academic papers are excessively concise, but this is a 58-page paper about an RNG. It is clearly not a journal paper and has a ton of extraneous content. I have to sympathize with the commenter that the author has made a trade-off and written a paper that's less rigorous than it should be (for peer review). I wonder why she didn't write 2 versions.

wadkar 9y ago
> I wonder why she didn't write [two] versions. Because the reviewers took over 10 months to respond with a rejection mainly citing the length of the paper. And more importantly, "By that point, everyone who might have wanted to read it had almost certainly found it here and done so, so I saw little merit in drastically shortening the paper."[1] She has updated the blog post which discusses all the nuanced details of the whole affair last month (2017-07-25)[2]. [1] http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html [2] http://www.pcg-random.org/posts/history-of-the-pcg-paper.html http://www.pcg-random.org/posts/history-of-the-pcg-paper.htm...
- bmm6o 9y ago
  There is no excuse for the journal to take so long to provide a response. At the same time, it seems to me that their response was entirely predictable. Or does the journal usually post such long articles directed at a general audience?

dsacco 9y ago

I have a few comments: 1. The paper itself[1] is extremely readable by the standards of most cryptography research. On one hand, this is great because I was able to follow the whole thing in essentially one pass. On the other hand, the paper is very long for its result (58 pages!), and it could easily do without passages like this one: Yet because the algorithms that we are concerned with are deterministic, their behavior is governed by their inputs, thus they will produce the same stream of “random” numbers from the same initial conditions—we might therefore say that they are only random to an observer unaware of those initial conditions or unaware of how the algorithm has iterated its state since that point. This deterministic behavior is valuable in a number of fields, as it makes experiments reproducible. As a result, the parameters that set the initial state of the generator are usually known as the seed. If we want reproducible results we should pick an arbitrary seed and remember it to reproduce the same random sequence later, whereas if we want results that cannot be easily reproduced, we should select the seed in some inscrutable (and, ideally, nondeterministic) way, and keep it secret. Knowing the seed, we can predict the output, but for many generators even without the seed it is possible to infer the current state of the generator from its output. This property is trivially true for any generator where its output is its entire internal state—a strategy used by a number of simple random number generators. For some other generators, such as the Mersenne Twister [35], we have to go to a little more trouble and invert its tempering function (which is a bijection; see Section 5), but nevertheless after only 624 outputs, we will have captured its entire internal state. That's a lot of setup for what is frankly a very basic idea. A cryptographer being verbose in their writing might briefly remind the reader of these properties with the first sentence, but they'd still likely do that with much more brevity than this. I understand wanting to make your research accessible, but for people who understand the field this detracts from getting to the "meat." It might make it harder to get through, but a 10-30 page result is preferable to a nearly 60-page one that assumes I know nearly nothing about the field. If I don't know these details very well, how can I properly assess the author's results? 2. The author's tone in her writing is something I take issue with. For example, passages like this one... Suppose that, excited by the idea of permutation functions, you decide to always improve the random number generators you use with a multiplicative step. You turn to L’Ecuyer’s excellent paper [25], and without reading it closely (who has time to read papers these days!), you grab the last 32-bit constant he lists, 204209821. You are then surprised to discover that your “improvement” makes things worse! The problem is that you were using XorShift 32/32, a generator that already includes multiplication by 747796405 as an improving step. Unfortunately, 204209821 is the multiplicative inverse of 747796405 (mod 2 32), so you have just turned it back into the far-worse–performing XorShift generator! Oops.* ...go a bit beyond levity. If you're trying to establish rigorous definitions and use cases to distinguish between generators, functions and permutations, this isn't the way to do it. This isn't appropriate because it doesn't go far enough to formalize the point. It makes it intuitive, sure, and that's a great educational tool! But it's a poor scenario to use as the basis for a problem statement - research is not motivated by the failure of an engineer to properly read and understand existing primitives, it's motivated by novel results that exhibit superior qualities over existing primitives. 3. The biggest grievance I have with this paper is the way in which it analyzes its primitives for cryptographic security. For example, this passage under 6.2.2 Security Considerations: In addition, most of the PCG variations presented in the next section have an output function that returns only half as many bits as there are in the generator state. But the mere use of a 2 b/2-to -1 function does not guarantee that an adversary cannot reconstruct generator state from the output. For example, Frieze et al. [12] showed that if we simply drop the low-order bits, it is possible for an adversary to discover what they are. Our output functions are much more complex than mere bit dropping, however, with each adding at least some element of additional challenge. In addition, one of the generators, PCG-XSL-RR (described in Section 6.3.3), is explicitly designed to make any attempt at state reconstruction especially difficult, using xor folding to minimize the amount of information about internal state that leaks out.17 It should be used when a fast general-purpose generator is needed but enhanced security would also be desirable. It is also the default generator for 64-bit output. That's not a rigorous analysis of a primitive's security. It is an informal explanation of why the primitive may be secure, but it so high level that there is no proof based on a significant hardness assumption. Compare this with Dan Boneh's recent paper, "Constrained Keys for Invertible Pseudorandom Functions"[2]. Appendices A and B after the list of references occupy nearly 20 pages of theorems used to analyze and prove the security of primitives explored in the paper under various assumptions. Novel research exploring functions with (pseudo)random properties is inherently mathematical; it's absolutely insufficient to use a bunch of statistical tests, then informally assess the security of a primitive based on the abbreviated references to one or two papers. _________ 1. http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf 2. https://eprint.iacr.org/2017/477.pdf https://eprint.iacr.org/2017/477.pdf

fwdpropaganda 9y ago

Physicist here. Off-topic > And it is not even entirely clear what “really random” would mean. It is not clear that we live in a randomized universe… At the quantum level it really is clear that we live in a really random universe. What's the meaning of really random? The outcome of a quantum process. On-topic. Yeah, you have to know your audience. As OP mentions, just because the paper wasn't published doesn't prevent anyone from thinking about it and even building on it. On the other hand these scientific publications have styles and target audiences, and maybe she got rejected not due to lack of relevance or rigor, but because the paper didn't match the publication's non-scientific criteria for publication.

eridius 9y ago
A quantum process is a random process, but isn't it still an open philosophical question as to whether the "random process" we observe is truly random, or is instead governed by deterministic hidden state?
- fwdpropaganda 9y ago
  No, all theories of (local) hidden variables have been experimentally ruled out. https://en.wikipedia.org/wiki/Bell%27s_theorem https://en.wikipedia.org/wiki/Bell%27s_theorem > Bell's theorem states that any physical theory that incorporates local realism cannot reproduce all the predictions of quantum mechanical theory. Because numerous experiments agree with the predictions of quantum mechanical theory, and show differences between correlations that could not be explained by local hidden variables, the experimental results have been taken by many as refuting the concept of local realism as an explanation of the physical phenomena under test. For a hidden variable theory, if Bell's conditions are correct, the results that agree with quantum mechanical theory appear to indicate superluminal effects, in contradiction to the principle of locality.
  - eridius 9y ago
    Interesting. But it sounds like non-local hidden variables are still possible. My assumption is that non-local hidden variables is non-falsifiable, which is why I said this was a philosophical question.

sulizilxia 9y ago

I love O'Neill's work on PCG, and loved the talks by her I watched online. As a tenured professor I want to say two things about this piece: 1. I think academic publishing will be forced to change. I'm not sure what it's going to look like in the end, but traditional journals are starting to seem really quaint and outdated now. 2. As far as I can tell from what she's written on the PCG page, the submission to TOMS is a poor example, because no one I know expects to be done with one submission. That is, no one I know submits a paper to one journal, even one reputable journal, and is done. They submit and it gets rejected and revise it and resubmit it, maybe three or even four times. After the fourth or fifth time, you might give up, but not necessarily even then. I have mixed feelings about the PCG paper as an example, because in some ways it's great: an example of how something very influential has superceded traditional academic publishing. In other ways, though, it's horrible, because it's misleading about the typical academic publishing experience. Yes, academic publishing is full of random nonsense, and corruption, but yes, you can also get past it (usually) with just a little persistence. In still other ways, it's a good example of what we might see increasingly, which is a researcher having a lower threshold for the typical bullshit out there.

Houshalter 9y ago

I once tried to develop my own fast random number generate using nothing but bitwise operations. On the theory they were the fastest/simplest. I had a program generate thousands of random combinations of bitwise functions. And then used statistical tests to see which ones produced the most "random" seeming behavior. It worked as far as I can tell. But I don't trust the statistical tests. Who is to say there isn't a very obvious pattern in the numbers that I didn't test for or notice? How do you prove a random number generator is good?

thaumasiotes 9y ago
> How do you prove a random number generator is good? You can't; that's the nature of randomness. You can prove they're bad, though.
carapace 9y ago
> How do you prove a random number generator is good? Compress its output.
cgmg 9y ago
A theoretical approach based on computability theory is https://en.m.wikipedia.org/wiki/Algorithmically_random_sequence https://en.m.wikipedia.org/wiki/Algorithmically_random_seque....

starmole 9y ago

As an engineer who switched to PCG: - PCG is not crypto, everybody should understand that. It's for simulation and rendering. - PCG mainly replaces Mersenne Twister which is in c++11. The Twister has a LOT more state and is a LOT slower for less randomness. - In rendering and simulation speed really matters, and PCG excels there. - Xorshift is another algorithm in the same class. I would really like to see an objective comparison. In my cursory engineering look PCG seemed better. - Fast PRNG is almost a new field again: It's not crypto, but immensely useful. How did the Twister get into C++11 while it is so much worse than PCG or Xorshift? Nobody cared! - Maybe PCG should have been a paper at SigGraph. - For the style of the paper, I think one contribution is rethinking PRNG outside crypto. That deserves and requires a lot of exposition.

MiceWithYaffle 9y ago
Yeah, it's not for crypto. But I think it's for more than simulation and rendering. It's meant as a general purpose PRNG. It's just as good for randomized algorithms like picking the pivot in quicksort, or playing games, procedural content generation (PCG!), or whatever you want to use it for. I think that the whole point of the prediction difficulty stuff is that a library (e.g., C++11's) with general purpose PRNGs can't know how they'll be used. Maybe some idiot write code for a gambling machine in C++ and use whatever PRNG is to hand. There was a story in the news the other week about people going around casinos predicting slot machines, so maybe this has already happened! PCG is trying to make your simulation and rendering code fast while trying to offer at least some defense against egregious misuse. Basically PCG is trying to be a good all rounder. As you say, it's meant as a replacement for the Mersenne Twister.
- starmole 9y ago
  I found the story: https://www.wired.com/2017/02/russians-engineer-brilliant-slot-machine-cheat-casinos-no-fix/ https://www.wired.com/2017/02/russians-engineer-brilliant-sl... And yes, PCG is harder to exploit in this way than the Twister, but you still really should not bet money on it!