4
$\begingroup$

Seedless Fruit is the Sweetest: Random Number Generation, Revisited introduces a theoretical framework for "seedless" RNGs.

AFAICT, this framework injects entropy directly into the underlying cryptographic primitive instead of treating the entropy collection/estimation and randomness extraction as two separate phases. Is my understanding correct?

What quantitative benefits does this framework have over the more traditional seed-based design?

$\endgroup$
8
  • 1
    $\begingroup$ Only read the abstract: It's [snip]. Please read about the concept of seedless RNGs here. $\endgroup$ – Paul Uszak Apr 16 at 3:33
  • 2
    $\begingroup$ Without reading the abstract in its entirety, "seedless" is an obvious violation of Kerckhoffs's principle for PRNGs. $\endgroup$ – DannyNiu Apr 16 at 4:50
  • 3
    $\begingroup$ @DannyNiu as far as I can tell you're misunderstanding the meaning of seedless. Their claim is that they can (under supposedly reasonable assumptions) extract almost uniform randomness from high entropy sources without requiring an initial uniformly and independently distributed seed. $\endgroup$ – Maeher Apr 16 at 9:57
  • 2
    $\begingroup$ @MaartenBodewes That's not really this paper's fault. The theoretical CS, (and specifically randomness extraction) literature has used "seed" to mean "short uniformly random string" for decades. It's simply a case of the same term being used to mean different things in different communities. $\endgroup$ – Maeher Apr 16 at 13:42
  • 4
    $\begingroup$ Seeded randomness extractors are a well known concept; I presume the authors assumed that their usual readers would guess by default that "seedless PRG" does not refer to "PRGs without seed" in the usual sense, since it trivially does not exist. It's true that the two meanings of "seed" might be slightly annoying for readers outside of the area, though. $\endgroup$ – Geoffroy Couteau Apr 16 at 13:46
3
$\begingroup$

AFAICT, this framework injects entropy directly into the underlying cryptographic primitive instead of treating the entropy collection/estimation and randomness extraction as two separate phases. Is my understanding correct?

Yes, that's my understanding as well.

What quantitative benefits does this framework have over the more traditional seed-based design?

The benefit is that if the entropy source is under partial control of an attacker it will still be possible to create a secure random number generator, assuming that enough entropy is left of course. If you assume that the entropy pool is not under control and delivers enough entropy to a traditional PRNG using the seed(s) then the benefits seem non-existent. Here's where I struggle a bit, because "partial control" seems to be tricky to accomplish.

In the traditional approach you could argue that the PRNG requires another PRNG-like construction (such as a KDF or, in the case of Intel, a PRF/MAC) to create the short, universally random bit string to be used as the seed.

$\endgroup$
1
$\begingroup$

The paper's use of "seedless" is very confusing as they aren't getting rid of internal state ... which is a seed, just a slightly different one. At 85 pages, the paper is also just very long. The problem I see the paper appears to address (after skimming through the text for a while), include:

  1. the chicken and egg situation with seed and randomness in PRNGs,

  2. a security model for PRNGs in such situation,

  3. instantiation constructions for such PRNGs using SHA-2 and SHA-3 and related cryptographic primitives.

In reality however, PRNG algorithms must still be defined in terms of entropy input (i.e. random internal state) and randomness output, so the paper doesn't affect existing practice too much.

$\endgroup$
8
  • 1
    $\begingroup$ "It may be better to separate it into multiple papers focusing on different aspects of the problem the authors are trying to address, instead of writing such a monolithic ramble." I don't understand this sentence. Is this saying that the paper is too big and should have been broken into several sub-papers? If yes, I disagree with the general concept of trying to break papers into smaller papers rather than having (possibly dense) coherent wholes. "Making 10 papers out of 1" is a plague of the academic publication pressure, and it's rather desirable that people avoid it as much as possible. $\endgroup$ – Geoffroy Couteau Apr 16 at 13:40
  • $\begingroup$ Yes I do mean it should be broken into parts. And if it's academically unorthodox (I'm by no mean an academic person myself), then I think the paper could certainly use better sectioning. $\endgroup$ – DannyNiu Apr 16 at 15:27
  • 1
    $\begingroup$ I've never claimed (or thought) that a good paper has to be long. And how about a third option: it's a perfectly fine paper that academic researchers which are experts in theoretical cryptography have no problem understanding, but that nonetheless might not fall into your area of expertise? To believe that a paper of Dodis & Tessaro (two major cryptographers), published at Crypto'19 (the best conference) can be "rambling nonsense" requires a fair amount of this kind of confidence that ignorance can provide. Something you don't understand need not be 'on another plane' or 'rambling nonsense'. $\endgroup$ – Geoffroy Couteau Apr 16 at 17:33
  • 2
    $\begingroup$ @GeoffroyCouteau As a nerd, I can't rule out that I'm totally wrong. I probably am. But the paper (to my uneducated eye) seems like a long literature review of common constructs. We have hashed un-seeded entropy pools for thousands of years as /dev/random. And I know a little about entropy extraction. This paper doesn't seem to present anything new. I say again: What exactly is in §1.4 (Our results)? But it could just be above me :-) $\endgroup$ – Paul Uszak Apr 16 at 19:05
  • 2
    $\begingroup$ This is a much more reasonable comment that I can perfectly hear and that a real expert on this topic (meaning, not me) could perhaps answer :) If I get time, I'll have a look to see if I can help with getting some intuition about what an answer could be. $\endgroup$ – Geoffroy Couteau Apr 16 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.