## 2 Problem Formulation and Related Work on Possible Solutions
### The Private Set Intersection Problem and Its Possible Solutions  
Reference [14] is one of the first papers to address the concept of PSI. That paper aims to solve the authentication problem of two distrusting parties through an impartial third party. [15] proposed a PSI protocol that does not require an impartial third party. It mainly uses asymmetric cryptography mechanisms, supplemented by hash functions, so that group members can know the intersection with other members. The protocol's key idea is to protect members' privacy through signature and verification mechanisms. However, this method faces a trade-off between information leakage and ease of use, and insiders can also spoof this protocol. Then, [16] proposed a protocol based on Oblivious Polynomial Evaluation; the primary polynomial can be expressed in the following formula:  
\[P\left(y\right) = \left(y-x_{1}\right)\left(y-x_{2}\right)\ldots\left(y-x_{n}\right) \tag{2}\]where \(y\in Y\), \(x_{i}\in X\), and \(i=1,\ldots,n\). From Equation (2), if \(y\) is included in the set X, the result after evaluating the polynomial will be 0, and otherwise, if it is not. Notice that we can apply the above polynomial to transform the PSI problem into an HE realizable form. Different from the conventional polynomial-based solution, [17] proposed the secure Pseudorandom Function (PRF)-based solution for PSI, in which the security of PRF is ensured by introducing an oblivious transfer (OT) protocol. Inspired by [17], many follow-ups OT-based methods have been proposed to solve the PSI problem. For example, [18] uses OT-extension optimization, which significantly improves the speed of Circuit-based and Bloom-filter-based PSI. [19; 20; 21] also applied the OT method to find the optimal solution for PSI. However, all the above OT-based methods have a common disadvantage: the communication cost will be proportional to the sets of two parties. This condition does not fit the requirement for our application landscapes (one set is large, and the other is relatively small in size). Reference [22] provided a HE-based PSI protocol. However, due to the time-consuming calculation of HE, it is prone to calculation errors once the number of operations is extensive. Hence, it took work to develop a practical PSI system with HE in the past. However, [22] did improve the computational and communication complexity of the HE-based PSI problem by combining many optimization methods so that it might be feasible to cope with an immense amount of computation and speed up the execution time. Reference [23] extends the work on [22] to deal with the Labeled PSI problem. Suppose a client wants to initiate a Labeled PSI request to a server. The Labeled PSI can be interpreted as each element in the set of servers having a corresponding label in the database, allowing the client to obtain the labels of the intersection elements. A simple illustrative example is as follows: Suppose there are three pieces of data on the Server, namely D1, D2, and D3, the labels corresponding to these three pieces of data are L6, L11, and L18, respectively, denoted as X = {(Di, Li)} = {(Di, L6), (D2, L11), (D3, L18)}. Suppose a client has two pieces of data, D2 and D5, denoted as Y = {Di} = {D2, D5}. Then, when the client initiates a PSI request to the Server, the answer will be {D2} (because the intersection element of the two sets is D2). When the client initiates a Labeled PSI request to the Server, the answer will be {(D2, L11)} (because the intersection element of the two sets is D2, the corresponding label is L11). Both [22] and [23] provide HE-based PSI solutions, and they meet the needs of our system to suppress the adverse effects brought by the man-in-the-middle attack. Moreover, both works have conducted optimization processes to deal with the case that \(\left\lvert X\right\rvert>>\left\lvert Y\right\rvert\), which aligns with our application landscape's assumptions.