Practically Efficient Private Set Intersection From Trusted Hardware with Side-Channels

Private set intersection (PSI) is one of the most important privacy-enhancing technologies with applications such as malware and spam detection, recognition of child pornography, contact discovery, or, more recently, contact tracing. In this paper, we investigate how PSI can be constructed and implemented simply and practically efficient. To this end, a natural possibility is the use of trusted execution environments (TEEs), which are commonly used in place of a trusted third party due to their presumed security guarantees. However, this trust is often not warranted: Today’s TEEs like Intel SGX suffer from a number of side-channels that allow the host to learn secrets of a TEE, unless countermeasures are taken. Furthermore, due to the high complexity and closed-source nature, it cannot be ruled out that a TEE is passively corrupted, i.e. leaks secrets to the manufacturer or a government agency such as the NSA. When constructing a protocol using TEEs, such (potential) vulnerabilities need to be accounted for. Otherwise, all security may be lost.

We propose a protocol for two-party PSI whose security holds in a setting where TEEs cannot be fully trusted, e.g. ... mehrdue to the existence of side-channels. In particular, we deal with the possibilities that i) the TEE is completely transparent for the host, except for very simple secure cryptographic operations or ii) that it leaks all secrets to a third party, e.g. the manufacturer. Even in this challenging setting, our protocol is not only very fast, but also conceptually simple, which is an important feature as more complex protocols tend to be implemented with subtle security faults.

To formally capture this setting, we define variants of the ideal functionality for TEEs due to Pass et al. (EUROCRYPT 2017). Using these functionalities, we prove our protocol’s security, which holds under universal composition. To illustrate the usefulness of our model, we sketch other possible applications like (randomized) oblivious transfer or private computation of the Hamming distance.

Our PSI implementation, which uses Intel SGX as TEE, computes the intersection between two sets with 2$^{24}$ 128-bit elements in 7.3 s. This makes our protocol the fastest PSI protocol to date with respect to single-threaded performance.