Skip to main content
Clarify how the _distribution_ on functions G is relevant to concrete crypto constructions.
Source Link
Squeamish Ossifrage
  • 49.5k
  • 3
  • 118
  • 227

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

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

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.

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

Source Link
Squeamish Ossifrage
  • 49.5k
  • 3
  • 118
  • 227

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

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.