Paper 2020/620

Private Identity Agreement for Private Set Functionalities

Ben Kreuter, Sarvar Patel, and Ben Terner


Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke on a support functionality to agree on the primary keys to represent their users. This paper studies a secure approach to agreeing on primary keys. We introduce and realize a functionality that computes a common set of identifiers based on incomplete information held by two parties, which we refer to as private identity agreement. We explain the subtleties in designing such a functionality that arise from privacy requirements when intending to compose securely with PSI protocols. We also argue that the cost of invoking this functionality can be amortized over a large number of PSI sessions, and that for applications that require many repeated PSI executions, this represents an improvement over a PSI protocol that directly uses incomplete or fuzzy matches.

Available format(s)
Publication info
Preprint. MINOR revision.
private set interectionprivate identity agreementgarbled circuits
Contact author(s)
benkreuter @ google com
bterner @ cs ucsb edu
2020-05-26: received
Short URL
Creative Commons Attribution


      author = {Ben Kreuter and Sarvar Patel and Ben Terner},
      title = {Private Identity Agreement for Private Set Functionalities},
      howpublished = {Cryptology ePrint Archive, Paper 2020/620},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.