# 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. Feb 21, 2020 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.87860394,"math_prob":0.9992534,"size":3162,"snap":"2023-14-2023-23","text_gpt3_token_len":692,"char_repetition_ratio":0.14407854,"word_repetition_ratio":0.08225108,"special_character_ratio":0.20746364,"punctuation_ratio":0.09255898,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999585,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-03-20T12:07:04Z\",\"WARC-Record-ID\":\"<urn:uuid:2b1efe43-7fd8-4085-bd7f-11a7df16d492>\",\"Content-Length\":\"165625\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fae65ee8-bcad-41f6-945c-baa66c83cd1a>\",\"WARC-Concurrent-To\":\"<urn:uuid:c75923c0-6937-47f7-8443-f49cf1be06df>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/77739/mathematical-definition-of-deterministic-and-non-deterministic-random-bit-genera\",\"WARC-Payload-Digest\":\"sha1:FGLWPIYU3ACOEOOQUQBEZRBNO7WJKBGA\",\"WARC-Block-Digest\":\"sha1:BIJKZYG3PL2MBHEW4Z4KUIGWBBUYYRV4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296943483.86_warc_CC-MAIN-20230320114206-20230320144206-00707.warc.gz\"}"}