Random number generation: It might be harder than you think to write code that rivals novice-level code written in Python.

I have to say I'm not really impressed with PCG. It's not that it's bad, even, it's that it greatly overstates what it actually is: an LCG with an output filter. This is basically an exercise in diffusion without any of the standard terminology.

The idea of outputting only part of the state is far from new. In fact, any cryptographer will immediately recognize the idea and constructions using it (e.g., sponges), since it is pervasive. Sharing the diffusion workload between the permutation and the output function is also not a new idea, see for example this paper. The reason typical non-cryptographic generators use up the entire state for output is because not doing so decreases performance without too much of a statistical quality benefit, and security is not a concern.

Regarding PCG itself, it appears that none of the versions (unless we count the tiny ones) is actually fast without a strong 64-bit multiplier. This is obviously bad on the now ubiquitous ARM chips present in nearly every phone, which will require 4 multiplication instructions (high and low) to advance the LCG. Additionally, variable-length rotations tend to be nonexistent in vector instruction sets, along with 64-bit multiplication; this means that {SSE2, NEON, etc}-vectorized implementations of PCG, outputting up to 4 words at a time, will not be easily done.

Regarding the website, the table in the introductory page is highly misleading and in some cases wrong:

  • Chacha20 does not require a 2KB state; its internal state is in fact 64 bytes. Likewise, Chacha20's statistical quality is not 'unclear': Chacha20 has been analyzed quite thoroughly by many cryptographers, and the best statistical biases that could be detected only went as far as 4 (out of 20) rounds, using fairly advanced methods. Also, since Chacha20 is a stream cipher using a PRF in counter mode, it is trivial to determine both its period (270 bytes) and how to jump head (simply increase the counter). Chacha20 is also not slow; its peak performance is on the order of 1 cycle per byte on the paper's Haswell processor, or 4 cycles per 32-bit word. This makes it rather comparable in performance with the small-state PCG instances, at least. "Not always reproducible" results? I don't know what this means, the algorithm is deterministic.

  • Prediction difficulty being "challenging" is basically a non-claim. I would put no faith in the security of PCG, especially under any reasonable attack model for secure pseudorandom generators, without any serious analysis performed on it. The security claims are extremely vague, but at the same time sold as a competitive advantage over other generators. This just seems dishonest: if there's a security claim, quantify it.

  • Labeling MT19937's performance as "acceptable", while PCG is "very fast" is again misleading. The paper's benchmarks put them very close together, and I would venture that in 32-bit architectures MT19937 actually takes the lead. There is also no mention of the smaller MT instances, namely MT607, SFMT, MTGP (SIMD-friendly!), and TinyMT.

  • Arc4random is complex? return i += 1, j += S[i], swap(S[i], S[j]), S[(S[i] + S[j])&255]; looks pretty simple to me.

If anything, I would recommend Chacha20 to be standardized as a default URNG for the C++ standard.

/r/cpp Thread Parent