Towards fair mutual private set intersection with linear complexity

Abstract In this paper, we propose a two‐way oblivious pseudorandom function (m O P R F ) secure in standard model against malicious parties under the decisional composite residuosity and decisional Diffie–Hellman assumptions. Using this two‐way O P R F , we construct an optimistic mutual private set intersection ( P S I ) protocol conserving fairness. In our P S I protocol, fairness is obtained by a semi‐trusted arbiter in the sense that it cannot get access to the private information of the two parties, but we believe that it will follow the protocol. To the best of our knowledge, our P S I protocol is the first fair P S I with linear communication and computation complexities and is proven to be secure in standard model against malicious adversaries under decisional q ‐Diffie–Hellman inversion, decisional composite residuosity, and decisional Diffie–Hellman assumptions. Apart from that, we present a modified version of the O P R F that requires less number of communication rounds. Copyright © 2016 John Wiley & Sons, Ltd.