Credibility in Private Set Membership

Sanjam Garg, Mohammad Hajiabadi, Abhishek Jain, Zhengzhong Jin, Omkant Pandey, Sina Shiehian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A private set membership (PSM) protocol allows a “receiver” to learn whether its input x is contained in a large database DB held by a “sender”. In this work, we define and construct 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∈ DB. Furthermore, the communication complexity must be logarithmic in the size of DB. We provide 2-round (i.e., round-optimal) C-PSM constructions based on standard assumptions: We present a black-box construction in the plain model based on DDH or LWE.Next, we consider protocols that support predicates f beyond string equality, i.e., the receiver can learn if there exists w∈ 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. As an application, our protocols can be used to build enhanced round-optimal leaked password notification services, where unlike existing solutions, a dubious sender cannot fool a receiver into changing its password.

Original languageEnglish (US)
Title of host publicationPublic-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsAlexandra Boldyreva, Vladimir Kolesnikov
PublisherSpringer Science and Business Media Deutschland GmbH
Pages159-189
Number of pages31
ISBN (Print)9783031313707
DOIs
StatePublished - 2023
Event26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, United States
Duration: May 7 2023May 10 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13941 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023
Country/TerritoryUnited States
CityAtlanta
Period5/7/235/10/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Cite this