International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Credibility in Private Set Membership

Sanjam Garg , University of California, Berkeley and NTT Research
Mohammad Hajiabadi , University of Waterloo
Abhishek Jain , Johns Hopkins University
Zhengzhong Jin , MIT
Omkant Pandey , Stony Brook University
Sina Shiehian , Snap Inc.
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: A private set membership (PSM) protocol allows a ``receiver'' to learn whether its input $x$ is contained in a large database $\algo{DB}$ held by a ``sender''. In this work, we define and construct \emph{credible private set membership (C-PSM)} protocols: in addition to the conventional notions of privacy, C-PSM provides a soundness guarantee that it is hard for a sender (that does not know $x$) to convince the receiver that $x \in \algo{DB}$. Furthermore, the communication complexity must be logarithmic in the size of $\algo{DB}$. We provide 2-round (i.e., round-optimal) C-PSM constructions based on standard assumptions: \begin{itemize}[itemsep=0pt] \item We present a black-box construction in the plain model based on DDH or LWE. \item Next, we consider protocols that support predicates $f$ beyond string equality, i.e., the receiver can learn if there exists $w \in \algo{DB}$ such that $f(x,w) = 1$. We present two results with transparent setups: (1) A black-box protocol, based on DDH or LWE, for the class of NC$^1$ functions $f$ which are efficiently searchable. (2) An LWE-based construction for all bounded-depth circuits. The only non-black-box use of cryptography in this construction is through the bootstrapping procedure in fully homomorphic encryption. \end{itemize} As an application, our protocols can be used to build enhanced leaked password notification services, where unlike existing solutions, a dubious sender {\em cannot} fool a receiver into changing its password.
  title={Credibility in Private Set Membership},
  author={Sanjam Garg and Mohammad Hajiabadi and Abhishek Jain and Zhengzhong Jin and Omkant Pandey and Sina Shiehian},