1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\{0,1\}^n$ is the set of all bit strings of length $n$. Defining $G(n)$ to be a set is probably not what you want but I'm not sure I understand what your question is. Are you redefining $G$? $\endgroup$ – Elias Aug 14 '17 at 15:22
  • $\begingroup$ Sorry for being unclear. I did not intend to redefine G. I just used the example from Boneh's slides and due to my stupidity wanted to change it into a function form :)So I guess my question is how to define a function that takes n as input and outputs n-bit random numbers? Or if I'm asking this wrong how to express mathematically a coin toss that outputs random numbers based on n number of tosses? $\endgroup$ – mat Aug 14 '17 at 15:33
  • $\begingroup$ Just to be clear - what comes out of your generator? Is it like HHTTHTHT or 230, 5, 0, 29? $\endgroup$ – Paul Uszak Aug 14 '17 at 15:44
  • $\begingroup$ $G: K \rightarrow \{0,1\}^n$ already is a function definition and it takes a seed $K$ and outputs a pseudorandom $n$-bit string. Writing down the transformation of $K$ explicitly is probably a bit hard to do in one line for any decent PRNG. $\endgroup$ – Elias Aug 14 '17 at 16:14
  • $\begingroup$ "what comes out of your generator? Is it like HHTTHTHT" Yes, like HHTTHTHT or 11001010. And the length depends on how many times the coin is tossed. How to express this mathematically? $\endgroup$ – mat Aug 14 '17 at 16:37
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for clearing out my confusion about functions. I see now that I was trying to use the PRG definition in Boneh's slides to do something that it's not supposed to do. The PRG in the slides always (deterministically) produces the same output for the same seed unlike a coin toss. Could you add to your answer the mathematical expression of the last paragraph, i.e. how to define a coin filp and a sequence of coin flips with mathematical symbols? $\endgroup$ – mat Aug 15 '17 at 0:30
  • $\begingroup$ He already did. That is what a random variable is. Ironically, it is again just a deterministic function except that the inputs come from a probability space. $\endgroup$ – Elias Aug 15 '17 at 13:29
  • $\begingroup$ @mat: I recommend you just review notation for probability and statistics. I don't know that there's a brief consensual way of notating a random variable that's obtained by an experiment over others. In this case I'd write something like this: the random variable $G_n = b_1\dots b_n$, where each $b_i$ is the outcome of an independent coin flip. In any case I would encourage you to read some more of the course materials and mimic the language that they use. $\endgroup$ – Luis Casillas Aug 15 '17 at 18:51
0
$\begingroup$

$\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.

$\endgroup$
  • $\begingroup$ Thank you for being so kind to explain basic notation to me. I apparently misunderstood it which partially caused me to ask the question wrong. $\endgroup$ – mat Aug 15 '17 at 0:40

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.