3

I am trying to understand the actual implications for the following statement regarding a 16-bit random number generator for the tag from the EPC Generation 2, UHF RFID specification, section 6.3.2.7. that states:

Probability of a single RN16: The probability that any RN16 drawn from the RNG has value RN16 = j, for any j, shall be bounded by $$0.8/2^{16} < P(RN16 = j) < 1.25/2^{16}$$

I realized this morning that I actually have no idea what that statement really means, but it seems one can have less than random, random number generator.

I made a 16-bit random number generator on silicon that passed statistical tests; however, looking back at the specification, it seems that I probably could have saved some power and cut some corners, but I honestly don't know how I would have turned those parameters into an engineering decision.

This gets me to the question: How does the above equation affect an allowable decrease in randomness from a truly random number generator?

edit: That statement is just so weird. If I counted up from 0 to 65535 and wrapped around to 0 again, I'd satisfy that condition, and that's not random at all.

kelalaka
  • 1,637
b degnan
  • 225
  • Not sure what you are asking. Of course any real world random number generator is likely to be prone to (hopefully small) biases. As to how those biases play out, well you can test them. Run simulations. Certainly, if you are building a simulator for some difficult computation, you will want to run a large suite of controls through it to detect failures of randomness (among other things). – lulu Apr 21 '22 at 12:45
  • Define RN16 mathematically – kodlu Apr 21 '22 at 12:56
  • Wrt your edit - obviously that is not the only criterion for randomness. It is a necessary condition, not a sufficient one. All it says really is that for any value, if it occurs slightly more or less often than expected, then it should not be too biased. They are not allowed to occur in a ratio of 5:4 or worse from the average. – Jaap Scherphuis Apr 21 '22 at 12:58
  • 1
    It's notoriously hard to write down a good short practical definition of randomness that disallows things like your scheme. Someone might object that "with probability one, the first output of your RNG is 0" but a similar objection applies to any deterministic prng. Answers here discuss the problem, you might find them and their links useful. – Matthew Towers Apr 21 '22 at 12:58
  • @kodlu It's just a 16-bit register. Thanks for the answer and references. – b degnan Apr 21 '22 at 13:35
  • 1
    Thank you to everyone who responded. I think that I can act upon the information that I have. Cheers. – b degnan Apr 21 '22 at 13:41

1 Answers1

4

All the comments are spot on. The statement is simply about the "probability" of each 16 bit output, say $X$, from the RNG. Something of the form $$ (1-\epsilon)2^{-16} \leq \Pr(X=x) \leq (1+\epsilon)2^{-16}, \quad \forall x \in \{0,1\}^{16}. $$ This can only be tested empirically but tests do not prove randomness, they can indicate nonrandomness due to failure of outputs.

In crypto literature and standards there are other tests, which attempt to evaluate aspects of randomness such as independence of consecutive (or non consecutive) samples such as "Runs Test", "overlapping Windows test", "non overlapping Windows test".

So this test you mention simply corresponds to what's called "frequency test" in cryptographic literature. The weakest, the simplest, but if it fails then one can strongly suspect something is wrong with the generator.

There is also whole field of computer science and mathematics focused on defining and measuring randomness. Martin-Lof and Kolmogorov have worked (among many others) in this area,

There is no way this test can prove any substantial randomness property.

kelalaka
  • 1,637
kodlu
  • 9,338