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

  • $\begingroup$ 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. $\endgroup$ – Radium Feb 21 '20 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$).


¹: 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.


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.