# On the Acceptability of a Naive Pseudo Random Number Generator

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?

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.

• @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 – kodlu Sep 13 at 1:32