Private Set Intersection Technology: A Hot Topic in Multi-Party Computing

Privacy Set Intersection (PSI) computation is a specific scenario in secure multi-party computing (MPC) applications. It not only has important theoretical significance but also has great practical usage. As people are more and more focusing on the privacy protection of user data, the research in this area is in line with the increasing desire to benefit from using personal information while maximizing its protection. This article first analyzes and compares 17 PSI protocol schemes based on secure MPC and full homomorphic encryption, including attack model, security model, performance test etc. The results show the EC-ROM/DE-ROM is currently the fastest cryptographic-based public secure PSI protocol. The article also made a comparative analysis with the latest SGX-based PSI protocol. The results show that the SGX-based PSI protocol independently proposed by Baidu Security Lab is 60 times faster than the fastest PSI protocol (EC-ROM and DE-ROM). Moreover, SGX PSI has many other advantages over traditional PSI in terms of security, flexibility and versatility. For example, SGX PSI can adapt to 2 parties, 3 parties and any number of participants, while traditional PSI has a clear gap in participant adaptation.

1- Traditional PSI

The PSI protocol allows two parties to jointly calculate the intersection of their respective data sets. At the end of the operation, one or both parties should get the correct intersection and will not get anything from the other party’s data outside the intersection. Protecting the confidentiality of a data set is a natural need and even a requisite in many scenarios. For example, when the data is user’s address book or the client genome of a genetic diagnosis service, such input data must be protected by cryptography.

It is worth noting that although the PSI protocol is developing very rapidly, and the need for data privacy protection is also growing very quickly, in many current application scenarios, efficient and non-secure protocols are still the mainstream choice. Therefore, understanding the latest development of the PSI protocol and their suitable application scenarios will help greatly in replacing existing non-secure protocols with the PSI protocol.

Use cases of PSI

PSI has many practical use case scenarios. Let’s take a look at two typical ones.

Online Advertising Effectiveness –Online advertising is a major form of advertising. A common way to measure the effectiveness of an ad is to calculate the so-called conversion rate, that is, how many users browsing the ad go on to view the corresponding product page, or eventually purchase the corresponding product or service. A general calculation method is through the intersection of user information (from supply side/publisher) and the user information (from demand side/advertiser) of the corresponding transactions (total amount or volume). At the same time, the user information of both parties needs to be kept private. If non-secure protocol is used, one party’s information will be exposed to the other party, resulting in the data breach of the users and the advertiser or the publisher. But with this scenario in the real world, the protocol used is still non-secure. Basically, while calculating advertising metrics, private data is also seriously threatened.

Finding a Contact — When a user signs up for a new service (such as WeChat, Whatsapp, etc.), it is necessary in most cases to find out which of the user’s existing contacts have registered the same service. This can be done easily by sending the user’s contact data to the service provider, but this essentially exposes user privacy data to the service provider. Therefore, in this scenario, the user’s contact data is used as the input of one party, and all the user information of the service provider is used as the input of the other party to perform the PSI protocol. This protects data outside of the intersection to be leaked to the other party.

It is worth noting that in this particular scenario, the size of the user’s contact set is much smaller than the size of the registered user set. The traditional PSI protocol considers the case where the two sets are of similar sizes. In this scenario, a much larger set will lead to performance bottleneck. Some researchers have been focusing on optimizing this common and practical scenarios and have achieved good results.

2- MesaTEE-based PSI

2.1 Introduction to MesaTEE

MesaTEE is the world’s first universal secure computing platform (USC). It provides the next generation of universal secure computing capabilities for scenarios that are critical for security and confidentiality, enabling sensitive data to be circulated and processed in both off-premise and off-shore scenarios without being compromised or misused. This is especially important today in the world of increasing privacy concerns, making many big data businesses possible. Meanwhile, due to the weakly-centralized architecture of USC/MesaTEE, it also complements the blockchain perfectly, filling the high-performance confidential data processing capability that the blockchain is lacking.

MesaTEE uses three core security technologies, including hybrid memory safety technology (Hybrid Memory Safety and Non-bypassable Security Paradigm), confidential computing technology (e.g. Intel SGX), and trusted computing technology (e.g. TPM). It builds a complete FaaS general-purpose computing framework that provides rigorous and practical privacy and security protection. Compared with traditional cryptography-based multi-party computing or full homomorphic encryption technology, USC/MesaTEE performance is more than 100 times faster, and the programming mode is consistent with traditional programming, easy for programmers to quickly get started. Future versions will also support safety languages ​​such as MesaPy (Memory Safety Python by Baidu Security Lab), further lowering the development barriers. As shown in below Figure 1, MesaTEE redefines the big data business model by providing a trusted and secure isolated execution computing environment. Even if the client and service/platform providers do not fully trust each other, the confidentiality and integrity of the data or model can be effectively protected.

Figure 1: MesaTEE Overview

At the same time, MesaTEE greatly simplifies the Trusted Computing Foundation (TCB), trust boundaries, and trust model complexity, making auditing and verification of the entire software stack practical.

2.2 MesaTEE-based PSI protocol

Figure 2: MesaTEE-based PSI Protocol (with side-channel defense capability)

Current MesaTEE PSI is built on the basis of Intel SGX as the root of trust. Intel SGX provides hardware-trusted and high-protection isolated execution environments (enclaves) embedded in CPUs. Even if an attacker controls the operating system and other privileged software, she still cannot directly access the enclave. Intel SGX also provides remote attestation services, which means that programs in enclave can prove their trustworthy to their third parties. Based on these characteristics, we can build a trusted verifiable PSI server based on SGX. And the PSI participants can use remote attestation to confirm that the PSI server is in a trusted state.

Figure 2 shows a flow chart of the MesaTEE PSI protocol. Although the agreement in the figure is based on two participants, the protocol is compatible and can easily be extended to three or more participants.

Step 1: each PSI participant (two or more parties) communicates with the PSI server, and the server generates a random salt for each participant.

• Participants remotely attest the server to ensure that the server is trusted.
• The server generates random salt through hardware instructions, such as through the rdrand command.

Step 2: The server notifies the participants to let the participants hash the data through the generated salt.

• The server sends the salt to each participant.
• Each participant hashes their data and salt, making it impossible for an attacker to reconstruct the raw data through the hash results.
• Sort the data after the hash. Because of the use of salt, the sorting result still breaks the order relationship between hash and original data, making side channel attacks more difficult or even impossible.

Step 3: Participants transfer the processed data to the server, and ask the server to perform PSI.

• Participants encrypt the sorted random-salt-hash data back to the server and use different transfer keys.
• The server starts PSI after receiving data from each participant. Because it is sorted hash data, it can be streamed and processed parallelly.
• The server put the PSI result in a bit vector. The purpose of this is also to mitigate side channel attacks.

Step 4: The server sends the vector to each participant. The vector obtained by each participant is different.

Step 5: Participants use their own vector to get the final PSI results.

The SGX-based PSI protocol is not only efficient but also highly secure:

1) Leverage strong isolation and trust of SGX;

2) Mitigating the potential side channel attacks of the SGX itself. This makes the protocol more secure than the pure Intel SGX.

2.3 Advantages of MesaTEE PSI

Traditional PSI builds root of trust based on cryptography. Another technique for building a root of trust is to use trusted hardware. For example, Intel’s SGX uses the CPU as a root of trust (see Figure 3). The benefits of using SGX as a root of trust are:

1) The SGX root of trust is smaller and more trustworthy than other roots of trust (such as TPM);

2) SGX provides a secure and trusted execution environment to ensure the confidentiality and integrity of code and data;

3) SGX Trusted Execution Environment can provide near-original processing speed, which greatly reduces the performance overhead of the running time.

Figure 3: Traditional PSI (left) and MesaTEE-based PSI (right)

On top of it, MesaTEE PSI further strengthens the security of the system:

• Ensure the memory safety of running software inside, so that memory safety issues such as use after free, double free, and buffer overflow will not occur.
• MesaTEE adopts the “Non-bypassable Security Paradigm”, which restricts all control flows and data flows through critical checkpoints, significantly lowers the difficulty of auditing and access control, greatly reduces the attack surface, regulates the deployment of access control policies, and makes it possible to implement secure formal verification.
• The programming mode sampling against side channel attacks, makes potential side channel attacks extremely difficult or impossible to complete.

Compared to SGX-based PSI, traditional PSI has many shortcomings:

• For the specified collaborative operation, once the pre-processing ends, the confidential information can only be used by the pre-designated participants. Lack of flexibility to add or remove participants. MesaTEE PSI has no such restrictions.
• For the specified operation mode, once the preprocessing ends, only the previously determined operations can be performed. Lack of flexible ability to add other computations. MesaTEE PSI has no such restrictions.
• Every participant needs to exchange information with each other, which results in performance loss and unavoidable high latency. MesaTEE PSI only needs to communicate with the central trusted node, effectively avoiding these problems.
• The traditional semi-honest PSI does not have an integrity guarantee for the results. MesaTEE’s PSI has natural and efficient integrity protection. From this perspective, the MesaTEE PSI is more secure than this traditional PSI. If you want to extend the traditional PSI to increase the integrity protection (such as the case of expanding to the malicious model), the performance of the entire protocol will be cut by orders of magnitude. MesaTEE can still match this traditional PSI with the strongest security strength.
• The SGX PSI can adapt to 2 parties, 3 parties and any number of different participants. The traditional PSI is obviously incapable in this adaptation.

In addition, MesaTEE PSI has significant advantages in performance compared to traditional PSI solutions.

2.4 Performance advantages of MesaTEE PSI

Figure 4: MesaTEE PSI Performance Advantages

To fully demonstrate the performance advantages of MesaTEE PSI, we compared with some high-performance traditional PSIs. The experiment was built under the LAN environment with transmission speed at 10Gbps. Participants perform single-threaded PSI operations. Participant machine configuration: Intel(R) Xeon(R) CPU E3–1280 v6 @ 3.90GHz and 128MB SGX enclave memory. For multi-threaded situations, the MesaTEE solution makes it easy to add multiple trusted nodes for expansion.

The comparison results are summarized in Figure 4. The horizontal axis of Fig. 4 is the size of the intersection set, and the vertical axis is the time required for the calculation. From the figure we can see that some traditional PSI schemes can only perform PSI operations on small datasets (such as RR [8], SM32, SM64 [9], etc.). Such a scheme can often only process data within a million, and if the amount of data is beyond this range, the entire operation cannot be completed. For EC-ROM and DE-ROM solutions [9], they overcome the bottlenecks of other traditional PSIs and can handle larger data sets (such as more than 10 million data sets). However, compared with MesaTEE PSI, there is still a large performance gap (see Figure 4). From the results in the figure we can see that the MesaTEE PSI is more than 60 times faster than the current fastest traditional PSI solution. Moreover, MesaTEE PSI can do distributed parallel streaming intersection. This performance gap will be further widened. MesaTEE PSI is flexible to intersect from any number of parties, and the cost is basically unchanged. In fact, the more participants, the larger the data set to analyze, the MesaTEE PSI will show a greater performance advantage than the traditional method, and can also solve the complex computing scenarios that traditional PSI can’t.