Live data from Hacker News

On Melissa O’Neill’s PCG random number generator

lemire.me

31–40 of 90 posts

Re: On Melissa O’Neill’s PCG random number generator

#31
post #21

Earlier quoted context omitted.

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.

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 opinio…

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.

Re: On Melissa O’Neill’s PCG random number generator

#32
post #21

Earlier quoted context omitted.

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 opinio…

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 'securi…

> Sniff test and exposition are style.

Peer review journals and conferences have (typically explicit) style guides. The argument that peer review arbitrarily rejects papers unsubstantively is a strawman; peer review councils do not maintain that meritocratic results-driven analysis are the only barriers to entry.

>Ding it for not analyzing her primitives but don't then call that security analysis. Do the security analysis.

Authors introducing novel results with cryptographic considerations typically perform their own analysis and publish that in the paper with the result. I was not referring to my observation of her own insufficient analysis as if it is a formal analysis on my part, I was observing (correctly) that she didn't do enough of her own formal analysis. There is a modicum of author-provided proof-based assurance that 1) is considered in the peer review process and 2) forms the foundation for formal cryptanalysis by peers in the community. In other words, there isn't yet enough for cryptanalysts to attack (or more precisely, the author has put the onus of analysis on other researchers, instead of providing specific, rigorous claims which they can empirically refute).

It comes down to respecting time. In attempting to be accessible, the author is not being respectful of other researchers' time. We don't need to have the birthday paradox explained to us, we've understood that since Intro to Statistics. The paper is 58 pages because, "think of the unwashed masses who can't understand our work!", but in attempting to appeal to those beyond the ivory tower, it's just become circuitous and over-indulgent. She didn't have to write in this style to make it more accessible (and the relevant mathematics has a lower bound on how accessible it can be, anyway).

It is not respectful of qualified cryptanalysts to not even provide a precise set of proofs for your claims. She uses phrases like, "PCG is a middle ground between security and performance." We cannot analyze that, and it's not for cryptanalysts to review every single claim that comes across their desks. This is why the author of xorshift+ didn't even provide a cryptanalysis in his scathing review.

If you're not going to sufficiently specify your claims, don't be surprised when the academic community ignores them (even if they're valid!). You are arguing your point from a first principles approach to meritocracy and the fairness of style-based assessment; I am arguing that as a practical matter in the research community, there is a reason this is not how novel cryptographic primitives are introduced.

Re: On Melissa O’Neill’s PCG random number generator

#33
post #15
post #14

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 help…

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…

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.

Re: On Melissa O’Neill’s PCG random number generator

#34
post #21

Earlier quoted context omitted.

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.

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 opinio…

It's not a security paper. Or at least, I think it isn't? It's not clear to me what journal it was submitted to.

Re: On Melissa O’Neill’s PCG random number generator

#35
post #20

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 beh…

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

Re: On Melissa O’Neill’s PCG random number generator

#36

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.

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.

Re: On Melissa O’Neill’s PCG random number generator

#37
post #35
post #20

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 beh…

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

She submitted it to ACM Transactions on Mathematical Software. I would personally consider it a cryptography paper, for three reasons:

1. She purports to introduce a novel result that bridges "medium-grade" performance characteristics and security characteristics in one primitive. In fact, if you look at the PCG Random website (pcg-random.org), she very clearly compares and emphasizes both performance and security characteristics with functions like xorshift and ChaCha.

2. We see cryptography papers submitted to all manner of theoretical CS conferences and journals, for example Symposium on the Theory of Computing, which are not uniformly crypto-focused.

3. She acknowledges herself that she found it hard to categorize her paper (it could be relevant for simulstion, it could be relevant for stream ciphers, etc) in a blog post about how she chose the venue: http://www.pcg-random.org/posts/history-of-the-pcg-paper.htm...

As a meta point I read the whole thing, and I actually think it would be a nice publishable result if it were, say 10 - 20 pages. But 60 is wild! It took me longer to get through this "accessible" paper than it did for me to get through any of Boneh's papers on constrained and puncturable pseudorandom functions!

It's definitely interesting, and sure, why not explore "medium-grade security" that makes explicit tradeoffs with performance and security. But the presentation seems like it was written by someone writing for a non-academic audience, and the content of 6.2.2 "Security Considerations" is really light on provable security.

Re: On Melissa O’Neill’s PCG random number generator

#38
post #24
post #6

Earlier quoted context omitted.

You don't think the peer review process ever produces false negatives?

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.

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.

Re: On Melissa O’Neill’s PCG random number generator

#39
post #35
post #20

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 beh…

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

ACM Transactions on Mathematical Software.

Re: On Melissa O’Neill’s PCG random number generator

#40
post #35
post #20

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 beh…

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

[deleted]
Post reply on HN