[Resource Topic] 2011/267: Mutual Private Set Intersection with Linear Complexity

Welcome to the resource topic for 2011/267

Mutual Private Set Intersection with Linear Complexity

Authors: Myungsun Kim, Hyung Tae Lee, Jung Hee Cheon


A private set intersection (PSI) protocol allows players to obtain the intersection of their inputs. While in its unilateral version only the client can obtain the intersection, the mutual PSI protocol enables all players to get the desired result. In this work, we construct a mutual PSI protocol that is significantly more efficient than the state-of- the-art in the computation overhead. To the best of our knowledge, our construction is the \emph{first} result with linear computational complexity in the semi-honest model. For that, we come up with an efficient data representation technique, called \emph{prime representation}.

ePrint: https://eprint.iacr.org/2011/267

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .