Paper 2011/267

Mutual Private Set Intersection with Linear Complexity

Myungsun Kim, Hyung Tae Lee, and 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}.

Available format(s)
Publication info
Published elsewhere. To be appeared at WISA 2011
Mutual Private Set IntersectionPrime Representation
Contact author(s)
msunkim @ snu ac kr
2011-12-26: last of 3 revisions
2011-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Myungsun Kim and Hyung Tae Lee and Jung Hee Cheon},
      title = {Mutual Private Set Intersection with Linear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2011/267},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.