How to express a coin flip based random generator mathematically?

Question

I would like to know how to express a coin flip based random generator mathematically.

I have recently started Dan Boneh's Cryptography 1 and in the slides a pseudo random generator G, which outputs n-bit sequences, is defined as $G:K \rightarrow \left\{0,1\right\}^n$.

So following this I have come up with this for a coin flip: $$ G(n) = \left\{0,1\right\}^n $$

The idea is that n is the number of tosses and the function G will output n-bit length random numbers. The latter part with curly braces and the exponent $\left\{0,1\right\}^n$ is something I have not come across before. Is this a notation that's only used in cryptography?

Formal definitions are definitely a weak point for me so I don't know if I'm way off. Or if there's some better way to express this. Or if I'm approaching this completely wrong.

Answer 1

Boneh's definition of a pseudorandom generator stipulates that a PRG is a mathematical function—a mapping from an input domain to an output codomain such that the choice of argument value uniquely determines the result. In recent programming parlance, this is what people often call a pure function, like in pure functional programming languages (e.g. Haskell)—one whose results depend exclusively on the value of its arguments, and not on the state of the program.

Coin flips clearly do not fit under that definition, because they're non-deterministic—calling the coin-flip "function" (really an imperative programming routine) twice with the same argument is supposed not to always produce the same result. So a sequence of coin flips is not a PRG.

Mathematically, the concept we'd use to model coin flips is random variables. The outcome of a coin flip is a random variable. The outcome of a sequence of coin flips can also be seen as a random variable: you can describe the former as an experiment that repeatedly takes samples of the outcomes of single coin flips.

Answer 2

$\newcommand{\Nat}{\mathbb{N}}\newcommand{\R}{\mathbb{R}}$When $S$ is a set, the notation $S^n$ is standard mathematics notation for the $n$-fold cartesian product $S \times S \times \dots \times S$, whose elements are tuples $(s_0, s_1, \dots, s_{n-1})$ with $s_i \in S$ for each $i$. For example, $\R^2$ is the set of points in the euclidean plane with a choice of origin. In the case of $\{0,1\}^n$, the set is the set of bits.

You could express what you said about $G$ by writing that the function $G\colon {\Nat}^0 \to \{0,1\}^*$ has the property that $G(n) \in \{0,1\}^n$ for each $n \in \Nat^0$, where $\Nat^0$ is the set of natural numbers starting at zero.

Of course, you would presumably want to define a distribution on the set of all such functions $G$, and since the domain $\Nat^0$ is infinite, there are infinitely many such functions, which means you can't have a uniform distribution as we usually want in crypto.

So you might limit it to some maximum $N$, and talk about the space of functions $G\colon \{0,1,2,\dots,N-1\} \to \{0,1\}^*$ with $G(n) \in \{0,1\}^n$ for each integer $0 \leq n < N$, and then you can have a uniform distribution on that space. Then you can compare it to the distribution on an easily computed indexed family of functions $H_k\colon \{0,1,2,\dots,N-1\} \to \{0,1\}^*$ induced by a uniform distribution on a seed/key $k$, and study how easy it is to distinguish that from the uniform distribution on all functions $G\colon \{0,1,2,\dots,N-1\} \to \{0,1\}^*$.

However, in crypto we often don't deal with uniform distributions on that space! For example, for a fixed message, neither keyed SHAKE256 nor ChaCha aspires to mimic that distribution. Why not? Because SHAKE256-$u$ is a prefix of SHAKE256-$v$ when $u < v$, which is a property shared only by a tiny subspace of the functions $G$.

Instead, we ask that for a fixed message/nonce and a fixed output length $n$, keyed SHAKE256 and ChaCha be indistinguishable from the uniform distribution on all bit strings.

I say ‘fixed message/nonce’ too because really we really usually think of keyed SHAKE256 and ChaCha as distributions on functions of messages $F_{\ell,n}: \{0,1\}^\ell \to \{0,1\}^n$. In the case of SHAKE256, the input to the function can vary in length $\ell$ up to arbitrarily long messages; in the case of ChaCha, the input length $\ell$ is always the nonce length, at most 128 with the remaining bits for a counter determining how many bits $n$ can have.

That said, sometimes we do want different output lengths to appear unrelated, though, and other constructions such as BLAKE2b provide that, by hashing the length into the message too. This makes BLAKE2b better resemble a random oracle.