International Association
for Cryptologic Research

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. due 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 seconds. This makes our protocol the fastest PSI protocol to date with respect to single-threaded performance.

Long-term security, a variant of Universally Composable (UC) security introduced by Müller-Quade and Unruh (TCC ’07, JoC ’10), allows to analyze the security of protocols in a setting where all hardness assumptions no longer hold after the protocol execution has finished. Such a strict notion is highly desirable when properties such as input privacy need to be guaranteed for a long time, e.g. with zero-knowledge proofs for secure electronic voting. Strong impossibility results rule out so-called long-term-revealing setups, e.g. a common reference string (CRS), to achieve long-term security, with known constructions for long-term security requiring hardware assumptions, e.g. signature cards. We circumvent these impossibility results with new techniques, enabling rewinding-based simulation in a way that universal composability is achieved. This allows us to construct a long-term-secure composable commitment scheme in the CRS-hybrid model, which is provably impossible in the notion of Müller-Quade and Unruh. We base our construction on a statistically hiding commitment scheme in the CRS-hybrid model with CCA-like properties. To provide a CCA oracle, we cannot rely on super-polynomial extraction techniques and instead extract the value committed to via rewinding. To this end, we incorporate rewinding-based commitment extraction into the UC framework via a helper in analogy to Canetti, Lin and Pass (FOCS 2010), allowing both adversary and environment to extract statistically hiding commitments. Our new framework provides the first setting in which a commitment scheme that is both statistically hiding and universally composable can be constructed from standard polynomial-time hardness assumptions and a CRS only. We also prove that our CCA oracle is k-robust extractable. This asserts that extraction is possible without rewinding a concurrently executed k-round protocol. Consequently any k-round (standard) UC-secure protocol remains secure in the presence of our helper. Finally, we prove that building long-term-secure oblivious transfer (and thus general two-party computations) from long-term-revealing setups remains impossible in our setting. Still, our long-term-secure commitment scheme suffices for natural applications, such as long-term secure and composable (commit-and-prove) zero-knowledge arguments of knowledge.

Starting with the work of Rivest et al. in 1996, timed assumptions have found many applications in cryptography, building e.g. the foundation of the blockchain technology. They also have been used in the context of classical MPC, e.g. to enable fairness. We follow this line of research to obtain composable general MPC in the plain model. This approach comes with a major advantage regarding environmental friendliness, a property coined by Canetti et al. (FOCS 2013). Informally, this means that our constructions do not “hurt” game-based security properties of protocols that hold against polynomial-time adversaries when executed alone. As an additional property, our constructions can be plugged into any UC-secure protocol without loss of security. Towards proving the security of our constructions, we introduce a variant of the UC security notion that captures timed cryptographic assumptions. Combining standard timed commitment schemes and standard polynomial-time hardness assumptions, we construct a composable commitment scheme in the plain model. As this construction is constant-round and black-box, we obtain the first fully environmentally friendly composable constant-round black-box general MPC protocol in the plain model from standard (timed) assumptions.

Universally composable protocols provide security even in highly complex environments like the Internet. Without setup assumptions, however, UC-secure realizations of cryptographic tasks are impossible. Tamper-proof hardware tokens, e.g. smart cards and USB tokens, can be used for this purpose. Apart from the fact that they are widely available, they are also cheap to manufacture and well understood.Currently considered protocols, however, suffer from two major drawbacks that impede their practical realization:The functionality of the tokens is protocol-specific, i.e. each protocol requires a token functionality tailored to its need.Different protocols cannot reuse the same token even if they require the same functionality from the token, because this would render the protocols insecure in current models of tamper-proof hardware. In this paper we address these problems. First and foremost, we propose formalizations of tamper-proof hardware as an untrusted and global setup assumption. Modeling the token as a global setup naturally allows to reuse the tokens for arbitrary protocols. Concerning a versatile token functionality we choose a simple signature functionality, i.e. the tokens can be instantiated with currently available signature cards. Based on this we present solutions for a large class of cryptographic tasks.