# Mathematical definition of deterministic and non-deterministic random bit generators

Can anyone give the mathematical definition of deterministic and non-deterministic random bit generator?

Providing a reference will also be very helpful.

Deterministic random bit generator is a function that takes as input a secret seed and possibly other inputs and produces (long) strings of output bits with the following property: for all adversaries with (polynomially) bounded computational power, the distribution of output bits is indistinguishable from a uniform, independent distribution of bits.

I don't think there is a strictly "mathematical" definition of true random bit source (I guess this is what you mean by 'non-deterministic') since it would need to define something that is now well captured by mathematics (external, physical source of entropy).

NIST in its standard SP800-90Ar1 defines non-deterministic random bit generator as:

An RBG that always has access to an entropy source and (when working properly) produces output bitstrings that have full entropy. Often called a True Random Number (or Bit) Generator. (Contrast with a deterministic random bit generator).

A good reference book that covers the topic of randomness and random bit generators is "Random Number Generators - Principles and Practices".

• Actually I was looking for mathematical definition! I have seen the SP 800-90a, not that much helpful, but the later reference is helpful; thank you sir. – Radium Feb 21 at 11:18

A deterministic random bit generator is, per standard terminology, a pseudo-random generator. That is defined¹ to be a deterministic polynomial-time algorithm $$G$$ with associated polynomial $$l$$ (it's length expansion factor), implementing a function $$G:\{0,1\}^*\to\{0,1\}^*$$ such that

• For all input $$s$$ it holds $$\mathbin\|G(s)\mathbin\|=l(\mathbin\|s\mathbin\|)>\mathbin\|s\mathbin\|$$
In other words, if the input bitstring² is $$n$$-bit, the output is $$l(n)$$-bit and longer than the input.
• For any polynomial-time algorithm $$D$$, there exists a negligible² function $$\operatorname{negl}$$ such that for any integer $$n$$ $$\Bigl|\Pr\bigl[D\bigl(G(s)\bigr)=1\bigr]-\Pr\bigl[D(r)=1\bigr]\Bigr|\le \operatorname{negl}(n)$$ where $$s$$ is a uniformly random⁴ $$n$$-bit string and $$r$$ is a uniformly random⁴ $$l(n)$$-bit bitstring.
In other words, no probabilistic polynomial-time algorithm can distinguish the output of $$G$$ from random with non-negligible probability.

A non-deterministic random bit generator can be mathematically defined⁴ as a pseudo-random generator with input designated random, just like the random input of a probabilistic algorithm. When computing probabilities all values of $$s$$ are considered.

For simplicity, the input can be replaced by its bit length $$n$$ (input $$s$$ becomes implicitly uniformly random of length $$n$$).

Alternatively, the input can be the desired output length $$m$$ ($$s$$ becomes implicitly uniformly random of length the lowest $$n$$ such that $$l(n)\ge m$$).

Notes:

¹: This definition is equivalent to and adapted from that in Jonathan Katz and Yehuda Lindell's Introduction to modern cryptography.

²: The set of bitstrings of arbitrary finite length is noted $$\{0,1\}^*$$

³: A negligible function is an $$f:\Bbb N\mapsto\Bbb R^+$$ such that for all $$k\in\Bbb N$$ it holds $$\displaystyle\lim_{n\to\infty}f(n)\,n^k=0$$

⁴: If algorithm $$D$$ is probabilistic, the probabilities are computed over all random inputs for $$D$$ in addition to all $$s$$ or $$r$$.

⁵: This definition is non-standard, and out of my head.