Unbalanced Labeled PSI in a server and receiver setting requires the server to perform a PSI and return the labels corresponding to items in intersection. I should also mention that in our case we need (1) unbalanced PSI, since set size hosted on server is lot bigger than set on client and (2) labeled PSI since instead of returning a boolean value whether intersection is null or not, we want to return the label (ie data) associated with items at intersection.

Homomorphic Encryption apparently so far is the only way to construct unbalanced PSI.

Moreover, in our case we don't require the set hosted on server to be private. It is ok, if PSI leaks information to the client. The implication of this is that we don't have to care about circuit privacy. Hence, we can get rid of OPRFs and other methods that such protocols use to prevent client from learning anything about set hosted on server. This should give improvements in offline phase (ie preprocessing) on server side, but I am unsure whether there will be concrete performance gains at the time of online phase (ie request latency).

Below I have given a short description of idea behind unbalanced PSI and labeled unbalanced PSI.

Unbalanced PSI: The idea is quite simple. Let's say user `A` wants to find whether a value x exists in set hosted by server. `A` encrypts and sends x to the server. The server evaluates the following polynomial on the input.

$$
z = \prod_{j=0}^n x - y_j
$$
$z$ will be 0 if $x \in y$, otherwise some random value.
You will notice that the degree of polynomial is $n$.
Following this basic blueprint, the core ideas are in how to homomorphically evaluate this polynomial as cheaply as possible for as many inputs.

Unbalanced PSI with labels: The goal here changes from just returning a boolean value of whether $x\in y$ to returning the label corresponding to $x$ stored on the server. Key idea here is to use polynomial interpolation to construct $G(x)$ as,
$$
G(x)=
\begin{cases}
l_i,& \text{if } x=y_i\\
random\space element, & \text{otherwise}
\end{cases}
$$
Moreover since we don't require privacy of the set $Y$, we can modify $G(x)$ to
$$
G(x)=
\begin{cases}
l_i,& \text{if } x=y_i\\
0, & \text{otherwise}
\end{cases}
$$
This will save us from additional requirements to suffice circuit privacy.

For performance I will refer you to [this paper](https://eprint.iacr.org/2021/1116) and its [implementation](https://github.com/microsoft/APSI). However, calculating exact performance values for our application might be hard without a prototype.

I can have a go at the prototype (it will be quite fun!). But before I prototype I wanted to ask about the set size and the size of the label (ie tx size).

Do let me know if you any questions.