Multiparty Private Set Intersection Cardinality and Its Applications

Nutshell. Two algorithms: Encode takes a set of key-value encryptions as input and returns an encoding. Decode takes an encoding and a key as input and returns a value. It consists of two algorithms:

• Encode. \(\mathsf{Encode}(\{k_i,v_i\}_{i\in [m]}) \rightarrow S\). Takes as input a set of \((k_i,v_i)\) key-value pairs from the key-value domain, \(\mathcal{K}\times \mathcal{V}\), and outputs an object \(S\) (or \(\bot\) with negligible probability)
• Decode. \(\mathsf{Decode}(S,k)\rightarrow v\). Decode takes as input an object \(S\), a key \(k\) and outputs a value \(v\).

Note from Peter: No guarantees on the output of Decode when the key is not present in the store.

Note, in the OPRF used in this paper the receiver chooses queries first. Setting. There are 2 parties: Sender and Receiver. There is a public bound \(m\) on the number of queries made by the receiver.

1. Receiver sends the \(m\) queries \((q_1,\ldots,q_m)\) to the functionality where \(q_i\in \{0,1\}^{\kappa}\).
2. Functionality samples a random PRF key \(k\).
3. Output \(k\) to Sender, \(\{F(k,q_1), \ldots, F(k,q_m)\}\) to Receiver.

This one is programmable. \(m_1\) is the upper bound on the number of points that can be programmed. \(m_2\) is the bound on the number of queries.

1. Sender sends points \(\mathcal{P} := \{(a_1,t_1), \ldots, (a_{m_1},t_{m_1})\}\) with distinct keys \(a_i\) to the functionality.
2. Receiver sends \(m_2\) distinct queries \((q_1,\ldots,q_{m_2})\) to the functionality.
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.

The functionality provides all parties

• a function \(\mathcal{S}:\{0,1\}^{\kappa}\times \{0,1\}^{\ell} \rightarrow \{0,1\}^{\kappa}\), and
• a key \(K_i\) for party \(P_i\)

such that for every \(x\in\{0,1\}^{\ell}\), we have that

• \(s_i = S(K_i, x)\), (\(s_i\) is \(P_i\)'s random share) and
• \(\oplus\limits_{i=1}^n s_i = 0\)

The functionality works as follows:

1. All parties start with a sharing function \(S\).
2. Functionality provides \(K_i\) to party \(P_i\).
3. When a party \(P_i\) invokes \(S(K_i,x)\), the functionality outputs \((K_i,\mathsf{store}_{x,i})\) to \(P_i\) if it exists. Otherwise,
   • Generate random \(s_1,\ldots,s_n\) such that
     • \(s_i = S(K_i,x)\)
     • \(\oplus\limits_{i=1}^n s_i = 0\)
   • Store \(\mathsf{store}_{x,i}=s_i\) for \(i\in [n]\)

Each party holds \(m\) elements. The functionality works as follows:

1. Each party \(P_i\) sends \(X_i\) of \(m\) distinct elements.
2. Output to \(P_1\) \(|\cap\limits_{i=1}^n X_i|\)

Each party holds an \(m\) element binary vector.

1. Each party \(P_i\) sends \(\vec{x_i}\) to the functionality.
2. The functionality outputs \(\sum\limits_{j=1}^m\prod\limits_{i=1}^n{x_i}[j]\) to party \(P_1\).

• Sender \(\mathcal{S}\) creates a key \(k = (k_1,k_2)\) where \(k_1\in \{0,1\}^{\kappa}\) and uses it as input.
• Define \(F'(k,x) = F'((k_1,k_2), x) = F(k_2, F(k_1, x))\).
• Receiver has input \(Y := \{y_1, \ldots, y_m\}\).
• Sender \(\mathcal{S}\) sends \(k_1\) to the receiver \(\mathcal{R}\).
• Sender \(\mathcal{S}\) sends \(k_2\) to the server \(\mathcal{C}\).
• Receiver \(\mathcal{R}\) computes \(Y' = F(k_1, Y)\).
• Receiver \(\mathcal{R}\) sends \(Y'\) to the server \(\mathcal{C}\).
• The server \(\mathcal{C}\) chooses a random permutation \(\pi: [m] \rightarrow [m]\).
• The server \(\mathcal{C}\) computes \(Y'' = F(k_2, Y')\).
• The server \(\mathcal{C}\) sends \(\pi(Y'')\) to the receiver \(\mathcal{R}\).

Similar to \(\mathsf{OPRF}-\Pi^{(m)}_{\mathsf{soprf}}\), except that there is no shuffling.

Sender -> $`\mathcal{F}^{(m_2)}_{\mathsf{soprf}}`$: $`k := (k_1,k_2) \in \{0,1\}^{2\kappa}`$

1. Sender \(\mathcal{S}\), Receiver \(\mathcal{R}\), and server \(\mathcal{C}\) invoke \(\mathcal{F}^{(m_2)}_{\mathsf{soprf}}\) with inputs \(k := (k_1,k_2) \in \{0,1\}^{2\kappa}\) for sender \(\mathcal{S}\), \(Y := \{y_i\}_{i\in [m_2]}\) for receiver \(\mathcal{R}\).
2. Note that \(\mathcal{F}^{(m_2)}_{\mathsf{soprf}}\) is non-shuffled.
3. Server \(\mathcal{C}\) obtains \(k_2\), and receiver \(\mathcal{R}\) obtains \(Y' = \{y'_1,\ldots, y'_{m_2}\}\). Note, here \(y'_i = F'(k,y_i)\).
4. Sender \(\mathcal{S}\) constructs an OKVS over \(T \leftarrow \mathsf{Encode}(\{x_i, F'(k,x_i)\oplus v_i\})\).
5. Sender sends \(T\) to \(\mathcal{R}\).