Fair Private Set Intersection Using Smart Contracts

A mutual private set intersection protocol (PSI) allows two parties to find the intersection of their private sets without leaking any other information. A mutual PSI protocol achieves complete fairness if a malicious party cannot disadvantage the honest party by using an early abort of the protocol. It has been proved that it is impossible to achieve complete fairness in plain two-party computation, and ensuring fairness needs the inclusion of a trusted third party (TTP). Smart contracts have been used to implement trusted computation in cryptographic protocols. In this paper, we consider fair mutual PSI protocols that use a smart contract as the TTP. We first show that it is impossible to achieve complete fairness by using a smart contract as a TTP in two-party mutual PSI, and consider the (weaker) goal of “fairness with coin compensation”. We design two protocols, \(\varPi \) and \(\varPi ^*\) , that achieve this notion of fairness using a smart contract as the TTP. The protocol \(\varPi \) is a redesign of a fair optimistic PSI protocol (Dong et al., DBSec 2013) that replaces TTP with a smart contract. The protocol \(\varPi ^*\) is a more efficient protocol that replaces some of the zero-knowledge proofs of \(\varPi \) with proof of misbehaviour that enables the smart contract to correctly identify the dishonest party and compensate the honest party with coin. We prove the security and privacy of the protocols in an extension of the ideal/real paradigm for non-monolithic adversaries and provide a proof-of-concept implementation of the smart contract in both protocols in a local Ethereum network. We evaluate the performance of the protocols in terms of gas cost for optimistic and pessimistic executions, compare their performance, and discuss our results and directions for future work.