Proofs around affine space partitions

This page contains mathematical proofs in the context of hash functions from ordered affine partitions.

Proof that our procedure defines a valid partition

Here we prove that $\left(\mathfrak{A}_y\right)_{y \in \mathbb{Z}_2^{s}}$, computed as in the page hash functions from ordered affine partitions, effectively defines an ordered affine partition.

We defined the partition $\left(\mathfrak{A}_y\right)_{y \in \mathbb{Z}_2^{s}}$ inductively. Given a bitstring $y_1 \dots y_s$, the corresponding $\mathfrak{A}_{y_1 \dots y_s}$ is computed, for $i=s,...,1$, as:

$$\begin{align*} \mathfrak{A}_{y_1 \dots y_s}^{(s)} &:= \mathfrak{S}_{n-s}\\\ \mathfrak{A}_{y_1 \dots y_s}^{(j-1)} &:= M_{y_1...y_{j-1}}^{-1} \left( \mathfrak{A}_{y_1 \dots y_s}^{(j)} + y_{j}\delta_{n - j +1} \right)\\\ \mathfrak{A}_{y_1 \dots y_s} &:= \mathfrak{A}_{y_1 \dots y_s}^{(0)} \end{align*}$$

We prove by induction on $j=s,...,0$ that the set

$$\mathcal{A}_{y_1...y_j}^{(j)} := \left\{ \mathfrak{A}_{y_1 \dots y_s}^{(j)} \;\middle|\; y_{j+1}...y_{s} \in \mathbb{Z}_2^{s-j} \right\}$$

formed by the affine subspaces $\mathfrak{A}_{y_1 \dots y_s}^{(j)}$ with the first $y_1...y_j$ fixed is a partition of the subspace $\mathfrak{S}_{n-j}$ for any choice of $y_1 \dots y_j$.

The terminal case $j=0$ then implies that the set $\mathcal{A}_\varepsilon^{(0)}$ formed by the affine subspaces $\mathfrak{A}_{y_1 \dots y_s}$ for all ${y_1 \dots y_s} \in \mathbb{Z}_2^{s}$ is a partition of $\mathfrak{S}_{n} = \mathbb{Z}_2^n$. The proof proceeds as follows.

For the base case $j=s$, fix $y_1 \dots y_s$. Then by definition

$$\mathcal{A}_{y_1...y_{s}}^{(s)} = \left\{\mathfrak{U}^{(s)}_{y_1...y_{s}}\right\} = \left\{\mathfrak{S}_{n-s}\right\}$$

And $\mathfrak{S}_{n-s}$ is trivially a partition of itself.

For the inductive case $s > j \geq 0$, fix $y_1 \dots y_j$ and consider

$$\mathcal{A}_{y_1...y_j}^{(j)} := \left\{ \mathfrak{A}_{y_1 \dots y_s}^{(j)} \;\middle|\; y_{j+1}...y_{s} \in \mathbb{Z}_2^{s-j} \right\}$$

We need to prove that this is a partition of the subspace $\mathfrak{S}_{n-j}$.

Let's apply a rotation of $M_{y_1...y_{j}}$ to all subspaces of $\mathcal{A}_{y_1...y_j}^{(j)}$:

$$M_{y_1...y_{j}} \mathcal{A}_{y_1...y_j}^{(j)} := \left\{ M_{y_1...y_{j}}\mathfrak{A}_{y_1...y_{s}}^{(j)} \;\middle|\; y_{j+1}...y_{s} \in \mathbb{Z}_2^{s-j} \right\}$$

$\mathfrak{A}_{y_1...y_{s}}^{(j)}$ is defined inductively, and expanding the definition we have:

$$M_{y_1...y_{j}}\mathfrak{A}_{y_1...y_{s}}^{(j)} = M_{y_1...y_{j}} \left( M^{-1}_{y_1...y_{j}} \left( \mathfrak{A}_{y_1...y_{s}}^{(j+1)} + y_{j+1}\delta_{n-j}\right) \right) = \mathfrak{A}_{y_1...y_{s}}^{(j+1)} + y_{j+1}\delta_{n-j}.$$

And so:

$$M_{y_1...y_{j}} \mathcal{A}_{y_1...y_j}^{(j)} := \left\{ \mathfrak{A}_{y_1...y_{s}}^{(j+1)} + y_{j+1}\delta_{n-j} \;\middle|\; y_{j+1}...y_{s} \in \mathbb{Z}_2^{s-j} \right\}$$

Hence $M_{y_1...y_{j}} \mathcal{A}_{y_1...y_j}^{(j)}$ can be split into two subsets, based on the value of $y_{j+1}$:

$$\begin{align*} \left\{\mathfrak{A}_{y_1...y_{s}}^{(j+1)}\,\middle|\,y_{j+1}=0, y_{j+2}...y_{s} \in \mathbb{Z}_2^{s-(j+1)} \right\} \\\ \left\{\mathfrak{A}_{y_1...y_{s}}^{(j+1)}+ \delta_{n-j} \,\middle|\,y_{j+1}=1, y_{j+2}...y_{s} \in \mathbb{Z}_2^{s-(j+1)}\right\} \end{align*}$$

The first component is $\mathcal{A}_{y_1...y_j,0}^{(j+1)}$, which by hypothesis is a partition of $\mathfrak{S}_{n-(j+1)}$. The second component contains just every affine subspace in $\mathcal{A}_{y_1...y_j,0}^{(j+1)}$ shifted by the vector $\delta_{n-j}$. As such, it spans $\mathfrak{S}_{n-(j+1)} + \delta_{n-j}$.

Notice that by definition $\mathfrak{S}_{n-(j+1)}$ is the affine subspace spanning only the first $n-(j+1)$ components of $\mathbb{Z}_2^n$. Hence, $\mathfrak{S}_{n-(j+1)}$ and $\mathfrak{S}_{n-(j+1)} + \delta_{n-j}$ are parallel affine subspaces, and so they are disjoint. Moreover, since our base field is $\mathbb{Z}_2$, the union

$$\mathfrak{S}_{n-(j+1)} \sqcup \left(\mathfrak{S}_{n-(j+1)} + \delta_{n-j}\right)$$

spans the whole $\mathfrak{S}_{n-j}$. This proves that $M_{y_1...y_{j}} \mathcal{A}_{y_1...y_j}^{(j)}$ is a partition of $\mathfrak{S}_{n-j}$.

Since $M_{y_1...y_{j}}$ is bijective and acts only on the first $n-j$ components of its input, it sends every vector in $\mathfrak{S}_{n-j}$ to a vector in $\mathfrak{S}_{n-j}$. This means that multiplying every element of a partition of $\mathfrak{S}_{n-j}$ by $M^{-1}_{y_1...y_{j}}$ gives back a partition of $\mathfrak{S}_{n-j}$.

Hence $\mathcal{A}_{y_1...y_j}^{(j)}$, which can be obtained by multiplying every element of the partition $M_{y_1...y_{j}} \mathcal{A}_{y_1...y_j}^{(j)}$ by $M^{-1}_{y_1...y_{j}}$, is a partition of $\mathfrak{S}_{n-j}$. This concludes the proof.

Proof of property 1 of the hash function

Here we prove that the functions

$$\begin{align*} \mathbb{Z}_2^n &\xrightarrow{h} \mathbb{Z}_2^s\\\ \mathbb{Z}_2^n \times \mathbb{Z}_2^s &\xrightarrow{h^\perp} \mathbb{Z}_2 \end{align*}$$

defined in the page hash functions from ordered affine partitions satisfy the following property:

$h(x_1 \dots x_n) = y_1 \dots y_s$ if and only if the vector with coordinates $(x_1, \dots, x_n)$ is in the affine subspace corresponding to the bitstring $y_1 \dots y_s$.

First of all, recall that the affine subspace corresponding to $y_1 \dots y_s$ is calculated inductively for $s \geq j \geq 1$ via the following procedure:

$$\begin{align*} \mathfrak{A}_{y_1 \dots y_s}^{(s)} &:= \mathfrak{S}_{n-s}\\\ \mathfrak{A}_{y_1 \dots y_s}^{(j-1)} &:= M_{y_1...y_{j-1}}^{-1} \left( \mathfrak{A}_{y_1 \dots y_s}^{(j)} + y_{j}\delta_{n - j +1} \right)\\\ \mathfrak{A}_{y_1 \dots y_s} &:= \mathfrak{A}_{y_1 \dots y_s}^{(0)} \end{align*}$$

On the other hand, given a bitstring $x_1 \dots x_n$, its corresponding hash is calculated inductively as follows for $1 \leq j \leq s$:

$$\begin{align*} u^{(0)} &:= (x_1, \dots, x_n) \\\ u^{(j)} &:= \zeta_{n-j+1}\left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right) \\\ y_{j} &:= \pi_{n-j+1} \left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right) \\\ \end{align*}$$

We want to prove by induction that $u^{(j)} \in \mathfrak{A}_{y_1 \dots y_s}^{(j)}$ for all $j$. Take $j = s$ as base case, and descent all the way to $j = 1$.

For the base case $j=s$, notice that by construction $\mathfrak{A}_{y_1 \dots y_s}^{(s)} := \mathfrak{S}_{n-s}$. On the other hand, $u^{(s)}$ is defined inductively from $u^{(0)}$, and at each step we apply a $\zeta_{n-j+1}$ which sets the $(n-j+1)$-th bit to $0$. This bit is not touched by any subsequent application of the matrices $\left(M_y\right)_{y \in \mathbb{Z}_2^{< s}}$ because of how they are defined. This means that all the bits from $n-s+1$ to $n$ in $u^{(0)}$ are $0$, and so $u^{(0)}$ is in $\mathfrak{S}_{n-s}$, as we wanted.

As for the inductive case, just consider:

$$\begin{align*} \mathfrak{A}_{y_1 \dots y_s}^{(j-1)} &:= M_{y_1...y_{j-1}}^{-1} \left( \mathfrak{A}_{y_1 \dots y_s}^{(j)} + y_{j}\delta_{n - j +1} \right)\\\ u^{(j)} &:= \zeta_{n-j+1}\left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right) \\\ y_{j} &:= \pi_{n-j+1} \left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right) \\\ \end{align*}$$

By inductive hypothesis, $u^{(j)} \in \mathfrak{A}_{y_1 \dots y_s}^{(j)}$, and so we can evaluate $\mathfrak{A}_{y_1 \dots y_s}^{(j-1)}$ on $u^{(j)}$:

$$\begin{align*} M_{y_1...y_{j-1}}^{-1} \left( u^{(j)} + y_{j}\delta_{n - j +1}\right) &= M_{y_1...y_{j-1}}^{-1} u^{(j)} + M_{y_1...y_{j-1}}^{-1} \left(y_{j}\delta_{n - j +1}\right)\\\ &= M_{y_1...y_{j-1}}^{-1} \left( \zeta_{n-j+1}\left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\right)\\\ & \qquad + M_{y_1...y_{j-1}}^{-1} \left(\pi_{n-j+1} \left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\delta_{n - j +1}\right) \end{align*}$$

Now notice that $\zeta_{n-j+1}$ operates only on bit $n-j+1$, which is left untouched by $M_{y_1...y_{j-1}}^{-1}$. A similar consideration holds for $\pi_{n-j+1}$ and $M_{y_1...y_{j-1}}^{-1}$. So we can write:

$$\begin{align*} M_{y_1...y_{j-1}}^{-1} \left( \zeta_{n-j+1}\left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\right) &+ M_{y_1...y_{j-1}}^{-1} \left(\pi_{n-j+1} \left(M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\delta_{n - j +1}\right)\\\ &= \zeta_{n-j+1} \left( M_{y_1...y_{j-1}}^{-1} M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\\\ & \qquad + \pi_{n-j+1} \left(\left(M_{y_1...y_{j-1}}^{-1} M_{y_1\dots y_{j-1}} u^{(j-1)}\right)\delta_{n - j +1}\right)\\\ &= \zeta_{n-j+1} \left(u^{(j-1)}\right) + \pi_{n-j+1} \left(M_{y_1...y_{j-1}}^{-1} M_{y_1\dots y_{j-1}} u^{(j-1)}\delta_{n - j +1}\right)\\\ &= \zeta_{n-j+1} \left(u^{(j-1)}\right) + \pi_{n-j+1} \left( u^{(j-1)}\right)\delta_{n - j +1}\\\ &= u^{(j-1)} \end{align*}$$

Hence $u^{(j-1)} \in \mathfrak{A}_{y_1 \dots y_s}^{(j-1)}$. This concludes the proof by observing that, for $j=1$,

$$x_1 \dots x_n = u^{(0)} \in \mathfrak{A}_{y_1 \dots y_s}^{(0)} = \mathfrak{A}_{y_1 \dots y_s}.$$