Mathematical definition of deterministic and non-deterministic random bit generators

Question

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

Providing a reference will also be very helpful.

Answer 1

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".

Answer 2

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.