Provably Secure Private Set Intersection With Constant Communication Complexity

Provably Secure Private Set Intersection With Constant Communication Complexity

Sumit Kumar Debnath (National Institute of Technology, Jamshedpur, India)
Copyright: © 2019 |Pages: 26
DOI: 10.4018/IJCWT.2019040104


Electronic information is increasingly shared among unreliable entities. In this context, one interesting problem involves two parties that secretly want to determine an intersection of their respective private data sets while none of them wish to disclose the whole set to the other. One can adopt a Private Set Intersection (PSI) protocol to address this problem preserving the associated security and privacy issues. In this article, the authors present the first PSI protocol that incurs constant (p(k)) communication complexity with linear computation overhead and is fast even for the case of large input sets, where p(k) is a polynomial in security parameter k. Security of this scheme is proven in the standard model against semi-honest entities. The authors combine somewhere statistically binding (SSB) hash function with indistinguishability obfuscation (iO) and space-efficient probabilistic data structure Bloom filter to design the scheme.
Article Preview

1. Introduction

In our everyday life, sharing of electronic information among mutually distrustful parties increases rapidly. Naturally, this raises important privacy concerns with respect to the disclosure and long-term safety of sensitive content. In this area, an interesting problem is to compute intersection of private data sets of two mutually dishonest entities. A few relevant applications are presented below:

  • 1.

    Government tax authority wants to detect whether any suspected tax evaders have accounts with a certain foreign bank and, if so, obtain their account records. The bank’s domicile forbids wholesale disclosure of account holders while the tax authority cannot disclose its list of suspects;

  • 2.

    Two national law enforcement bodies (e.g., IND’s CBI and USA’s FBI) seek to know the list of common terrorist suspects from their respective databases, while they are not allowed to reveal the whole list ot each other;

  • 3.

    A detective agency may want to verify whether a given biometric appears on a government watch-list. Note that privacy of biometric owner has to be preserved if no matches found, while at the same time, unrestricted access to the watch-list cannot be approved.

Private set intersection (PSI) can be utilized to solve the aforementioned problems. It is a two-party cryptographic protocol where each party engages with their private sets. On completion of the protocol either only one of the participants learns the intersection and other learns nothing, yielding one-way PSI or both of them learn the intersection, yielding mutual PSI (mPSI). On the other hand, if the participants wish to determine the cardinality rather than the intersection then that variant of PSI is known as Private set intersection cardinality (PSI-CA). Similar to PSI, it can be divided into two types: one-way PSI-CA and mutual PSI-CA (mPSI-CA).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing