A (2,1)-Distributed Point Function

Having read the general introduction to distributed point functions, you were left wondering how to reduce the size of the keys to send to the servers. Gilboa and Ishai, the inventors of DPFs introduced a \((2,1)\)-DPF which reduced the key sizes from \(O(L)\) to \(O(\operatorname{polylog}(L))\)[GI14]. In their Riposte paper[CgBM15], Corrigan-Gibbs, Boneh and Mazières introduced a simplified \((2,1)\)-DPF which generates slightly bigger keys of sizes \(O(\sqrt{L})\), but which is a lot easier to explain, and whose construction method can serve as a template to design a \((n, n-1)\)-DPF, albeit using more complex cryptographic primitives when \(n > 2\). This is the distributed point function implementation that we'll expose in this crypto bite.

The story so far

We have a cluster of two Riposte servers \(R_0\) and \(R_1\). Each one maintains a table \(\vec{t}\) of \(L\) rows, where each row contains an element of the finite field \(\mathbb F = \{0, 1, 2, \cdots, 2^{8 \times 160}\}\), i.e. a single whisp of 160 bytes. Each client wishing to upload a whisp \(m\) to the cluster computes

  1. \(l \overset{R}{\leftarrow} \{0, 1, 2, \cdots, L-1\}\)
  2. \((\vec{k_0}, \vec{k_1}) \leftarrow \operatorname{Gen}(l, m)\)
  3. send \(\vec{k_0}\) to \(R_0\) and send \(\vec{k_1}\) to \(R_1\)

Upon receiving \(\vec{k}\) from a client, server \(R\) computes \(\forall i \in \{0, 1, 2, \cdots, L-1\}\)

  1. \(m'_i \leftarrow \operatorname{Eval}(\vec{k}, i)\)
  2. \(\vec{t}[i] \leftarrow \vec{t}[i] + m'_i\)

In the toy example case, you've seen implementations for the algorithms \(\operatorname{Gen}(l, m)\) and \(\operatorname{Eval}(\vec{k}, i)\).

Our mission now is to design new algorithms \(\operatorname{Gen}\) and \(\operatorname{Eval}\) which reduce the key lengths \(|k_0|\) and \(|k_1|\) form \(O(L)\) to \(O(\sqrt{L})\).

The Matrix + PRG Trick

One problem with the toy example was that the size of the keys grew linearly with the table size \(O(L)\). We'll reduce this size by combining two tricks:

  • we view the table \(\vec{t}\) as a rectangular matrix, where each cell \(\vec{t}[l]\) is indexed by a row number \(l_x\) and a column number \(l_y\),
  • we make use of a pseudo random generator (PRG), a cryptographic primitive that can stretch small numbers (seeds) to much bigger numbers.

While the matrix trick is generalizable to the \((n, n-1)\)-DPF case with \(n > 2\), the PRG trick is \((2,1)\)-DPF specific.

As we'll see later, the point of using a rectangular matrix representation is that the size of the row- and column-indexes needed to address a cell grow only with the lengths of the sides, instead of with the area of the rectangle. Thus, these indexes will be \(O(\sqrt{L})\) instead of \(O(L)\).

The PRG's purpose is, of course, to implement secret sharing. And since a PRG stretches seeds, it also contributes in further reducing the key sizes.

Without loss of generality, we set \(\mathbb F = \mathbb Z_{2^k}\), i.e. each row contains an \(k\)-bit bitstring, interpreted as big integer.

Storing the table in a matrix

We turn the \(L\)-rows table \(\vec{t}\) into a matrix with \(x\) rows and \(y\) columns like this: find \(x\) and \(y\) such that \(xy \ge L\). In other words, we give ourselves an \(x \times y\) matrix large enough to contain all \(L\) elements of the table \(\vec{t}\). There are, of course, many possible choices for \(x\) and \(y\). The optimal choice will depend upon the PRG that we'll describe in the next subsection.

We then simply put (conceptually) the elements of \(\vec{t}\) into the matrix in a row-wise order:

\[ \pmatrix{m_0 \\ m_1 \\ \vdots \\ m_{L-1}} = \pmatrix{m_0 & m_1 & \cdots & m_{y-1} \\ m_y & m_{y+1} & \cdots & m_{2y-1} \\ \vdots & \vdots & \vdots & \vdots \\ m_{(x-1)y} & m_{(x-1)y+1} & \cdots & m_{(x-1)(y-1)}}  \]

(where unused cells in the matrix are set to zero, i.e. \(m_{l_x l_y} = 0, l_x l_y \ge L\)).

Of course, an implementation doesn't need to explicitly use a matrix or to copy elements from an array into a matrix. It could store all elements in a huge (one-dimensional) array \(\vec{t}\) of \(xy\) elements, and index that array like this: \(\vec{t}[l_xy + l_y]\), each times it wants to index the matrix element at row \(l_x\) and column \(l_y\). Or, leave that to the compiler to take care of.

A Pseudo Random Generator (PRG)

Our next ingredient is a pseudo random generator (PRG) \(\operatorname{G}: \mathbb S \rightarrow \mathbb F^y\), which expands seeds from a seed domain \(\mathbb S\) into matrix rows, i.e. into y-length vectors of \(\mathbb F\) elements: Picture something like this:

\[ \operatorname{G} \colon s \mapsto \pmatrix{m_{s_0} & m_{s_1} & \cdots & m_{s_{y-1}}} \]

In practice, one can use AES in counter mode to implement \(\operatorname{G}\). For example, when using AES-128, the seed space would be \(\mathbb S = \mathbb Z_{2^{128}}\).

Selecting x and y

As said before, optimal choices for \(x\) and \(y\) which mimimize the size of the keys generated by \(\operatorname{Gen}(l,m)\) depend on the specifics of the PRG \(\operatorname{G}\). More specifically, let \(\alpha\) be the length of an element of \(\mathbb S\) in bits, and let \(\beta\) be the length of an element of \(\mathbb F\) in bits (i.e. \(k\) when \(\mathbb F = \mathbb Z_{2^k}\)). It turns out that the following values for \(x\) and \(y\) are optimal:

\[ x = c \sqrt{L}, y = \frac{1}{c} \sqrt{L} \]

where

\[ c = \sqrt{\frac{\beta}{1 + \alpha}} \]

The paper[CgBM15] gives a concrete example:

  • a table with \(L=2^{20}\) rows (about 1 million rows),
  • of which each row contains 1KB (i.e. \(\mathbb F = \mathbb Z_{2^{8 \times 1024}}\), that is \(\beta = 8192\)),
  • and when using as PRG AES-128 (i.e. \(\mathbb S = \mathbb Z_{2^{128}}\), that is \(\alpha = 128\)).

By plugging in these values, we get keys of length roughly 263 KB instead of 1 GB as in the toy example, which is not only pretty impressive savings of bandwidth between clients and servers, but also affordable even for the most resource-constrained mobile apps scenario, i.e. battery and data plan saving.

Defining Gen(l,m) and Eval(k,l')

Now, with all ingredients in place, let's define the improved \((2,1)\)-distributed point function. Like with every DPF, we need to define the client-side algorithm \(\operatorname{Gen}(l,m)\), which generates a pair of keys \((\vec{k}_0, \vec{k}_1)\) to send to the servers \(R_0\) and \(R_1\), and the server-side algorithm \(\operatorname{Eval}(\vec{k}, l')\), which is used to element-wise compute a matrix \(M'\) to be added to the server state matrix.

Algorithm Gen(l,m)

We want to define an algorithm \(\operatorname{Gen}(l,m)\) which generates two keys \(\vec{k}_0\) and \(\vec{k}_1\). Server \(R_0\) will \(\operatorname{Eval}\)-uate \(\vec{k}_0\) to obtain matrix \(M'_0\), and server \(R_1\) will \(\operatorname{Eval}\)-uate \(\vec{k}_1\) to obtain matrix \(M'_1\). Both matrices will look pretty random, and neither server will be able to deduce from one matrix alone which row and column the user intended to update. By adding those matrices to their own internal state (matrix), the servers will update the (distributed) database.

Recall though the essential property that makes the matrices \(M'_0\) and \(M'_1\) suitable for a writable PIR scheme where multiple users can add their messages to randomly selected cells, without overwriting each others' entries (barring collisions):

\[ M'_0 + M'_1 = \pmatrix{0 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & m_{l_x l_y} & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & \cdots & 0} \]

In other words, \(M'_0 + M'_1\) is \(0\) everywhere, except at location \((l_x, l_y) \in \mathbb Z_x \times \mathbb Z_y\), with \(l = l_xy + l_y\).

Algorithm \(\operatorname{Gen}(l,m) \rightarrow (\vec{k}_0, \vec{k}_1)\):

  1. Compute \(l_x \in \mathbb Z_x\) and \(l_y \in \mathbb Z_y\) such that \(l = l_xy + l_y\).
  2. \(\vec{b}_0 := (b_0, \cdots, b_{l_x}, \cdots, b_{x-1}) \overset{R}{\leftarrow} \{0, 1\}^x\)
  3. \(\vec{b}_1 := (b_0, \cdots, \bar{b}_{l_x}, \cdots, b_{x-1})\)
  4. \(s^{*}_{l_x} \overset{R}{\leftarrow} \mathbb S\)
  5. \(\vec{s}_0 := (s_0, \cdots, s_{l_x}, \cdots, s_{x-1}) \overset{R}{\leftarrow} \mathbb S^x\)
  6. \(\vec{s}_1 := (s_0, \cdots, s^{*}_{l_x}, \cdots, s_{x-1})\)
  7. \(\vec{v} := m \cdot \vec{e}_{l_y} + \operatorname{G}(\vec{s}_0[l_x]) + \operatorname{G}(\vec{s}_1[l_x])\)
  8. \(\vec{k}_0 := (\vec{b}_0, \vec{s}_0, \vec{v}), \vec{k}_1 := (\vec{b}_1, \vec{s}_1, \vec{v})\)
  9. Return \((\vec{k}_0, \vec{k}_1)\)

In plain words:

  1. Locate the matrix cell that we want the servers to update in their shared database. Given \(x\) and \(y\), this is simple integer division and remainder.
  2. Sample a vector \(\vec{b}_0\) of \(x\) random bits, i.e. one random bit per row. We'll see below in algorithm \(\operatorname{Eval}\) what those bits are used for.
  3. \(\vec{b}_1\) is the same as \(\vec{b}_0\), but with bit at row \(l_x\) flipped.
  4. Sample a random seed in \(\mathbb S\).
  5. Sample a vector \(\vec{s}_0\) of \(x\) random seeds in \(\mathbb S\), i.e. one seed per row
  6. \(\vec{s}_1\) is the same as \(\vec{s}_0\), except for the random seed at row \(l_x\) sampled in step 4.
  7. \(\vec{e}_{r}\) is the unit vector of \(y\) components, with \(\vec{e}_{r}[i] = 0, \forall i \ne r\) and \(\vec{e}_{r}[r] = 1\). By multiplying with scalar \(m\), the resulting \(m \cdot \vec{e}_{l_y}\) is an \(y\)-element vector of all \(0\) except at index \(l_y\) where it is \(m\), i.e. \(m \cdot \vec{e}_{l_y} = \pmatrix{0 & \cdots & m & \cdots & 0}\). To this \(y\)-element vector, we add both expanded seeds \(\operatorname{G}(s_{l_x})\) and \(\operatorname{G}(s^{*}_{l_x})\), which happen to also be \(y\)-element vectors (see below)
  8. The resulting key \(\vec{k}_0\) has 3 vectors: the random bit vector \(\vec{b}_0\) from step 2 with \(x\) components, the random seed vector \(\vec{s}_0\) from step 5 with \(x\) components, and \(\vec{v}\) from step 7 with \(y\) components. Similarly, the resulting key \(\vec{k}_1\) has 3 vectors: the random bit vector \(\vec{b}_1\) from step 3 with \(x\) components, the random seed vector \(\vec{s}_1\) from step 6 with \(x\) components, and \(\vec{v}\) from step 7 with \(y\) components.
  9. The output of the \(\operatorname{Gen}\) algorithm is the pair \((\vec{k}_0, \vec{k}_1)\).  We send \(\vec{k}_0\) to server \(R_0\) and we send \(\vec{k}_1\) to server \(R_1\).

To clarify step 7, this is what happens:

\[ \pmatrix{v_0 \\ \vdots \\ v_{l_y} \\ \vdots \\ v_{y-1}} \leftarrow \pmatrix{0 \\ \vdots \\ m \\ \vdots \\ 0} + \pmatrix{G(s_{l_x})[0] \\ \vdots \\ G(s_{l_x})[l_y] \\ \vdots \\ G(s_{l_x})[y-1]} + \pmatrix{G(s^{*}_{l_x})[0] \\ \vdots \\ G(s^{*}_{l_x})[l_y] \\ \vdots \\ G(s^{*}_{l_x})[y-1]} \]

Algorithm Eval(k, l')

Now is time to specify algorithm \(\operatorname{Eval}(\vec{k}, l')\). Again, recall from the general introduction to distributed point functions that \(\operatorname{Eval}(\vec{k}, l')\) will compute the matrix element \(m' = M'[l_x][l_y]\) that the server will add to its own state matrix: \(M[l_x][l_y] \leftarrow M[l_x][l_y] + m'\). In other words, \(\operatorname{Eval}(\vec{k}, l)\) will be executed for every \(l\) in \(\{0,1,\cdots,L-1\}\).

Recall from the previous section that the key \(\vec{k}\) that \(\operatorname{Eval}(\vec{k}, l)\) gets is the tuple:

\[ ( \pmatrix{b_0 \\ \vdots \\ b_{x-1}}, \pmatrix{s_0 \\ \vdots \\ s_{x-1}}, \pmatrix{v_0 & \cdots & v_{y-1}} )\]

Algorithm \(\operatorname{Eval}(\vec{k}, l')\):

  1. \((\vec{b}, \vec{s}, \vec{v}) := \vec{k}\)
  2. Compute \(l'_x \in \mathbb Z_x, l'_y \in \mathbb Z_y\) such that \(l' = l'_xy + l'_y\)
  3. \(\vec{g} \leftarrow \operatorname{G}(\vec{s}[l'_x])\)
  4. \(m' \leftarrow (\vec{g}[l'_y] + \vec{b}[l'_x]\vec{v}[l'_y])\)
  5. Return \(m'\)

Or, in plain words:

  1. Interpret the key \(\vec{k}\) as the tuple \((\vec{b}, \vec{s}, \vec{v})\). Recall that \(\vec{b}\) is a vector of \(x\) random bits, \(\vec{s}\) is a vector of \(x\) seeds in \(\mathbb S\), and \(\vec{v}\), a \(y\)-element vector, encoded the message.
  2. Locate the matrix cell that we want to update, by converting the index \(l'\) into a row-index \(l'_x\) and a column-index \(l'_y\). In other words, we want to ultimatly compute \(m'\) that is to be added to our state \(M[l'_x][l'_y]\).
  3. Use the row index \(l'_x\) computed in step 2 to locate the seed \(\vec{s}[l'_x]\) in the seed vector \(\vec{s}\) from step 1. Expand this seed with the PRG \(\operatorname{G}\) into a \(y\)-element vector \(\vec{g} \leftarrow \operatorname{G}(\vec{s}[l'_x])\).
  4. To compute \(m'\) at index \((l'_x, l'_y)\), we add to \(\vec{g}[l'_y]\) the corresponding element \(\vec{v}[l'_y]\), but only if \(\vec{b}[l'_x]\) is \(1\).
  5. The result is the message \(m'\) to be added to the state matrix \(M[l_x][l_y]\) as already said.

Again, [CgBM15] shows a toy example with \(x=6\) rows, listing \(\vec{b}\), \(\vec{s}\), \(\vec{M}'\) in a table. In this case, the element \(m'\) is to be inserted in row \(l_x = 3\) and column \(l_y = 4\). \(R_0\) computes:

\[ ( \pmatrix{1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0}, \pmatrix{s_0 \\ s_1 \\ s_2 \\ s_3 \\ s_4 \\ s_5}, \pmatrix{ \operatorname{G}(s_0) + \vec{v} \\ \operatorname{G}(s_1) \\ \operatorname{G}(s_2) + \vec{v} \\ \operatorname{G}(s_3) + \vec{v} \\ \operatorname{G}(s_4) \\ \operatorname{G}(s_5)} ) \]

Server \(R_1\) computes instead:

\[ ( \pmatrix{1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0}, \pmatrix{s_0 \\ s_1 \\ s_2 \\ s^{*}_3 \\ s_4 \\ s_5}, \pmatrix{ \operatorname{G}(s_0) + \vec{v} \\ \operatorname{G}(s_1) \\ \operatorname{G}(s_2) + \vec{v} \\ \operatorname{G}(s^{*}_3) \\ \operatorname{G}(s_4) \\ \operatorname{G}(s_5)} ) \]

Correctness and Privacy

Refer to the paper[CgBM15] for a proof of correctness and a discussion on the privacy property of this \((2,1)\)-distributed point function.

The Path To A Real-World Riposte Cluster

With this \((2,1)\)-distributed point function, we can now implement an efficient Riposte cluster of 2 servers \(R_0\) and \(R_1\), such that as long as one of them isn't compromized, users' anonymity is guaranteed.

However, there is still some work to do before we get a stable Riposte system

  • A malicious user who doesn't respect the Riposte protocol could send two keys \((\vec{k_0}, \vec{k_1})\) that weren't generated by one run of \(\operatorname{Gen}(l, m)\) to the servers. Because both keys aren't related in this case, both \(R_0\) and \(R_1\) will thrash their shared distributed database. When then come together, they'll add their matrices and instead of recovering all messages submitted by the clients in this period, they'll get junk everywhere. In other words, one malicious user can with a single update delete all messages collected in a period. We must therefore ensure that the keys \((\vec{k_0}, \vec{k_1})\) are indeed legitimate, i.e. that they are issued by a run of the \(\operatorname{Gen}\) algorithm. The Riposte paper addresses this issue by adding a trusted audit server.
  • The issue of authenticating users and securing their connections to the Riposte servers wasn't addressed. Something like TLS 1.3 could be used between clients and servers. This is necessary to guarantee privacy (and correctness) in scenarios with passive or active attackers.
  • In practice, handling a huge number of client connections can be somewhat problematic. Middleware like ZeroMQ may be interesting.
  • We didn't discuss the issues of collisions, cf. Riposte paper.
  • If we wanted to support more than 2 Riposte servers, we'll need a \((n, n-1)\)-distributed point function for \(n \gt 2\). As said, we may reuse the matrix trick, but we'll have to replace the fast and efficient PRG with some other more powerful (but much less efficient) cryptographic primitives: seed-homomorphic PRGs[BLMR14], which can not be efficiently (i.e. yialding key sizes less than exponential in the number of servers) implemented with fast AES, but require algebraic groups, or lattice-based cryptography, making them orders of magnitude slower. Furthermore, the audit protocol for more than 2 Riposte servers require ZK proofs, as shown in [CgBM15, 5.2 Zero Knowledge Techniques].

This concludes this series on Riposte. I hope you've enjoyed it.

Literature