0
$\begingroup$

My question is probably both philosophical and technical.

Background

I was developing a CSPRNG, and I needed to shuffle the bits in one step in the middle of the algorithm - any naive shuffle would suffice.

I had this question in my mind:

Why would be any difference if one chooses to confine to a "shuffle" algorithm (see next) instead of my whole complicated algorithm? Which terrified me, to be honest.


The Naive Method

I created a pool of $10^6$ bits where the 1's count exactly 50% and distributed consecutively.

$1111......0000$

Then used the very simple Fisher–Yates shuffle Algorithm to shuffle the bits.


Results

Trying different seeds and sequence lengths, the above-mentioned naive method passed ALL NIST and DieHarder Tests, in addition to the Next Bit Test. It was even superior to the results of urandom and Mersenne Twister (I know that the latter is not CSPRNG but it's widely used as PRNG).


The Question

I believe that if anyone proposes the above naive shuffle algorithm even if supported by its excellent results in the literature, it will be immediately rejected (though I'm open to correction here).

Then the question that is confusing me is : Why? I mean "Why" on both ways:

Why such naive and simple thing is not appealing and Why would such naive and simple method pass all tests and even surpass urandom and MT algorithm on the basis of the aforementioned tests (which are extremely used as an evidence of the proposed algorithms in the literature).

What is the "real" compass?

$\endgroup$
4
$\begingroup$

Why such naive and simple thing is not appealing

If you're talking about a method that internally generates 500,000 0 bits and 500,000 1 bits, shuffles them (by some method), and then outputs them, that would not be considered a CSRNG.

What is the "real" compass?

The compass is "can we devise an efficient test that distinguishes the output of the proposed CSRNG from the output of a truly random number generator (e.g. generated by someone flipping a fair coin)". This test would take a sequence (generated by either the CSRNG or the random source) and generate a 0 or 1 answer; it is considered a distinguisher if it generates a 1 answer with a nontrivially different probability when given a sample from the CSRNG versus a sample from the random source.

In the shuffle-rng case, yes; one can ask for the output of 1,000,000 bits and count the '1' bits. For the shuffle rng, you're get exactly 500,000 '1' bits; for the truly random source, you're get exactly 500,000 '1' bits rather rarely (with probability $c 10^{-3}$ for some $c$ not too far from 1 that I'm too lazy to look up). That gives us a distinguisher, and hence the shuffle RNG is not a CSRNG.

In addition, you state:

the aforementioned tests [NIST, Dieharder, Next Bit Test] (which are extremely used as an evidence of the proposed algorithms in the literature).

Actually, when it comes to CSRNGs, those tests will rarely be used as evidence (and, quite frankly, when we come across a proposal which states them as evidence, that'll be taken as evidence that the authors are clueless when it comes to cryptography). It's quite easy to make a generator that passes all those tests, but for which it is easy to make a distinguisher (and hence is not a CSRNG).

Those tests might be sufficient if you want to make sure that the RNG you're considering has good statistical properties, and so might be reasonable for noncryptographical work; however in crypto, we have considerably stricter requirements.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer and +1. Can I summarize this by saying: the plot is the distinguisher? Also, in the literature it is mandatory to have exactly 50% of any pattern, however, the TRNGs are always biased (as you said) and indeed they are in all of my prolonged simulations, so how come TRNGs are CSPRNG although they don't fulfill the 50% requirement ? $\endgroup$ – Mike Sep 12 at 12:37
  • $\begingroup$ The whole answer is great, and the bustlast paragraph pure wisdom. $\endgroup$ – fgrieu Sep 12 at 12:39
  • 2
    $\begingroup$ @Mike: "in the literature it is mandatory to have exactly 50% of any pattern"; where in the "literature" do you see that? Real random sources don't meet that requirement, and that's what a CSRNG is trying to mimic. $\endgroup$ – poncho Sep 12 at 12:41
  • $\begingroup$ The Next Bit Test itself in the reference above requires no pattern is more than its conjugate (e.g. 001 and 000), in any subsequence, is greater than a threshold (the threshold is 50% for all sequences greater than 20000 bits). You know that the next bit test is the first mandatory requirement for CSRNG. $\endgroup$ – Mike Sep 12 at 12:45
  • 1
    $\begingroup$ @Mike, the statements of the type that occur in the next bit test are asymptotic in nature. They typically say that there is no fixed constant $\epsilon>0,$ such that the ratio of 1's to 0's is outside $(1/2-\epsilon,1\2+\epsilon).$ So in particular the imbalance can be as large as (say) $n/\log n$ and still satisfy this requirement. And the probability of having exactly the same number of 1's and 0's goes to zero for an ideal uniform i.i.d. bit source $\endgroup$ – kodlu Sep 13 at 1:32

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.