Boldyreva, A.
; Kolesnikov, V.
(Ed.)
A private set membership (PSM) protocol allows a βreceiverβ to learn whether its input x is contained in a large database π£π‘ 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 π₯βπ£π‘. Furthermore, the communication complexity must be logarithmic in the size of π£π‘.
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 π€βπ£π‘ such that π(π₯,π€)=1. We present two results with transparent setups: (1) A black-box protocol, based on DDH or LWE, for the class of NC1 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.
https://doi.org/10.1007/978-3-031-31371-4_6
more »
« less