Two-Party Threshold Private Set Intersection Protocols from Lightweight Cryptographic Primitives ^†

Abstract

Private Set Intersection (PSI) is a significant application of interest within Secure Multi-party Computation (MPC), even though we are still in the early stages of deploying MPC solutions to real-world problems. Threshold PSI (tPSI), a variant of PSI, allows two parties to determine the intersection of their respective sets only if the cardinality of the intersection is at least (or less than) a specified threshold t. In this paper, we propose a generic construction for two-party tPSI that extensively utilizes Oblivious Transfer (OT). Our approach is based on lightweight primitives and avoids costly public-key systems such as homomorphic encryption. We start by introducing the secret-sharing private membership test ${}^{\mathrm{ss}}\mathrm{PMT}$ that is based on the secret-sharing private equality test ${}^{\mathrm{ss}}\mathrm{PEQT}$. The ${}^{\mathrm{ss}}\mathrm{PMT}$ enables tPSI to be scaled for a wide range of practical applications, particularly benefiting parties with limited computational resources. Consequently, two distinct two-party tPSI protocols can be efficiently implemented: over-threshold PSI ($t^{\le }\mathrm{PSI}$) and under-threshold PSI $t^{>}\mathrm{PSI}$. In addition, we propose a lightweight two-party tPSI with limited leakage and a generic precomputing OT suitable for phased implementation. Experimental performance demonstrates that our protocols are highly efficient and computationally friendly, thus paving the way for broader deployment of tPSI solutions.

1. Introduction

Originating from Yao’s millionaire’s problem [1] in 1982, secure Multi-party Computation (MPC) has witnessed notable achievements as a research area and in experimental performance. However, we remain in the early stages of implementing MPC solutions for real-world applications [2]. Researchers have shown growing interest in private set operations, which encompass intersection, union, counting, summation, and more general functions relating to intersections or unions. Private set operations enable two or more parties to perform calculations on their datasets without disclosing the actual data to one another. This mechanism ensures that sensitive information stays confidential, which is especially critical in sectors such as healthcare, finance, and personal data management.

Private Set Intersection (PSI) allows two parties, denoted by Alice and Bob with their respective sets X and Y, to compute the intersection $X\cap Y$ without revealing any additional information about either set. As a specific research field within MPC, and driven by practical applications, PSI has been a topic of significant interest across various fields. Recently, extensive research papers have been published, focusing on various aspects of PSI, including efficiency [3,4,5], the functionality of union operations [6,7], the security of PSI in the two-party scenario [8], multiparty [9,10], and server-aided settings [11], as well as various adversary models [12]. A growing body of literature highlights the importance and practical applications of PSI in different scenarios, such as online ad conversion rates [13], privacy-preserving contact tracing [14], searchable encryption scheme [15] and vertical Federated Learning [16].

Threshold PSI (tPSI) enables the parties to learn the intersection only if the number of their common items is sufficiently large, i.e., a threshold t. PSI with Cardinality (${\mathrm{PSI}}^{\mathrm{CA}}$) [17] is designed to limit the output to the size of the intersection, revealing nothing else about the sets involved. Thus, the construction of tPSI protocols typically invokes ${\mathrm{PSI}}^{\mathrm{CA}}$ as an intermediary computation. We take over-threshold PSI protocol ($t^{\le }\mathrm{PSI}$) as an example; the protocol $t^{\le }\mathrm{PSI}$ outputs the intersection only when the cardinality is greater than or equal to the threshold (i.e., $t\le$ ${\mathrm{PSI}}^{\mathrm{CA}}$). In this paper, we define that if the cardinality matches the threshold, the protocol still outputs the intersection. Apparently, tPSI reduces to normal PSI when $t=0$, and it is equivalent to ${\mathrm{PSI}}^{\mathrm{CA}}$ when $t=\left|X\right|=\left|Y\right|=n$. Intuitively, ${\mathrm{PSI}}^{\mathrm{CA}}$ serves as a building block in the design of tPSI protocol. That is to say, to carry out tPSI in a secure way, one could simply invoke ${\mathrm{PSI}}^{\mathrm{CA}}$ as a subprotocol first and then securely compare the output of ${\mathrm{PSI}}^{\mathrm{CA}}$ with a specified threshold t. Finally, tPSI outputs the intersection by invoking any standard PSI protocol if ${\mathrm{PSI}}^{\mathrm{CA}}$ is greater than (or less than) the threshold t. However, this straightforward method for implementing tPSI is often inefficient due to the independent nature of the two protocols ${\mathrm{PSI}}^{\mathrm{CA}}$ and PSI. Moreover, to the best of our knowledge, most existing ${\mathrm{PSI}}^{\mathrm{CA}}$ constructions rely heavily on public-key primitives. Without resorting to generic MPC methods, designing a lightweight tPSI protocol indeed presents a significant challenge, but it is not insurmountable.

1.1. Related Work

The studies in the field of tPSI have primarily focused on minimizing communication cost [18,19,20], often at the expense of computational efficiency due to expensive public-key operations such as homomorphic encryption. While effective in reducing network data transfer, they fail to address scenarios where participants have computational limitations, which is crucial for practical, lightweight implementations. Ghosh and Simkin [21] demonstrated that the communication complexity can be sublinear in the set size and showed a lower bound on the communication complexity of any protocol for the two-party case that is based on fully homomorphic encryption (FHE). Branco et al. [22] presented a multi-party cardinality testing approach based on threshold additively homomorphic encryption (AHE). This method allows for the verification of whether the intersection of input sets exceeds $(n-t)$, where n represents the size of each individual set and t denotes a specific threshold. Furthermore, they developed an l-party threshold PSI protocol with communication complexity $O\left(l{t}^2\right)$. Badrinarayanan et al. [23] examined two functionalities tailored for the multi-party case. They rigorously proved that both functionalities require at least $\mathsf{\Omega }\left(nt\right)$ bits of communication. This finding underscores the inherent communication complexity involved in such multi-party protocols. They also solved an open problem in [21] by building a two-party threshold PSI protocol with communication complexity $\tilde{O}\left(t\right)$ from assumptions weaker than FHE. Recently, the communication optimization and new functionality for multi-party protocols have been proposed, expanding the research scope of tPSI. Based on AHE and Oblivious Transfer (OT), Ghosh and Simkin [24] proposed an l-party threshold PSI protocol with a communication complexity of $O\left({\lambda }^{2}lt\mathrm{poly}\left(\log t\right)\right)$, where $\lambda$ is the security parameter. Liu et al. [25] introduced a new notion called probabilistic tPSI, where the parties learn the intersection with probability proportional to the size of it. In [26], the protocol securely computes which element appears in at least t sets of lightweight parties. In addition, Mohanty et al. [27] proposed the first quantum secure tPSI protocol which has a direct application in privacy-preserving ride sharing.

Constructing tPSI based on lightweight techniques with better efficiency is non-trivial. This line of research is attractive because, in general, few cryptographic techniques achieve both computational and communicational efficiency when designing PSI and variants. Oblivious Transfer is currently one of the most popular methods for investigating how to construct an efficient PSI protocol [28,29,30] and its variants in different settings [31] and adversary models [32,33]. Compared to a naïve hashing solution, OT-based private set operations, leveraging the OT extension technique, balance communication and computation costs well and are currently one of the most popular methods. Batched OPRF (Oblivious Pseudorandom Function) and VOLE (Vector Oblivious Linear Evaluation) can be generated through the use of the OT extension mechanism [34]. Orrù et al. [35] described a random actively secure 1-out-of-n OT extension protocol and applied it as a building block to improve the performance of PSI. Zhao et al. [36] proposed lightweight tPSI based on OT, ensuring that the computational complexity is independent of the set size. Also in two-party computation scenarios, Hu et al. [37] studied tPSI using FHE within the realm of cloud computing, where the server has a larger dataset than the client. By carefully selecting and optimizing cryptographic primitives and by leveraging efficient algorithms and design patterns, it is possible to design a protocol that balances security, efficiency, and simplicity. This would meet the needs of applications where computational resources are limited, ensuring practical and secure implementations.

1.2. Our Contribution

We focus on a balanced two-party scenario where the size of two sets is equal, namely $\left|X\right|=\left|Y\right|=n$ where the length of each element is l. In particular, the output should be received by the party that does not possess the threshold t, to which we refer as a receiver $\mathcal{R}$.

To our knowledge, developing tPSI using almost exclusively lightweight cryptographic primitives is highly challenging, and this difficulty extends to more general protocols, including over-threshold PSI ($t^{\le }\mathrm{PSI}$) and under-threshold PSI ($t^{>}\mathrm{PSI}$) in which the protocol outputs the intersection only when $t\le$ ${\mathrm{PSI}}^{\mathrm{CA}}$ and $t>$ ${\mathrm{PSI}}^{\mathrm{CA}}$, respectively. In this paper, we concentrate on two-party threshold PSI under the semi-honest model. The main contributions of this work are summarized as follows:

• We propose ${}^{\mathrm{ss}}\mathrm{PMT}$ to compute secret-shared private membership test functionality ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$. In ${}^{\mathrm{ss}}\mathrm{PMT}$, ${}^{\mathrm{ss}}\mathrm{PEQT}$ serves as a building block, which securely computes the secret-shared private equality test functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$.
• We offer a generic tPSI framework where two kinds of tPSI could be efficiently implemented: over-threshold PSI ($t^{\le }\mathrm{PSI}$) and under-threshold PSI ($t^{>}\mathrm{PSI}$). Furthermore, we propose a more lightweight tPSI with limited leakage. We prove the security of all protocols under the semi-honest model.
• We introduce a generic precomputing OT method used to generate instances in tPSI. Experimental results on ${}^{\mathrm{ss}}\mathrm{PEQT}$ and tPSI show that our proposed protocols are highly efficient and computationally friendly.

In addition to our previous work in [36], we have two new contributions. First, we propose another new tPSI protocol named $t_{ll}^{\le }\mathrm{PSI}$, which is entirely based on lightweight cryptographic primitives. Unlike $t^{\le }\mathrm{PSI}$ and $t^{>}\mathrm{PSI}$, the $t_{ll}^{\le }\mathrm{PSI}$ protocol eliminates the need for the comparison circuit for functionality ${\mathcal{F}}_{\gtrless (y_0,x,y_1)}$ by employing our proposed radix complement method. Second, we introduce a generic precomputing OT method where, for any given n, the 1-out-of-n OT protocol primarily involves symmetric operations during online computation. Our work aims to provide a general framework for tPSI with lightweight cryptographic primitives, contributing to the ongoing discourse on enhancing the computational efficiency of such protocols.

2. Preliminaries

In this section, we introduce the notation, cryptographic primitives, and security definitions used in the protocols.

2.1. Notation

We denote the computational and statistical security parameters by $\kappa$ and $\mu$, respectively. A shared variable x is denoted by ${\left[\right[x\left]\right]}_P$, where the subscript $P\in \{\mathcal{S},\mathcal{R}\}$ indicates that which party, $\mathcal{S}$ or $\mathcal{R}$, holds the share. $r{\in }_R{\mathbb{Z}}_q$ denotes that r is uniformly chosen at random from ${\mathbb{Z}}_q$. We let $“\oplus ”$ denote mod-2 addition (also used to denote bitwise XOR operation without causing ambiguity); $x:=y$ denote assigning the value of y to x. We write $X\stackrel{\mathrm{c}}{\equiv }Y$ if two distribution probability ensembles X and Y are computationally indistinguishable.

2.2. Oblivious Transfer

Oblivious transfer is rapidly emerging as a significant primitive in secure computation. We begin with the 1-out-of-2 OT, which involves a sender $\mathcal{S}$ that holds two messages $(m_0,m_1)$ and a receiver $\mathcal{R}$ that holds a choice bit $b\in \{0,1\}$. The protocol guarantees that $\mathcal{R}$ only learns $m_b$ but knows nothing about $m_{1-b}$, while the sender does not gain any knowledge about the choice bit b.

In Figure 1, the functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ provides the receiver $\mathcal{R}$ one message from n messages sent by the sender $\mathcal{S}$. We denote by ${\mathrm{OT}}_n^1$ a specific 1-out-of-n OT construction that securely computes that functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$. Unless otherwise stated, we use “OT” to refer to 1-out-of-2 OT and ${\mathrm{OT}}_n^1$ to denote 1-out-of-n OT protocol. Correlated OT (COT) [38,39] introduces special variants of OT when $n=2$ in ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$. While exhibiting the same essential functionality as OT, COT allows the sender to choose the inputs $(x_0,x_1)$ under the constraint that their XOR equals $\Delta$. This constraint is specifically defined by a correlation function $f_{\Delta }(·)$ where $x_1=f_{\Delta }\left(x_0\right)=x_0+\Delta$.

2.3. Cuckoo Hashing

Cuckoo Hashing is a dictionary data structure designed to enhance performance by allowing an item to be stored in one of several possible locations. As detailed in [40], the fundamental structure of Cuckoo hashing employs multiple hash functions to allocate items into bins. Specifically, using m hash functions $h_i,\cdots ,h_m$, this method maps n items to b bins $\mathcal{B}[1,\cdots ,b]$, where $b=(1+ϵ)n$ ($ϵ$ is a constant and typically $ϵ=1.2$ as an experience parameter [3]) and each bin $\mathcal{B}\left[i\right]$ can contain at most one item.

Typically, there is a stash for items that cannot be placed in the bins, and two hash functions $h_0$ and $h_1$ (i.e., $m=2$) are randomly selected. When inserting an item x, the algorithm first checks if either of the bins $\mathcal{B}\left[h_0\left(x\right)\right]$ or $\mathcal{B}\left[h_1\left(x\right)\right]$ is empty. If an empty bin is available, the item x is placed there, and the algorithm proceeds to the next item. If both bins are occupied, x is inserted into bin $\mathcal{B}\left[h_i\left(x\right)\right]$ where $i{\in }_R\{0,1\}$, evicting the item currently in $\mathcal{B}\left[h_i\left(x\right)\right]$. The evicted item is then subjected to the same insertion process. This cycle continues until either an item is successfully placed without further evictions or a predetermined iteration threshold (indicating a maximum number of evictions) is reached. In cases where the threshold is surpassed, the last evicted item is stored in the stash. This method effectively balances space efficiency with quick item retrieval and insertion operations.

2.4. Secret Sharing

A secret sharing scheme [41] allows a secret s to be divided into several pieces held by different individuals. In this framework, a certain coalition of holders can recover the original secret value s, while any smaller coalition learns nothing about s. In our discussion, we focus on $(n,n)$ secret sharing schemes, where all shares are both necessary and sufficient to reconstruct the secret. We utilize sharing in both ${\mathbb{Z}}_q$ (arithmetic sharing) and ${\mathbb{Z}}_2$ (boolean sharing) to implement it. Arithmetic sharing involves dividing the secret in a manner that relies on modular arithmetic over a finite field, while boolean sharing operates over binary representations.

Linear shares offer significant benefits by supporting parties to perform operations on the addition of two shared values in a non-interactive way. We take full advantage of the linearity of the secret sharing scheme in this work. We suppose there are two parties named $\mathcal{S}$ and $\mathcal{R}$ in a secret sharing scheme. The linearity means that, given arithmetic sharing ${\left[\right[x\left]\right]}_P$ of x and ${\left[\right[y\left]\right]}_P$ of y where $P\in \{\mathcal{S},\mathcal{R}\}$, $z=x+y$ is evaluated by $\mathcal{S}$ and $\mathcal{R}$ adding the shares they already hold. That is, $\mathcal{S}$ computes its output share as ${\left[\right[z\left]\right]}_{\mathcal{S}}={\left[\right[x\left]\right]}_{\mathcal{S}}+{\left[\right[y\left]\right]}_{\mathcal{S}}$, and $\mathcal{R}$ correspondingly computes its output share as ${\left[\right[z\left]\right]}_{\mathcal{R}}={\left[\right[x\left]\right]}_{\mathcal{R}}+{\left[\right[y\left]\right]}_{\mathcal{R}}$. As a consequence, two parties indeed share the secret value z without any additional interaction. This scheme implies the appropriate homomorphic property when the method of sharing is simple additive sharing over a group, such as ${\mathbb{Z}}_q$. Apparently, this kind of linear operation could be executed correctly by several times if the group ${\mathbb{Z}}_q$ is sufficiently large. We would call the property linearity instead of additive homomorphism in a later section.

2.5. Security Definition

Goldreich [42] proposed the formal security definition of secure multiparty protocols by comparing two output distributions, which come from an ideal world and a real world, respectively. In this paper, we focus on the semi-honest model, and the formal security definition is proposed in the following.

We let $f=(f_1,f_2)$ denote a deterministic two-party functionality and $\pi$ a two-party protocol for computing f. Given the security parameter $\kappa$, the input $\left\{x\right\}$ from $P_1$ and $\left\{y\right\}$ from $P_2$, for $i\in \{1,2\}$, the view of $P_i$ during the execution of $\pi$ is denoted as ${\mathrm{view}}_i^{\pi }(x,y,\kappa )=(w,r_i,m_i^1,\cdots ,m_i^t)$, where $w\in \{x,y\}$, $r_i$ represents the randomness used by $P_i$, and $m_i^j$ means the jth message received by $P_i$; the output of $P_i$ is denoted by ${\mathrm{output}}_i^{\pi }(x,y,\kappa )$, and the joint output of the two parties is ${\mathrm{output}}^{\pi }(x,y,\kappa )=({\mathrm{output}}_1^{\pi }(x,y,\kappa ),{\mathrm{output}}_2^{\pi }(x,y,\kappa ))$.

Definition 1.

We say that π securely computes f in semi-honest model if

• The correctness holds:

  $${\mathrm{output}}^{\pi }(x,y,\kappa )\stackrel{\mathrm{c}}{\equiv }{\left\{f(x,y)\right\}}_{x,y,\kappa }.$$
• There exist probabilistic polynomial-time simulator ${\mathrm{Sim}}_1$ and ${\mathrm{Sim}}_2$, such that

  $$\begin{array}{l}{\left\{{\mathrm{Sim}}_1(1^{\kappa },x,f_1(x,y))\right\}}_{x,y,\kappa }\stackrel{\mathrm{c}}{\equiv }{\left\{{\mathrm{view}}_1^{\pi }(x,y,\kappa )\right\}}_{x,y,\kappa },\\ {\left\{{\mathrm{Sim}}_2(1^{\kappa },y,f_2(x,y))\right\}}_{x,y,\kappa }\stackrel{\mathrm{c}}{\equiv }{\left\{{\mathrm{view}}_2^{\pi }(x,y,\kappa )\right\}}_{x,y,\kappa }.\end{array}$$

The construction of simulators ${\mathrm{Sim}}_1$ and ${\mathrm{Sim}}_2$ is crucial for demonstrating the security of the protocol under the chosen corruptions. For $i\in \{1,2\}$, ${\mathrm{Sim}}_i$ represents the simulator for participant $P_i$ that has been corrupted by an adversary. The simulator constructs a simulated view based on the inputs and outputs of the ideal functionality. Specifically, given input x and output $f_1$ from functionality $f=(f_1,f_2)$, simulator ${\mathrm{Sim}}_1$ needs to construct view $\left\{{\mathrm{Sim}}_1(1^{\kappa },x,f_1(x,y))\right\}$. The same is the case with simulator ${\mathrm{Sim}}_2$ and view $\left\{{\mathrm{Sim}}_2(1^{\kappa },y,f_2(x,y))\right\}$. By ensuring that the outputs of the simulators are indistinguishable from the actual views of the corrupt parties, we can argue that the security conditions of the protocol hold.

3. Overview of Our Construction

In this section, together with briefly introducing the main limitations of the current study, we offer two functionalities ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ and ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$ which compute a secret-shared private equality test ${}^{\mathrm{ss}}\mathrm{PEQT}$ and a secret-shared private membership test ${}^{\mathrm{ss}}\mathrm{PMT}$, respectively. In addition, we intuitively present our constructions ${}^{\mathrm{ss}}\mathrm{PEQT}$ and ${}^{\mathrm{ss}}\mathrm{PMT}$.

3.1. One-out-of-n Correlated OT

We first review COT from another point of view and then generalize the definition of COT by extending from ${\mathrm{OT}}_2^1$ to ${\mathrm{OT}}_n^1$ to construct other high-level building blocks for our final protocol. We suppose Alice and Bob, respectively, hold bit a and bit b. Alice chooses $r{\in }_R{\mathbb{Z}}_2$ first and then inputs messages $(m_0,m_1)$ under the correlation function $f_{\Delta }(·)$, where $m_a=-r+1$ and $m_{1-a}=-r$. Bob inputs b as his choice bit and receives $m_b$ from COT. Notably, it holds that $m_{1-a}=-r=r$ when $r\in {\mathbb{Z}}_2$.

An important observation is that, by setting $m_{1-a}=f_{\Delta }\left(m_a\right)={\left(m_a\right)}^{-1}\oplus 1$ in COT, Alice and Bob secretly share the result of $a\oplus b=m_a\oplus m_b$. That is to say, we suppose $c=a\oplus b$; Alice always holds ${\left[\right[c\left]\right]}_0=r$ and Bob learns ${\left[\right[c\left]\right]}_1=x_b$ from COT defined above. It implies that Alice and Bob cooperatively finish a two-out-two ⊕-secret sharing on c. Essentially, the value of c indicates whether the two bits a and b are identical or not.

We let ${\mathrm{COT}}_n^1$ denote one-out-of-n Correlated OT. Alice holds $a\in {\mathbb{Z}}_{2^l}$ and Bob holds $b\in {\mathbb{Z}}_{2^l}$. First of all, Alice now chooses $r{\in }_R{\mathbb{Z}}_p$ (instead of $r{\in }_R{\mathbb{Z}}_2$), and then prepares $n=2^l$ input messages $(m_0,\cdots ,m_{n-1})$ under a correlation function $f_{\Delta ,a}(·)$ in the following way:

• For $i=a$, $m_i=-r+1$;
• For $i\in \left[n\right]$ and $i\ne a$, $m_i=f_{\Delta ,a}(·)=-r$.

Finally, Bob inputs his b as the chosen string in ${\mathrm{OT}}_n^1$ and receives $m_b$ as output. The objective of the correlation function $f_{\Delta ,a}(·)$ above is that, apart from the ath input $x_a$, each input message generated by the sender (i.e., Alice) in ${\mathrm{OT}}_n^1$ is always one same value satisfying $f_{\Delta ,i}(·)$, which is similar to original COT protocol.

Notably, different correlation functions could be defined to restrict the sender’s inputs in ${\mathrm{COT}}_n^1$, though we assign a special but sufficient correlation function used in our ${}^{\mathrm{ss}}\mathrm{PEQT}$ construction. When the context is unambiguous, we abuse the notation and use COT to represent all variants of $f_{\Delta ,i}(·)$ in ${\mathrm{OT}}_2^1$ and ${\mathrm{OT}}_n^1$. In Section 4, we introduce another tailor-made COT construction to obtain better performance, which is not omitted here to keep the content more consistent and coherent.

3.2. Secret-Shared Private Equality Test

We start by introducing the Private Equality Test (PEQT) functionality named ${\mathcal{F}}_{\mathrm{PEQT}}$ (see Figure 2), which is used to determine whether two strings x and y are equal. In a specific PEQT protocol, a sender $\mathcal{S}$ with x as input interacts with a receiver $\mathcal{R}$ holding y as input. At the end of the protocol, $\mathcal{R}$ only learns bit z indicating the comparison result but nothing else, and $\mathcal{S}$ has no outputs. As shown in Figure 2, $\mathcal{R}$ learns $z=1$ if and only if $x=y$; otherwise, $z=0$.

In Figure 3, we introduce the ideal definition of a secret-shared PEQT functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$, which enables two parties $\mathcal{S}$ and $\mathcal{R}$ to learn whether two strings are equal in a secret-sharing way. Notably, Couteau [43] introduced a similar secure equality test protocol that computes shares over ${\mathbb{Z}}_2$ of the equality predicate. Here, we formally define a general secret-shared PEQT functionality where the outputs are shared over ${\mathbb{Z}}_q$. In detail, we define a public parameter q in ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ to indicate the output type of ${\left[\right[z\left]\right]}_P$, i.e., Boolean sharing (when $q=2$) or Arithmetic sharing. That is, the output z in ${\mathcal{F}}_{\mathrm{PEQT}}$ is shared using additive secret sharing scheme to produce ${\left[\right[z\left]\right]}_{\mathcal{S}}=r$ and ${\left[\right[z\left]\right]}_{\mathcal{R}}=r^{\prime }$. Intuitively, the only difference between ${\mathcal{F}}_{\mathrm{PEQT}}$ and ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ lies in that the latter provides two correlated outputs to both $\mathcal{S}$ and $\mathcal{R}$. It may appear to be indirect and unnecessary. However, this distinction becomes more conspicuous in the following.

In ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$, it either satisfies ${\left[\right[z\left]\right]}_{\mathcal{S}}+{\left[\right[z\left]\right]}_{\mathcal{R}}=0$ or ${\left[\right[z\left]\right]}_{\mathcal{S}}+{\left[\right[z\left]\right]}_{\mathcal{R}}=1$ because of the fact that $r^{\prime }\in \{r^{-1},-r\}$. In prior classical works [4,28,31,32], it only holds ${\left[\right[z\left]\right]}_{\mathcal{S}}={\left[\right[z\left]\right]}_{\mathcal{R}}=r$ when $x=y$, or provides $\mathcal{S}$ and $\mathcal{R}$ two different random shares ${\left[\right[z\left]\right]}_{\mathcal{S}},{\left[\right[z\left]\right]}_{\mathcal{R}}{\in }_R{\mathbb{Z}}_{2^l}$ when $x\ne y$. In fact, by introducing Garbled Circuit (GC) or Homomorphic Encryption, it is an easy task to adjust these prior works to securely computing ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$, such that $z=\{0,1\}$ and ${\left[\right[z\left]\right]}_{\mathcal{S}},{\left[\right[z\left]\right]}_{\mathcal{R}},z\in {\mathbb{Z}}_q$. However, without resorting to additional public-key operations, it is not trivial to design the protocol satisfying that the output $z=\{0,1\}$ in PEQT is additive secret shared by $\mathcal{S}$ and $\mathcal{R}$. Therefore, we offer the formal functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ in this paper, and we introduce a simple construction based on COT in the following.

We leverage the capability of COT to provide an efficient solution for this construction. That is, ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ could be instantiated directly by generalized COT defined above when x and y are short strings. We suppose $x,y\in {\mathbb{Z}}_{2^l}$, $\mathcal{S}$ generates $r{\in }_R{\mathbb{Z}}_q$ and prepares $n=2^l$ messages $(m_0,\cdots ,m_{n-1})$ satisfying the following paprameters: For $i=x$, it holds $m_i=r^{-1}$; For $i\in \left[n\right]$ and $i\ne x$, it holds $m_i=-r$. Then, $\mathcal{R}$ acts as receiver with chosen string y in ${\mathrm{OT}}_n^1$, and $\mathcal{S}$ acts as sender with input messages $(m_0,\cdots ,m_{n-1})$ prepared above. After ${\mathrm{OT}}_n^1$, $\mathcal{R}$ obtains $m_y$ and takes $r^{\prime }=m_y$ as a share. It is trivial to verify that general correlated ${\mathrm{OT}}_n^1$ cooperatively executed by $\mathcal{S}$ and $\mathcal{R}$ securely compute ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ such that ${\left[\right[z\left]\right]}_{\mathcal{S}}=r$ and ${\left[\right[z\left]\right]}_{\mathcal{R}}=r^{\prime }$.

This is an illustrative example that is instructive to build the intuition of ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$. When l is large, say, $l>16$, it is almost impractical for $\mathcal{S}$ to prepare $n=2^l$ messages in ${\mathrm{OT}}_n^1$ protocol. To solve this problem, we offer a general construction to compute ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ to support any length of x and y and the actual decomposition of the protocol ${}^{\mathrm{ss}}\mathrm{PEQT}$ in Section 4.

3.3. Secret-Shared Private Membership Test

In Figure 4, the ideal Private Membership Test (PMT) functionality ${\mathcal{F}}_{\mathrm{PMT}}$ is as follows. The sender $\mathcal{S}$ has a set X; meanwhile, the receiver $\mathcal{R}$ has an element y. After ${\mathcal{F}}_{\mathrm{PMT}}$, $\mathcal{R}$ receives bit z indicating whether $y\in X$ or not and $\mathcal{S}$ receives nothing.

Following the study relationship between functionalities ${\mathcal{F}}_{\mathrm{PEQT}}$ and ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ in Figure 2 and Figure 3, we offer the ideal definition of a secret-shared PMT functionality ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$ in Figure 5. The research interest of designing protocols that securely compute functionality ${\mathcal{F}}_{\mathrm{PMT}}$ is similar to ${\mathcal{F}}_{\mathrm{PEQT}}$ and ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$, and now we need the output z in ${\mathcal{F}}_{\mathrm{PMT}}$ to be secretly shared between $\mathcal{S}$ and $\mathcal{R}$. The idea of [4] is that if $y\in X$, then both $\mathcal{S}$ and $\mathcal{R}$ learn the same random value. Otherwise, they learn different random values. Instead of sharing $z=\{0,1\}$, it is $z=\{0,\Delta \}$ that is shared between $\mathcal{S}$ and $\mathcal{R}$ in [4], which is not what we want, though it could transform $\Delta$ to a bit by an additional conversion circuit.

Given functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$, it is trivial to construct a secret-shared PMT (${}^{\mathrm{ss}}\mathrm{PMT}$) protocol (see Figure 6) that securely realizes functionality ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$. We make full use of the linearity property of the secret sharing scheme defined in ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$. Because the outputs of ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ are additively secret-shared between $\mathcal{S}$ and $\mathcal{R}$, the outputs for ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$ can be obtained by summing up these shares without interaction. The correctness of ${}^{\mathrm{ss}}\mathrm{PMT}$ is obvious: ${\left[\right[r\left]\right]}_{\mathcal{S}}+{\left[\right[r\left]\right]}_{\mathcal{R}}=1$ if and only if there exactly exists an element $x_j$ satisfying $y=x_j$ so that $r_j+r_j^{\prime }=1$, which implies the fact that $y\in X$. Otherwise, ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ offers zero-shares to $\mathcal{S}$ and $\mathcal{R}$ in each invocation, and after all invocations and accumulations, it still holds that ${\left[\right[r\left]\right]}_{\mathcal{S}}+{\left[\right[r\left]\right]}_{\mathcal{R}}=0$.

The security of the protocol in Figure 6 boils down to the protocol that computes functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$. In the semi-honest model, the security of ${}^{\mathrm{ss}}\mathrm{PMT}$ is easy to understand: the only new information obtained by $\mathcal{S}$ and $\mathcal{R}$ is secret shares, which leak no information about the parties’ input when invoking ideal functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$.

4. Secrect-Shared Private Equality Test (${}^{\mathrm{ss}}\mathrm{PEQT}$)

In this section, we offer concrete construction ${}^{\mathrm{ss}}\mathrm{PEQT}$ that securely computes ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ in a more general case. ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ can not be instantiated directly by generalized COT when inputs are long strings. This can be circumvented by ${\mathcal{F}}_{\mathrm{OT}}^n$ which transforms the comparison between two long input strings into two shorter ones.

The core idea of the ${}^{\mathrm{ss}}\mathrm{PEQT}$ is to reduce the comparison procedure between two long input strings to two smaller arithmetic shares, which are obtained by sharing the Hamming Distance of the two long binary strings. Notation $d_{\mathrm{H}}(x,y)$ denotes the Hamming Distance between two binary strings (vectors) x and y, here $x,y\in {\{0,1\}}^l$ and $l=2^k$. Apparently, we have $0\le d_{\mathrm{H}}(x,y)\le l$ and the binary representation of $d_{\mathrm{H}}(x,y)$ would be k-bit long at most. So are the arithmetic sharing shares of $d_{\mathrm{H}}(x,y)$, denoted by ${\left[\left[d_{\mathrm{H}}(x,y)\right]\right]}_1$ and ${\left[\left[d_{\mathrm{H}}(x,y)\right]\right]}_2$. That is, instead of focusing on two long inputs x and y themselves, we now just compare two shares that are much shorter than x and y. In addition, the induction procedure between two shares could be invoked again until the length of shares of $d_{\mathrm{H}}(x^{\prime },y^{\prime })$ is short enough. In fact, if we invoke such a reduction procedure just once, we can receive a log-order of magnitude.

Theorem 1.

The ${}^{\mathrm{ss}}\mathrm{PEQT}$ protocol in Figure 7 securely computes functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ (Figure 3) in semi-honest setting, as described in Definition 1, given functionality ${\mathcal{F}}_{\mathrm{OT}}^n$ defined in Figure 1.

Proof. 

We begin by proving correctness. Notably, $l^{\prime }$ is the length of p in binary form. That is to say, it requires at most $l^{\prime }$ binary bits to represent $x_{\mathrm{OUT}}$ or $y_{\mathrm{OUT}}$. In Step 6, it is impossible that $x_{\mathrm{OUT}},y_{\mathrm{OUT}}\in {\mathbb{Z}}_3$, though it also holds that $\lceil \log 3\rceil =2$. If so, we have $p_{now}=3$ and $l_{now}^{\prime }=\lceil \log 3\rceil =2$. We notice that $p_{now}:=l_{old}^{\prime }+1$, and we obtain $l_{old}^{\prime }=2$, which is the time to end the loop and execute Step 6 since $l_{old}^{\prime }$ is not greater than two. In addition, due to the fact that $p_{old}>p_{now}>2$, according to the constraints $l_{old}^{\prime }=2=\lceil \log p_{old}\rceil$ and $p_{old}>p_{now}=3$, we draw a conclusion that there always exists $p_{old}=4$. Therefore, it always holds that $x_{\mathrm{OUT}},y_{\mathrm{OUT}}\in {\mathbb{Z}}_4$ in Step 6 when $l>2$.

In summary, we have ${\mathrm{output}}^{\pi }(x,y,\kappa )\stackrel{\mathrm{c}}{\equiv }{\left\{f(x,y)\right\}}_{x,y,\kappa }$. It concludes the correctness of ${}^{\mathrm{ss}}\mathrm{PEQT}$.

In this context, the protocol ${}^{\mathrm{ss}}\mathrm{PEQT}$ is denoted as $\pi$ for brevity in the proof. According to the specifications of ${}^{\mathrm{ss}}\mathrm{PEQT}$, we define the functions as follows: $f_1(x,y)=r$ and $f_2(x,y)=r^{\prime }$, where r and $r^{\prime }$ represent the outputs computed by the respective parties based on their inputs x and y.

We now construct two simulators, ${\mathrm{Sim}}_{\mathcal{S}}$ and ${\mathrm{Sim}}_{\mathcal{R}}$, designed for simulating the corrupt parties $\mathcal{S}$ and $\mathcal{R}$, respectively. The goal of these simulators is to produce a transcript and a view that is computationally indistinguishable from those generated during a real execution of the protocol. More formally, we express this indistinguishability as follows:

$$\begin{array}{l}{\left\{{\mathrm{Sim}}_{\mathcal{S}}(1^{\kappa },x,f_1(x,y))\right\}}_{x,y,\kappa }\stackrel{\mathrm{c}}{\equiv }{\left\{{\mathrm{view}}_{\mathcal{S}}^{\pi }(x,y,\kappa )\right\}}_{x,y,\kappa },\\ {\left\{{\mathrm{Sim}}_{\mathcal{R}}(1^{\kappa },y,f_2(x,y))\right\}}_{x,y,\kappa }\stackrel{\mathrm{c}}{\equiv }{\left\{{\mathrm{view}}_{\mathcal{R}}^{\pi }(x,y,\kappa )\right\}}_{x,y,\kappa }.\end{array}$$

The protocol ${}^{\mathrm{ss}}\mathrm{PEQT}$ is denoted as symbol $\pi$ for briefness in proof, and according to ${}^{\mathrm{ss}}\mathrm{PEQT}$, we have $f_1(x,y)=r$ and $f_2(x,y)=r^{\prime }$.

Corrupt $\mathcal{S}$. In protocol $\pi$, $\mathcal{S}$ is always working as a sender of ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ in Step 2 and Step 7, where $\mathcal{S}$ prepares $r_i{\in }_R{\mathbb{Z}}_p$ for $i\in \left[l\right]$ and $r{\in }_R{\mathbb{Z}}_q$, respectively. This role is crucial as it ensures that $\mathcal{S}$’s inputs are both random and independent, which is essential for the security of the protocol. Except for $\mathcal{S}$’s input, all messages obtained by $\mathcal{S}$ essentially are generated locally, just reminding that $\mathcal{S}$ gets the output $f_1(x,y)=r$. That is to say, the main transcript in ${\mathrm{view}}_{\mathcal{S}}^{\pi }(x,y,\kappa )$ originates from random messages set $R=\left\{r_i\right|i\in \left[l\right],r_i{\in }_R{\mathbb{Z}}_p\}$. Therefore, it is trivial for ${\mathrm{Sim}}_{\mathcal{S}}$ to generate a simulation of ${\mathrm{view}}_{\mathcal{S}}^{\pi }(x,y,\kappa )$.

Specifically, ${\mathrm{Sim}}_{\mathcal{S}}$ simulates a simulation by choosing $\hat{R}=\left\{{\hat{r}}_i\right|i\in \left[l\right],{\hat{r}}_i{\in }_R{\mathbb{Z}}_p\}$ and preparing $M_1=\left\{(m_0^i,m_1^i)\right|i\in \left[l\right],m_0^i={\hat{r}}_i+x_i,m_1^i={\hat{r}}_i+(x_i\oplus 1)\}$ in Step 2. Then, ${\mathrm{Sim}}_{\mathcal{S}}$ could compute ${\hat{x}}_{\mathrm{OUT}}={\sum }_{i=1}^l{\hat{r}}_i\mathrm{mod}p$. It ensures that the output maintains the necessary randomness and structure consistent with the actual execution of the protocol $\pi$. Here, we omit Step 6 and skip to Step 7 since simulator ${\mathrm{Sim}}_{\mathcal{S}}$ can repeat the reduction process by following the operations described above. Then, ${\mathrm{Sim}}_{\mathcal{S}}$ prepares messages set $M_2=\left\{{\hat{m}}_i\right|i=0,1,2,3\}$, where ${\hat{m}}_{{\hat{x}}_{\mathrm{OUT}}}={\left(f_1(x,y)\right)}^{-1}=r^{-1}$ and ${\hat{m}}_j=-f_1(x,y)$ for $j=i+{\hat{x}}_{\mathrm{OUT}}\mathrm{mod}4$.

Finally, we let $\{M_1,M_2\}$ be the output of ${\mathrm{Sim}}_{\mathcal{S}}(1^{\kappa },x,f_1(x,y))$. This view guarantees that the simulator’s output effectively simulates the real execution. Therefore, we claim that the view generated by ${\mathrm{Sim}}_{\mathcal{S}}$ and the view of corrupt $\mathcal{S}$ in a real protocol are computationally indistinguishable.

Corrupt $\mathcal{R}$. To construct simulator ${\mathrm{Sim}}_{\mathcal{R}}$ that simulates the view of the corrupt $\mathcal{R}$ in the real protocol execution, we start by analyzing $\mathcal{R}$’s view ${\mathrm{view}}_{\mathcal{R}}^{\pi }(x,y,\kappa )$. $\mathcal{R}$ acts as a receiver of ${\mathcal{F}}_{\mathrm{OT}}^n$ in Step 2 and Step 7, with input y and message set $\left\{y_{\mathrm{OUT}}\right\}$ obtained from previous steps. Therefore, ${\mathrm{view}}_{\mathcal{R}}^{\pi }(x,y,\kappa )$ consists of $\mathcal{R}$’s input y, output $f_2(x,y)$, and the random message set $\left\{y_{\mathrm{OUT}}\right\}$. Given the ideal functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$, it is straightforward for ${\mathrm{Sim}}_{\mathcal{R}}$ to construct the simulation of view ${\mathrm{view}}_{\mathcal{R}}^{\pi }(x,y,\kappa )$. For simplicity, we omit the repeated reduction process and present the simulation of Step 2 only once.

${\mathrm{Sim}}_{\mathcal{R}}$ simulates the following views: (1) In Step 2, each time invoking the ideal functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$, ${\mathrm{Sim}}_{\mathcal{R}}$ prepares ${\hat{m}}_{y_i}=m_{y_i}$ and ${\hat{m}}_{1-y_i}=s_i$ where $s_i{\in }_R{\mathbb{Z}}_p$, and then sends messages $M=\{{\hat{m}}_{y_i},{\hat{m}}_{1-y_i}\}$ to ${\mathcal{F}}_{\mathrm{OT}}^n$. ${\mathrm{Sim}}_{\mathcal{R}}$ receives a message set $M_3=\left\{{\hat{m}}_{y_i}\right\}$ from ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ first and then computes ${\hat{y}}_{\mathrm{OUT}}$. (2) In Step 7, the simulator prepares four messages $M_4=\{{\hat{m}}_j\mid j=0,1,2,3\}$, where ${\hat{m}}_{{\hat{y}}_{\mathrm{OUT}}}=f_2(x,y)$ and the others are random values. Then, ${\mathrm{Sim}}_{\mathcal{R}}$ appends the output of ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ to its output.

By combining the two steps described above in sequence, we establish that the output of ${\mathrm{Sim}}_{\mathcal{R}}$ is computationally indistinguishable from that of the real execution. This means that we have ${\left\{{\mathrm{Sim}}_{\mathcal{R}}(1^{\kappa },y,f_2(x,y))\right\}}_{x,y,\kappa }\stackrel{\mathrm{c}}{\equiv }{\left\{{\mathrm{view}}_{\mathcal{R}}^{\pi }(x,y,\kappa )\right\}}_{x,y,\kappa }.$

This completes the construction of two simulators, ${\mathrm{Sim}}_{\mathcal{S}}$ and ${\mathrm{Sim}}_{\mathcal{R}}$. In summary, we prove protocol ${}^{\mathrm{ss}}\mathrm{PEQT}$ secure under the semi-honest model. □

5. Generic Threshold PSI Protocols

Our tPSI protocols benefit from hashing the item of the input set to bins and executing ${}^{\mathrm{ss}}\mathrm{PMT}$ protocol separately on each bin where functionality ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ features a useful linearity property. In Cuckoo hashing, the size of the bins $\mathcal{B}[1,\cdots ,b]$ depends on the number of hash functions as well as on the stash size. The higher the number of hash functions chosen, the more likely the process is to succeed. Therefore, we choose a stash-less cuckoo hashing used in our construction, where cuckoo hashing parameters guarantee that the stash does not exist with sufficiently low probability.

Based on the relationship between the threshold and the intersection cardinality, we first introduce two types of protocols sequentially, i.e., $t^{\le }\mathrm{PSI}$ and $t^{>}\mathrm{PSI}$. Next, we consider lightweight and efficient methods for determining the threshold and the intersection cardinality, which leads us to introduce $t_{ll}^{\le }\mathrm{PSI}$.

5.1. Over-Threshold PSI Protocol: $t^{\le }\mathrm{PSI}$

We first introduce a threshold PSI protocol $t^{\le }\mathrm{PSI}$ which outputs the intersection only when $t\le$ ${\mathrm{PSI}}^{\mathrm{CA}}$. We provide over-threshold PSI functionality in Figure 8 and an ideal comparison functionality with three inputs in Figure 9.

The protocol outlined in Figure 10 involves the following steps: (1) both $\mathcal{S}$ and $\mathcal{R}$ map their respective set into bins before invoking the ${}^{\mathrm{ss}}\mathrm{PMT}$ for each bin; (2) $\mathcal{S}$ and $\mathcal{R}$ aggregate the results from all bins and then compare the cardinality and threshold; (3) $\mathcal{R}$ outputs the intersection based on the comparison. The key insight of our protocol lies in fully utilizing the linearity property of the secret sharing scheme defined in ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$. Given that the outputs of ${\mathcal{F}}_{\mathrm{PEQT}}^{\mathrm{ss},q}$ are additively secret-shared between $\mathcal{S}$ and $\mathcal{R}$, the outputs for ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$ can be obtained by summing these shares without additional interaction. It is crucial to emphasize that $\mathcal{S}$ cannot straightforwardly disclose the shares from each ${}^{\mathrm{ss}}\mathrm{PMT}$ to $\mathcal{R}$, as our protocol mandates that $\mathcal{R}$ should only receive the intersection and proceed with the protocol output if the threshold condition is satisfied. Consequently, $\mathcal{S}$ must relay these shares to $\mathcal{R}$ without gaining insight into the comparison outcome. To maintain security, this process necessitates the implementation of a one-time OT.

It is trivial to securely compare the threshold t and intersection cardinality ${\mathrm{PSI}}^{\mathrm{CA}}$, though ${\mathrm{PSI}}^{\mathrm{CA}}$ is secret-shared between two parties. We provide an ideal comparison functionality with three inputs in Figure 9 to simplify the $t^{\le }\mathrm{PSI}$ protocol. In fact, different secure comparison implementations could be realized. For example, we leverage the capability of the garbled circuit to offer a lightweight solution for this task. It is very efficient to deploy a comparison circuit for short inputs, where $\mathcal{S}$ encodes $c_0$ and t and $\mathcal{R}$ encodes $c_1$ for corresponding input wires. However, we claim that our overall protocol in Figure 10 is not a circuit-based construction because different secure comparison methods could be taken to obtain value z for functionality ${\mathcal{F}}_{\gtrless (y_0,x,y_1)}$.

Theorem 2.

Protocol $t^{\le }\mathrm{PSI}$ in Figure 10 securely computes the functionality in Figure 8 in a semi-honest model, given functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ in Figure 1, ${\mathcal{F}}_{\mathit{PMT}}^{\mathrm{ss},q}$ in Figure 5 and ${\mathcal{F}}_{\gtrless (y_0,x,y_1)}$ in Figure 9.

Proof. 

We omit the detailed security proof of the $t^{\le }\mathrm{PSI}$ in Figure 10 and provide a sketch of the proof.

$\mathcal{S}$ is corrupted. The semi-honest $\mathcal{S}$ receives nothing from the protocol, and the only messages received are random shares from ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$. Therefore, it is trivial to perfectly construct simulator ${\mathrm{Sim}}_S$.

$\mathcal{R}$ is corrupted. The view of $\mathcal{R}$ consists of three kinds of messages: (1) outputs from ${\mathcal{F}}_{\mathrm{PMT}}^{\mathrm{ss},q}$, which are random values and independent of the inputs; (2) one-bit output z from ${\mathcal{F}}_{\gtrless (y_0,x,y_1)}$, which can be obtained from the $t^{\le }\mathrm{PSI}$ protocol. That is, $z=1$ if $\mathcal{R}$ outputs intersection ∅, otherwise $z=0$; (3) the concatenated shares via input message $I^{\prime }$ in the OT phase, which are used to compute the intersection. Given the ideal functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ and the output of the protocol, i.e., intersection $\left\{{\mathcal{B}}_{\mathcal{R}}\left[i\right]\right\}$, simulator ${\mathrm{Sim}}_S$ needs to simulate the entire index set I. ${\mathrm{Sim}}_S$ computes secret shares at the corresponding positions indicating the element in the output that satisfies $r_i+{\hat{r}}_i=1$, while the shares at other positions can be filled with random numbers. If the intersection is ∅, all shares are randomly generated by ${\mathrm{Sim}}_S$. This selective computation ensures that the simulator accurately mimics the behavior of the real protocol. Hence, scripts can be perfectly simulated. □

5.2. Under-Threshold PSI Protocol: $t^{>}\mathrm{PSI}$

The key to constructing the $t^{>}\mathrm{PSI}$ protocol, or rather its distinction from the $t^{\le }\mathrm{PSI}$ protocol, lies in the assessment of the threshold and intersection cardinality. Similar to $t^{\le }\mathrm{PSI}$, we claim that it is trivial to execute $t^{>}\mathrm{PSI}$ without any extra communication or computation. Therefore, we only offer the detailed $t^{\le }\mathrm{PSI}$ protocol corresponding to the functionality and omit the functionality of $t^{>}\mathrm{PSI}$ and its concrete construction. The only difference lies in Step 5a of Figure 10 where $\mathcal{S}$ acts as sender with pair-input $\{0,I\}$. The security proof for this protocol follows a similar approach and is not elaborated upon here.

5.3. Lightweight tPSI with Limited Leakage: $t_{ll}^{\le }\mathrm{PSI}$

Now we consider lightweight and efficient methods for determining the threshold and intersection cardinality. Given that we assume the threshold t is an input of $\mathcal{S}$ and is unknown to $\mathcal{R}$, the cardinality testing approach does not necessarily depend on the secure comparison functionality in Figure 9. Here, we introduce $t_{ll}^{\le }\mathrm{PSI}$ in Figure 11, a lightweight tPSI protocol designed with limited leakage. We begin by defining function $\mathcal{L}$ that describes the leakage in threshold PSI. Without loss of generality, we define the leakage function on the $\mathcal{S}$ side as $\mathcal{L}$ $=|X\cap Y|-t$.

Notably, if $\mathcal{S}$ sends $t^{\prime }=c_0-t$ to $\mathcal{R}$ that computes locally $\delta =c_0-t+c_1$ over the ring ${\mathbb{Z}}_q$ in Step 2 of Figure 11, the protocol does not correctly compare the threshold t with the cardinality of the intersection because $\delta$ must be non-negative in ${\mathbb{Z}}_q$. This limitation reminds us of the need to prevent the wraparound when working over the integers with a certain modulus. To address this issue, a straightforward solution is to perform the calculation over another ring ${\mathbb{Z}}_{q^{\prime }}$ that can represent a negative value in some manner.

We refer to the radix complement that is used to execute arithmetic operations of addition and subtraction within a binary number system. This allows us to expand the representational meanings of elements in ${\mathbb{Z}}_q$. We first represent all elements in ${\mathbb{Z}}_q$ as binary strings and then use the concept of complement to classify these binary strings into positive and negative numbers. In this representation, the most significant bit represents the sign of a number. Given the bit length of q is $\lambda$, we use mapping

$$Q\left(x\right)=\left\{\begin{array}{ccc}x\hfill & \mathrm{if}& 0\le x<2^{\lambda -1}-1\hfill \\ x-2^{\lambda }\hfill & \mathrm{if}& 2^{\lambda -1}\le x<2^{\lambda }-1\hfill \end{array}\right.$$

to recover the original value of the radix complement.

To prevent unexpected overflow when the cardinality of any two sets is large, we assume that parameter $\lambda$ could satisfy constraint $2^{\lambda -1}>n$ instead of $2^{\lambda }>n$. In this approach, $\mathcal{S}$ computes $t^{\prime }$ over the ring ${\mathbb{Z}}_{2^{\lambda }}$, where the range of original numbers spans from $-2^{\lambda -1}$ to $2^{\lambda -1}-1$. $\mathcal{R}$ then obtains $\delta$ in the complement representation. We let $\mathrm{MSB}\left(x\right)$ denote the most significant bit of x. In Step 2 of Figure 11, $\mathcal{R}$ can simply determine $\sigma =\mathrm{MSB}\left(\delta \right)$. Additionally, $\mathcal{R}$ computes $Q\left(\delta \right)$ to learn the original value of $\delta$, which essentially implies $\mathcal{L}$ defined above.

Theorem 3.

The $t_{ll}^{\le }\mathrm{PSI}$ protocol in Figure 11 securely computes the functionality in Figure 8 in a semi-honest model, given leak function $\mathcal{L}$ $=|X\cap Y|-t$, functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$ in Figure 1, and ${\mathcal{F}}_{\mathit{PMT}}^{\mathrm{ss},q}$ in Figure 5.

We omit the detailed security proof of Theorem 3. We start by providing a sketch of the proof when $\mathcal{R}$ is corrupted. Similar to the proof in Therorem 2, it is trivial to perfectly construct simulator ${\mathrm{Sim}}_S$. For simulator ${\mathrm{Sim}}_R$, the most critical aspect is to simulate the situation where $\mathcal{R}$ outputs intersection ∅. Specifically, given leak $\mathcal{L}$, simulator ${\mathrm{Sim}}_S$ calculates $t=\mathcal{L}-c_1$ and sends it to $\mathcal{R}$. Then, ${\mathrm{Sim}}_S$ simply follows the previous simulation process. ${\mathrm{Sim}}_S$ computes secret shares at the corresponding positions indicating $r_i+{\hat{r}}_i=1$, while the shares at other positions are filled with random numbers. If the intersection is ∅, all shares are randomly generated.

6. Complexity Analysis and Comparisons

We provide comparisons to prior classical protocols in

Table 1. Threshold PSI Protocol Comparisons.

Protocol	Public-Key Computation	Communication	Leakage	Functionality	Main Tools
[19]	$O\left(n^2\right)$	$O(ln+\kappa n)$	$|X\cap Y|$	$t^{\le }\mathrm{PSI}$	HE, OT
[20]	$O\left(n\right)$	$O(ln+\kappa n)$	-	$t^{\le }\mathrm{PSI}$ & $t^{>}\mathrm{PSI}$	HE
[21]	$O\left(nl\right)$	$\tilde{O}\left(t^2\right)$	-	$t^{\le }\mathrm{PSI}$	FHE
[23]	$O\left(nl\right)$	$\tilde{O}\left(t\right)$	-	$t^{\le }\mathrm{PSI}$	AHE
[36]	$O(\kappa +l)$	$O\left(ln\log n\right)$	-	$t^{\le }\mathrm{PSI}$ & $t^{>}\mathrm{PSI}$	OT, GC
[24]	$O\left(nl\right)$	$O\left({\kappa }^{2}t\mathrm{poly}\left(\log t\right)\right)$	-	$t^{\le }\mathrm{PSI}$	AHE
Ours *	$O(\kappa +l)$	$O\left(ln\log n\right)$	$|X\cap Y|-t$	$t^{\le }\mathrm{PSI}$, $t^{>}\mathrm{PSI}$ & $t_{ll}^{\le }\mathrm{PSI}$	OT

*: We analyze all the three protocols in Section 5. Note: $\kappa$ denotes the computational security parameter. $\tilde{O}(·)$ hides $\mathrm{poly}$ factors. The complexity in [19,20] refers to ${\mathrm{PSI}}^{\mathrm{CA}}$ phase. The threshold t in [21,23,24] is used to measure the number of different items instead of common ones.

. It should be emphasized that our comparisons are confined to the literature providing two-party computation protocols. The construction of multi-party threshold computation protocols is explicitly excluded from this analysis. This exclusion is based on the observation that threshold definitions in multiparty scenarios exhibit significantly greater complexity and diversity. For instance, in multi-party threshold PSI in [23], parties learn the intersection only if the difference between their respective sets and the intersection does not exceed t, or if the discrepancy between the union of all their sets and the intersection is within t.

7. Implementation and Performance Evaluation

7.1. Generic Precomputing Oblivious Transfer

To accelerate computation time during the online phase in code implementation, as illustrated in Figure 12, we provide a generic precomputing OT that securely computes functionality ${\mathcal{F}}_{\mathrm{OT}}^{\mathrm{n}}$. The idea of precomputing OT could be traced back to Beaver’s work [44] where a precomputing one-out-of-two OT construction is given. We apply this idea to a more general case.

The security of the precomputing method can be reduced to the security of the offline-phase OT, and we omit the proof details here. It is worth noting that $\mathcal{S}$ learns additional information $\delta$, but it only reveals the difference in $\mathcal{R}$ ’s choices between the two phases without disclosing the inputs of either phase, thus maintaining the security of the construction. Furthermore, through the precomputing technique, both parties in the online phase perform simple operations such as XOR or shift, significantly enhancing the lightweight nature of the entire threshold PSI protocol.

7.2. Experimental Performance

In this section, we test the performance of ${}^{\mathrm{ss}}\mathrm{PEQT}$ and tPSI. The experiments were performed on Ubuntu version 20.04 equipped with 3.20 GHz AMD R7-6800H CPU and 16 GB RAM. Our tests refer to the implementation on Github: https://github.com/osu-crypto/libOTe, (accessed on 14 December 2024). We simulate the protocols on a single machine.

In Figure 13, the three subplots exhibit a consistent increase in processing time as the number of the length increases. For the subplot with an element length of $l=128$, the sender has mostly stable data around 10 ms, while the receiver averages around 14 ms with slightly more fluctuation. The total reflects the combined time with fluctuations between 20 ms and 30 ms. For $l=256$, the total averages about 45 ms, maintaining a stable trend but with higher values. For $l=512$, the total average is 70 ms, showing notable fluctuations and higher values. Comparing across subplots, as the element length increases, so do the average values for sender, receiver, and total times, indicating that longer elements require more processing time. Smaller element lengths show less volatility and more stable trends, while longer elements exhibit more pronounced fluctuations. Overall, processing times for both sender and receiver, as well as the total time, are proportional to the element length, suggesting performance decreases with longer elements. This highlights the importance of carefully considering performance implications when handling longer elements.

Table 2. tPSI running time.

Length	Comm. (MB)	Running Time (ms)
		1	2	3	4	5	6	7	8	9	10
$l=128$	2.816	321.92	340.736	388.48	317.184	297.088	296.96	334.72	337.664	397.312	374.272
$l=256$	5.932	628.75	665.5	758.75	619.5	580.25	580	653.75	659.5	776	731
$l=512$	12.264	1257.2	1331	1517.5	1239	1160.7	1160	1307.1	1319	1552.3	1462

illustrates a pronounced rise in execution time as the length of elements escalates, accompanied by a parallel increase in communication volume. For a length of 128, the average execution time is approximately 300 ms. With a length of 256, the average time is around 600 ms, ranging from about 580 ms to 770 ms. When the length extends to 512, the average execution time is roughly 1300 ms. These findings indicate that as the length increases, there is a simultaneous increase in both the average execution time and its variability, providing crucial insights for performance optimization and prediction.

In Figure 14, we present the building blocks and time comparisons of similar protocols. For polynomial interpolation, we referenced open-source code available at https://github.com/openfheorg/openfhe-development, (accessed on 14 December 2024). For the HE algorithm, we utilized an open-source framework hosted on the server, which can be found at https://gitee.com/tianpu/Fast-Polynomial-Interpolation-and-Evaluation, (accessed on 14 December 2024). It is important to note that the timing for HE is provided for reference only, as local testing is likely to take more time. In Figure 14a, we set the set sizes to security parameter $\kappa =256$ and 512. Here, Poly-256 indicates the time required for interpolating the plaintext polynomial on the set $X=\{x_1,\cdots ,x_n\}$, where $n=256$. The same applies to Poly-512, AHE-256, AHE-512, OT-256, and OT-512. Since the OT extension protocol requires a foundational instance of at least 256, the advantages of the OT protocol are not particularly pronounced in this scenario without assistance by the precomputing technique.

However, our lightweight protocols demonstrate increasingly significant time advantages as the size of the set grows, as shown in Figure 14b. The protocols presented in [19,20] do not provide open-sourced code, and the constructions in [21,24] focus on the theoretical optimization of communication complexity but lack a testing procedure. Therefore, we adopt the best conclusions from both types of schemes and provide a comparative analysis of the simulated times. The blue and black curves show a rapid increase, indicating that HE-based protocol becomes less efficient as the input grows. In contrast, the red curve from our construction shows minimal growth, suggesting greater efficiency. Therefore, the protocol derived from lightweight cryptographic primitives is more favorable for scenarios that prioritize speed and resource utilization.

8. Conclusions and Future Work

We propose generic threshold Private Set Intersection (tPSI) construction via Oblivious Transfer (OT) without resorting to the relatively expensive public-key operations. We believe ${}^{\mathrm{ss}}\mathrm{PMT}$ is an important building block in tPSI applications. In future work, we will consider the problem of lightweight design in multi-party tPSI scenarios. Given the significant communication burden on participants posed by OT-extension-based protocols, our subsequent research will focus primarily on balancing the computational and communication loads of the protocol, as well as designing multi-party protocols under different security models.