Secure and Scalable Circuit-based Protocol for Multi-Party Private Set Intersection

Our protocols are built upon the foundation of the two-party circuit-based PSI protocols proposed by [9]. One notable difference is that, in order to overcome the challenges of complex interactions and scalability in the multi-party setting, our protocol adopts a generic two-party secure computation protocol. As a result, prior to conducting circuit computations, the private inputs of the parties need to be securely distributed between the two parties engaged in the secure computation process. These two parties then reconstruct the items and perform secure computation of multi-party PSI (mPSI) within the circuit. The construction of our protocols uses generic secure multi-party computation (MPC) protocols, such as Yao’s garbled-circuit protocol and the GMW protocol, to evaluate boolean circuits that compute the desired functionality. By relying on these established MPC protocols, which possess proven security properties, we can focus on designing circuits that effectively implement the desired functionality. In our study, we consider the multi-party setting involving $m$ parties denoted as $P_{1},...,P_{m}$. Each party possesses an input set consisting of $n$ items, which are represented using $\sigma$ bits.

In our first protocol, namely multi-party Bitwise-AND (mBWA), the input sets are represented as bit-vectors of length $2^{\sigma}$. The protocol incorporates a secret sharing scheme, where each party securely distributes their respective bit-vectors to two designated parties, denoted as $P_{1}$ and $P_{2}$. Subsequently, $P_{1}$ and $P_{2}$ reconstruct the bit-vectors within the circuit, enabling the computation of the intersection by performing bit-wise AND operations on the corresponding bit-vectors.

It is important to highlight that the practical applicability of this protocol is limited to scenarios involving smaller universes. The exponential growth of AND gates within the circuit imposes constraints on its scalability when dealing with larger datasets.

Our second protocol, multi-party Sort-Compare-Shuffle (mSCS), follows the Sort-Compare-Shuffle (SCS) paradigm while extending it to the multi-party setting. In this protocol, each party independently performs a local sorting operation on their respective input sets. The sorted sets are then distributed among the designated parties, $P_{1}$ and $P_{2}$, ensuring that the order of the secret shares aligns with the order of the items in the sorted sets.

Upon distribution, $P_{1}$ and $P_{2}$ reconstruct the sets within the circuit and merge them securely using a $k$-bitonic sorting network based on the $k$-Bitonic sort algorithm [7]. The intersection of the sets can be subsequently determined by identifying the elements that occur $m$ times consecutively in the merged list. This identification process involves comparing adjacent elements. Finally, before revealing the sorted intersection, a shuffling procedure is applied to conceal the positional information of the items, thus preserving privacy and confidentiality.

Our research is also motivated by the work presented in [13], which introduced a method for comparing items mapped to each bin. In light of this, we propose a novel approach that employs simple hashing scheme for each party to distribute their elements into distinct bins. This approach aims to reduce communication overhead by utilizing multi-party circuit-based PSI protocols to compare the elements within each bin. Through our exploration, we have discovered substantial advantages in employing individual instances of the aforementioned protocol within each bin, as opposed to directly utilizing a single, large circuit for computation. These advantages extend beyond the realm of communication overhead and also encompass the facilitation of parallel computation. By leveraging this approach, our protocols exhibit improved efficiency and scalability, making them well-suited for practical deployment in multi-party settings.

The problem of PSI has always been a hot issue in the field of MPC. We focus on the discussion of the state-of-the-art of semi-honest PSI protocols and simply classify previous works into two-party PSI and multi-party PSI.

In summary, in this paper we present the following contributions:

• •

  We provide the first multi-party circuit-based PSI achieving $O(mnlog^{2}(mn))$ asymptotic communication overhead. Our protocol is a natural generalization of the two-party circuit-based PSI protocol, which simplifies the complexity of multi-party interactions and can be easily expanded.

• •

  We integrate simple hashing scheme into our multi-party circuit-based protocols. By using the permutation-based hashing function, the elements can be represented in the form of shorter bits in the bins. Grouping data into bins results in a reduction in circuit size and enables parallel computation. This approach achieves the goal of simultaneously decreasing both communication and time overheads.

There are $m$ parties, which we denote as $P_{1}$, …, $P_{m}$, where $P_{1}$ and $P_{2}$ are typically the two parties for security computation. Each of these parties is in possession of respective input sets, $S_{1},S_{2},\dots,S_{m}$, each of which contains $n$ items represented by $\sigma$ bits. It is assumed that $P_{1}$ and $P_{2}$ agree on a circuit $C$ that receives the secret shares of input sets and computes the intersection of $\hat{n}$ elements. They also agree on a symmetric function $f$ and can compute $f(S_{1}\cap S_{2}\cap...\cap S_{m})$ securely. We denote the computational and statistical security parameters by $\kappa$ and $\lambda$. We use $\gamma$ to denote a parameter that determines the probability of hashing failure, which is employed in optimization schemes. We use $S_{i}[j]$ to denote the $j$-th item in the set $S_{i}$. We also denote the set $\{1,...,c\}$ as $[c]$.

In this work, similar to most protocols for private set intersection, we focus on the semi-honest model, also known as the honest-but-curious model, which assumes that all parties will follow the protocol, but adversaries may attempt to extract as much information as possible from the protocol execution. This is different from malicious adversary model, where adversaries can deviate from the protocol steps arbitrarily. While protocols designed for malicious adversaries offer more security, they tend to be less efficient than those designed for the semi-honest setting. In most scenarios, semi-honest security is sufficient, as it is currently difficult for adversaries to modify software with attestation or business restrictions. However, for most recent optimization of circuit-based PSI protocols that rely on Cuckoo hashing, it is still difficult to ensure that such operation of hashing is secure and correct.

The SCS protocol of [9] is a unique circuit-based PSI protocol that can be easily modified to provide security against malicious adversaries by expanding the circuit to verify that the elements are sorted, while maintaining an overall complexity of $O(nlogn)$. It is worth noting that this advantage is also present in our protocol.

In contemporary MPC research, there exist two primary methods for the secure computation of boolean circuits: Yao’s garbled circuit (GC) protocol [20] and the GMW protocol [8].

Yao’s garbled circuit protocol presents a constant round complexity and implements the free XOR gates technique [12]. Through the optimization techniques developed in [21], the protocol requires at least two ciphertext transmissions to evaluate an AND gate. Similarly, the GMW protocol also implements the free XOR technique and necessitates two ciphertext transmissions to evaluate each AND gate using OT extension [2]. However, the GMW protocol offers an additional benefit in the form of its ability to perform symmetric cryptographic computations in advance during the pre-computation phase, thereby improving the efficiency of the online phase.

The main advantage of generic protocols is that it can easily extend the functionality of the protocol without having to change the security of the protocol. As such, we use generic secure two-party computation protocol to implement our protocols.

In cryptography, an $(n,t)$-secret sharing scheme has been proposed for distributing a secret $s$ among $n$ parties in such a way that any $t+1$ parties can collectively reconstruct the secret $s$ from their shares, while preventing any collusion of $t$ parties from learning any information about $s$ [18, 3]. This scheme provides a secure and efficient way to distribute secret information among multiple parties without compromising its confidentiality.

In this context, our protocols employ an additive $(n,n-1)$-secret sharing scheme. In our protocols, all parties have to distribute their input sets among two designated parties, $P_{1}$ and $P_{2}$. This distribution ensures that neither $P_{1}$ nor $P_{2}$ can obtain any information about the input sets of other parties except their own data. During the computation phase of the circuit, $P_{1}$ and $P_{2}$ reconstruct the inputs of the parties in the circuit and calculate the intersection of the input sets.

The use of the additive secret sharing scheme in our protocols provides an additional layer of security to the distribution of secret information among multiple parties. The data pre-processing phase ensures that the input sets of parties are kept confidential, and the computation phase guarantees that the secret information is reconstructed securely without revealing any information to unauthorized parties. This approach is beneficial for applications that require the distribution of confidential information among multiple parties, such as secure multi-party computation, privacy-preserving data analysis, and secure cloud computing.

We have incorporated a hashing scheme in our protocols to optimize them. The literature on hashing schemes is extensive and covers a range of methods for handling collisions, complexities associated with insertion, deletion, and look-up operations, as well as utilization of storage space. Previous works such as [15, 13, 5] have used hashing to improve the number of comparisons performed in Private Set Intersection (PSI) protocols. Similarly, our protocols allow the use of simple hashing schemes to split the computation by mapping input items to bins.

The simple hashing scheme typically utilizes a table $T$ containing $\beta$ bins. We make the assumption that the number of bins $\beta$ is a power of 2. In cases where $\beta$ is not a power of 2, [1] proposes a method to handle this situation. Using a hash function $H$ which maps an element $e$ to an address $a=H(e)$ within the range $[0,\beta-1]$, the element $e$ is then placed into the corresponding bin $T[a]$. The simple hashing approach allows for multiple elements to be stored in each bin, with the maximum number of elements that can be stored in each bin depending on the total number of elements and the number of bins. This problem has been analyzed in detail in [16], which showed that when randomly mapping $n$ items to $n$ bins using $H$, the most populated bin would have at most $\frac{lnn}{lnlnn}(1+o(1))$ items with high probability.

In summary, by adopting simple hashing scheme, our protocols allow for efficient computation by reducing the number of comparisons while enabling parallel computation.

When dividing elements into bins, it is possible to reduce the bit-length of stored items through permutation-based hashing, a technique introduced in prior literature [1, 13]. In this work, we apply permutation-based hashing to improve the memory usage of our simple hashing scheme. Specifically, by utilizing permutation-based hashing, the elements stored in bins can be represented using fewer bits, resulting in a reduction of the number of gates required during the circuit computation stage. This reduction can lead to significant efficiency improvements in terms of communication costs and computation time. Notably, the permutation-based hashing technique can be applied in all hashing-based privacy-preserving set intersection (PSI) protocols, including the one proposed in this study.

In general, a traditional hash function $h:\{0,1\}^{\sigma}\rightarrow\{0,1\}^{log\beta}$ maps an element $x$ to bin $h(x)$, where $|x|$ represents the bit-length of $x$. We notice that the bin index $h(x)$ is able to carry $log\beta$ bits of information. So, it is possible to reduce the information stored in the bins from $\sigma$ to $\sigma-log\beta$, which means that secure computations are done on elements with smaller representations. If we choose the hash function carefully, we can realize that if two items have the same representation stored in the bin and are in the same bin, they must be equal. Permutation-based hashing provides uses a Feistel-style trick to implement this purpose.

In details, we split the bit representation of an input item $x$ into $x_{L}||x_{R}$, where $x_{L}$ has $log\beta$ bit-length, which is equal to the big-length of the bin index in the hash table, and $|x_{R}|$ has $\sigma-log\beta$ bit-length. Then we define $f()$ be a random function whose range is $[0,\beta-1]$, represented by $log\beta$ bits. We define $h(x)=x_{L}\oplus f(x_{R})$. Then the input item $x$ is stored in the bin $x_{L}\oplus f(x_{R})$, and the value stored in the bin is $x_{R}$, which is reduced to $\sigma-log\beta$ bit-length. We observe that if two elements $x$ and $y$ are stored in the same bin, and the stored values $x_{R}$ and $y_{R}$ are also the same, then that means $f(x_{R})=f(y_{R})$. Since the bin $h(x)=h(y)$, then $x_{L}=y_{L}$. So, we can conclude that $x=y$. Note that if $|x|$ is not much longer than $log\beta$, the overhead will have a great improvement.

The first circuit-based PSI protocol was introduced in [9]. Prior to performing computations in the circuit, the parties are required to sort their input sets and input them to the circuit. In the protocol proposed in [13], the parties must also utilize hash schemes, such as Cuckoo hashing and simple hashing, to map their input items into bins. Generally, these circuit-based PSI protocols necessitate that the parties conduct operations (e.g., reordering and hashing) on their input sets beforehand.

It was shown in [6] that if the parties map their input items into bins, then they only need to compare the items that stored in the same bins. Nevertheless, the number of items mapped into each bin may reveal information about their input sets. Thus, to ensure that this information is concealed from other parties, it is necessary to pad all bins with random dummy values, without revealing the number of items in each bin. It is assumed that the parties agree on the maximum number of items that can be mapped into a bin, denoted as $B$. Following the mapping of all items into bins, the parties must pad each bin with dummy values until it contains $B$ items. If the two parties compare the items in the bins using pairwise comparisons, the total number of the comparisons will reduce from $O(n^{2})$ to $O(\beta\cdot B^{2})$, where $n$ is the number of items in each input set and $\beta$ is the number of the bins.

In our proposed protocols, we combine simple hashing scheme with the Sort-Compare-Shuffle protocol to compare items in each bin. By carefully selecting the number of bins $\beta$ and the upper bound $B$ for the maximum number of items that can be mapped to a bin, this approach can offer computational and communicational advantages over previous schemes. In this scenario, the parties need to map their input items into bins using a hash function and locally sort the items in each bin for subsequent merge sorting.

Referring to the first protocol for distributing and reconstructing the input sets, we assume that the input set of each participant has already been reconstructed in the circuit. Following this, participants $P_{1}$ and $P_{2}$ are required to implement an oblivious merging network to sort the union of the input sets, making use of the fact that the input sets are already sorted. The term ”oblivious” implies that regardless of the order of the input elements, the circuit remains fixed, i.e., the sequence of comparison between elements is predetermined. In order to merge the $m$ sorted lists into a fully sorted sequence, a merge-sort network is designed based on the $k$-Bitonic sort algorithm [7]. The resulting number of comparisons is $O(mnlog^{2}(mn))$.

The concatenation of a sequence sorted in ascending order with a sequence sorted in descending order yields a bitonic sequence, which can be obtained after local sorting. In the context of sorting networks, the 2-Sorter module serves as a fundamental component. As shown in Figure 4, a design for 2-Sorter is presented in [9], which comprises a $\sigma$-bits Comparator and a $\sigma$-bits CondSwap, resulting in a requirement of only $2\sigma$ non-free gates to compare two $\sigma$-bits elements. We can recursively utilize the Batcher’s bitonic sorting network, as described [9], in a tree-like manner. However, the resulting high complexity caused by excessive redundant computations is not acceptable.

In our work, we introduce a $k$-Bitonic sort algorithm, denoted as Algorithm 1, which is a generalized version of the bitonic sort introduced by Batcher in 1968. We assume that $k=\lceil\frac{m}{2}\rceil$ to indicate that there are $k$ bitonic sequences in total in the case of $m$ parties. It is important to note that $k$-Bitonic sort reduces to Batcher’s bitonic sort when $k$ is equal to 1. Specifically, the code executed until the 10th line of the algorithm is identical to Batcher’s bitonic sorting algorithm.

We assume that the input $V=V[0:N-1]$ is a $k$-bitonic sequence, where $N=mn$ is the length of the sequence, and the ouput $U[0:N-1]$ is an incremental sequence. By performing odd-even splitting on a sequence, the resulting sub-sequences can still exhibit the characteristic of $k$-bitonic sequence. Thus, the $k$-bitonic sort algorithm KBS($V,N,U$) is a recursive procedure. We denote $Q({a_{0},a_{1},...,a_{n-1}})$ is the permutation of the sequence $A=\{a_{0},a_{1},...,a_{n-1}\}$ ordered in an ascending fashion. The fundamental operation in the execution process of the KBS algorithm is to compare and exchange two elements.

Based on the complexity analysis of the recursive function, we deduce that the time complexity of the KBS algorithm is $O(mnlog^{2}(mn))$. To provide a more detailed analysis, we use the recurrence formula to work out the number of comparisons performed by the merge sort circuit. The resulting expression is $\frac{mn}{4}log(mn)log(\frac{mn}{2})+mn-1$. Thus, we can construct a circuit that merges $m$ sequences of $n$ elements, each consisting of $\sigma$ bits, into a single sorted sequence of $mn$ elements. The circuit requires $2\sigma(\frac{mn}{4}log(mn)log(\frac{mn}{2})+mn-1)$ non-free gates.

After sorting the $mn$ elements in a list, the next step in the secure set intersection protocol involves comparing adjacent $m$ elements to identify the elements in the intersection.

In this phase, we employ a duplicate-selection circuit to identify all elements in the intersection. Specifically, the circuit filters out the elements in the intersection by computing whether a consecutive set of $m$ elements are all equal. If they are equal, it outputs the value of the element; otherwise, it outputs a dummy value. Our investigation focused on exploring the properties of sorted lists and their relevance to the protocol at hand. We aimed to gain a deeper understanding of the characteristics that could be leveraged to optimize the execution of the protocol. After thorough analysis, we identified two key properties that are particularly significant:

Upon figuring out the intersection, the matched $n$ elements (and dummy values) are arranged in a specific positional order in the circuit. This ordering has the potential to compromise the confidentiality of parties’ input sets. However, if we only need to perform subsequent computations based on the elements in the intersection, this step can be omitted. Therefore, to preserve privacy, it is essential to shuffle the elements before their disclosure. The shuffling process is crucial to ensuring privacy in secure multi-party computation, especially when dealing with sensitive data. In the absence of a proper shuffling algorithm, the positional information of the elements in the circuit may allow an adversary to deduce the corresponding parties’ input sets. Specific examples can be obtained in [9]. In line with [9], we also utilize an oblivious shuffling network, which is constructed using $O(mnlog(mn))$ non-free gates, to implement the random permutation needed to obliterate the positional information.

An oblivious shuffling network employs a set of gates that do not reveal any information about the input values while transforming the input sequence into an output sequence. The network achieves this by iteratively swapping pairs of elements in the sequence according to a predetermined permutation. Since the permutation is randomly generated, the resulting sequence is uniformly distributed over all possible permutations. Consequently, the positional order of the elements in the circuit is destroyed, and parties’ input sets remain private.

The computational complexity of the shuffling process is a critical consideration, as it determines the scalability of the multi-party computation protocol. The $O(mnlog(mn))$ complexity of the oblivious shuffling network used in this protocol can be expensive for large inputs. Nonetheless, it remains a practical solution for most use cases, and ongoing research aims to develop more efficient shuffling algorithms.

As shown in Figure 7, each participant follows simple hashing scheme, where each bin can store more than one element, using a public permutation-based hash function $h$ to hash elements from the input set to their respective bins. We assume that each participant possesses $\beta$ bins, with each bin having a capacity of $B$, including both dummy values and actual elements.

Once the elements are hashed into the bins, the generic circuit-based multi-party protocol is executed in each corresponding bin to perform the set intersection operation. The circuits in each bin are independent of each other, allowing for simple and efficient parallel computation.

In our proposed scheme, each party employs simple hash scheme to map their respective input set into multiple bins. In simple hash scheme, if the number of items mapped to a bin exceeds its capacity, the use of bins with a constant size may result in hashing failures.

When hashing fails, the party responsible for the hashing operation has two possible options. The first option is to ignore the unmapped element and remove it from its input set, which may result in an incorrect final computed result, albeit rare. The second option is to attempt to use an alternative hash function to remap the unmapped element. However, this approach requires informing the other parties involved of the use of the new hash function, which introduces a potential privacy leak. For instance, the other party could infer whether the input set $S$ of the first party could be equal to a set $S^{\prime}$ by checking if $S^{\prime}$ did not encounter hash failure, indicating that $S^{\prime}$ and $S$ are not identical. Thus, it is essential to carefully set the capacity of each bin to minimize the probability of hashing failures to be negligibly small. However, a large bin capacity may inevitably result in an excessive number of dummy values in each bucket, leading to a reduction in the overall efficiency of the protocol.

The most desirable scenario is when all elements are uniformly mapped to bins and each bin is fully occupied. In this case, we denote the ideal capacity of each bin is $b=\frac{n}{\beta}$, where $n$ is the total number of elements and $\beta$ is the number of bins. Next, the actual capacity $B$ should be as close as possible to $b$ while maintaining a negligible probability of hashing failures. We assume that $h$ is a random uniform hash function, and $X_{i},i\in[n]$ are independent random variables. From the perspective of a fixed party, observing a fixed bin, $X_{i}=1$ means that the $i$-th element is mapped to the bin by $h$, otherwise $X_{i}=0$. Then, $X=\sum_{i=1}^{n}X_{i}$ represents the number of the participant’s elements mapped to that bin. Thus, we can obtain $E(X)=b$.

In probability theory, Chernoff Bound is a statistical concept that helps us understand the probability of the sum of independent random variables deviating from its expected value. Thus, according to Chernoff Bound, we can obtain that for any $\delta\in[0,1]$, it holds that:

We define the event $A_{i}$ as $X\geq(1+\delta)b$, which represents the occurrence of hashing failure in a particular bin. Using the Boolean inequality $P(\bigcup_{i}A_{i})\leq\sum_{i}P(A_{i})$, given that there are $m$ parties and each party has $\beta$ bins, the probability of the whole protocol experiencing hashing failure satisfies:

Therefore, if $B$ is set to $(1+\delta)b$ and the right-hand side of the inequality is a negligible function, it suffices to prove that the proposed scheme will result in negligible probability of hashing failures. So, if we want to keep the overall failure probability less than $2^{-\gamma}$:

We can get:

and

In fact, we can set $\delta=1$ and $b=\log^{2}n$ to make the probability of overall hashing failure a negligible function of the input set size $n$. If we consider the mSCS protocol and use it to handle the elements in each bin, we need to perform $O(mb\log^{2}(mb))$ comparisons between elements. Thus, the total number of comparisons for $\beta$ bins is $O(\beta mb\log^{2}(mb))$, which can be simplified as $O(mnlog^{2}(mlogn))$.

We assume that all the elements can be represented using $\sigma$ bits. By using permutation-based hashing function to map elements to corresponding bins, the elements stored in the bin can be represented with shorter bits. Specifically, with $\beta$ bins, the corresponding element can be stored using $l=\sigma-log\beta$ bits, and it can be guaranteed that if two elements have the same value stored in the same bin, then these two elements must be equal. Therefore, the asymptotic communication complexity of our final protocol reduces from $O(\sigma mnlog^{2}(mn))$ to $O(lmnlog^{2}(mlogn))$. By summing up, simplifying, and scaling down the number of non-free gates across the three stages, we obtain an upper bound on the number of non-free gates required for computations within each bin:

In our proposed optimization scheme, each bin stores $B=(1+\delta)b$ elements, and each element has a length of $\sigma-\log\beta$ bits. Therefore, we can obtain an upper bound on the number of non-free gates for each bin required after incorporating the hashing scheme using the above equation (with $n=(1+\delta)b$ and $\sigma$ is set to $\sigma-\log\beta$). That is, for given $m$, $n$, $\sigma$, and $\gamma$, we can minimize the number of non-free gates required by setting the value of $\delta$ and $b$.

Table 1 presents the results of a experimental evaluation conducted to assess the performance of the plain mSCS protocol in computing the intersection of large-scale input sets. Our findings reveal that the plain mSCS protocol incurs a significantly higher communication overhead compared to a custom multi-party private set intersection protocol, such as the one proposed by [11]. Specifically, the plain mSCS protocol necessitates between 100 and 1000 times more communication than [11], which discloses the intersection in plaintext to the participating parties. Despite the increased communication overhead, the results obtained highlight the feasibility of employing the plain mSCS protocol for privacy-preserving set intersection in large-scale scenarios. Furthermore, the protocol demonstrates potential utility in non-real-time applications where private set intersection serves as a submodule.

Table 2 presents a comprehensive analysis of the minimum numbers of non-free gates required for each element in the Hashing-mSCS protocol, with $\delta$ and $b$ values set at $m=3$ and $\gamma=40$. The number of non-free gates serves as a crucial metric for evaluating the protocol’s complexity, as it significantly influences the performance of circuit-based Multi-Party Computation protocols. Notably, the number of non-free gates remains independent of the specific implementation details of the MPC framework, distinguishing it from other benchmarks such as communication overhead or runtime.

By conducting a meticulous analysis and comparing the theoretical computational results of our proposed Hashing-mSCS protocol with the empirical findings from the naive mSCS protocol, we have discovered a substantial reduction of approximately 20% in communication overhead when employing the Hashing-mSCS protocol. This reduction can be attributed to the utilization of hashing techniques, which partition the elements into distinct bins. Importantly, each bin operates independently, and the intersection of computation results within each bin forms a subset of the final intersection. As a consequence, the Hashing-mSCS protocol facilitates parallel computation, effectively mitigating the challenge of excessive memory consumption associated with large-scale circuits.

This improvement in communication overhead underscores the advantages offered by the Hashing-mSCS protocol in terms of efficiency and scalability. The parallel computation capability, achieved through bin-based partitioning and independent processing, enables more efficient resource utilization. By avoiding the need for storing and processing the entire intersection in a single circuit, the protocol alleviates the burden on memory resources, making it particularly well-suited for scenarios involving large circuit scales. These findings contribute to the growing body of knowledge in the field of secure multi-party computation, paving the way for enhanced privacy-preserving protocols in large-scale settings.