Oblivious Programmable PRF

The OPPRF ideal functionality \(\mathcal{F}^{m_1,m_2}_{\mathsf{opprf}}\) is parameterized by:

• \(m_1\): upper bound on the number of programmable points
• \(m_2\): upper bound on the number of receiver queries

The protocol proceeds as follows:

1. Sender sends programmed points \(\mathcal{P} := \{(a_1,t_1), \ldots, (a_{m_1},t_{m_1})\}\) with distinct keys \(a_i\).
2. Receiver sends \(m_2\) distinct queries \((q_1,\ldots,q_{m_2})\).
3. The functionality runs \(k \leftarrow \mathsf{KeyGen}(\kappa, \mathcal{P})\).
4. Output \(k\) to Sender, \(\{F(k,q_1), \ldots, F(k,q_{m_2})\}\) to Receiver.

If \(q_j = a_i\) for some \(i\), then \(F(k,q_j) = t_i\). Otherwise, \(F(k,q_j)\) is pseudorandom.

An Oblivious Key Value Store can be viewed as a non-interactive version of an OPPRF that can also be sent in the clear [1]. While an OPPRF requires interaction between sender and receiver, an OKVS encodes programmed key-value pairs into a data structure \(S\) that the receiver can decode locally. A polynomial is the most compact form of an OKVS.

The original construction from [2] builds an OPPRF from an OPRF and polynomial interpolation:

1. Sender holds programmed points \(\mathcal{P} = \{(a_i, t_i)\}_{i \in [m_1]}\). Receiver holds queries \(Y = \{y_j\}_{j \in [m_2]}\).
2. Sender and receiver run an OPRF: the receiver obtains \(\{F(k, y_j)\}\) for each \(y_j \in Y\), and the sender obtains key \(k\).
3. Sender interpolates a polynomial \(P\) of degree \(m_1 - 1\) over the points \(\{(a_i,\ t_i \oplus F(k, a_i))\}_{i \in [m_1]}\). That is, \(P(a_i) = t_i \oplus F(k, a_i)\) for all \(i\).
4. Sender sends \(P\) to the receiver.
5. Receiver computes \(\mathsf{out}_j = F(k, y_j) \oplus P(y_j)\) for each query \(y_j\).

If \(y_j = a_i\) for some \(i\), then \(P(y_j) = t_i \oplus F(k, a_i)\), so \(\mathsf{out}_j = F(k, a_i) \oplus t_i \oplus F(k, a_i) = t_i\). Otherwise, \(P(y_j)\) is an unrelated field element and \(\mathsf{out}_j\) is pseudorandom (since \(F(k, y_j)\) is pseudorandom and independent of \(P(y_j)\)).

The polynomial can be replaced by any Oblivious Key Value Store encoding, which is how modern constructions work: the sender encodes \(\{(a_i,\ t_i \oplus F(k, a_i))\}\) into an OKVS structure \(T\) instead of a polynomial, and the receiver decodes \(\mathsf{Decode}(T, y_j)\) in place of evaluating \(P(y_j)\).

OPPRFs are primarily used in multi-party private set intersection (PSI) protocols. The sender programs the PRF on its set elements with specific values, and the receiver evaluates on its own set. Matching elements yield the programmed values, while non-matching elements produce pseudorandom outputs, enabling set intersection without revealing non-intersecting elements.