International Association
for Cryptologic Research

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.

Non-malleable zero-knowledge, originally introduced in the context of man-in-the-middle attacks, serves as an important building block to protect against concurrent attacks where different protocols may coexist and interleave. While this primitive admits almost optimal constructions in the plain model, they are several orders of magnitude slower in practice than standalone zero-knowledge. This is in sharp contrast to non-malleable commitments where practical constructions (under the DDH assumption) have been known for a while. We present a new approach for constructing efficient non-malleable zero-knowledge for all languages in NP, based on a new primitive called instance-based non-malleable commitment (IBNMC). We show how to construct practical IBNMC by leveraging the fact that simulators of sub-linear zero-knowledge protocols can be much faster than the honest prover algorithm. With an efficient implementation of IBNMC, our approach yields the first general-purpose non-malleable zero-knowledge protocol that achieves practical efficiency in the plain model. All of our protocols can be instantiated from symmetric primitives such as block-ciphers and hash functions, have reasonable efficiency in practice, and are general-purpose. Our techniques also yield the first efficient non-malleable commitment scheme without public-key assumptions.

General-purpose zero-knowledge proofs for all $\NP$ languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains black-box calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only black-box access to the function. Rosulek (Crypto'12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access. We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function $f$, we seek to construct a {\em new} one-way function $F$ given only black-box access to $f$, {\em and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a {\em proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions. We show how to construct proof-based versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically, \begin{itemize} \item We first show that if the prover entirely chooses the input, then proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary. \item We next present black-box constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used Goldreich-Levin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input. \end{itemize} Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.

Ring signatures allow a user to sign a message on behalf of a ``ring'' of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members. In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a trusted setup or on the random oracle heuristic. In contrast with the prior work of Backes \etal~[EUROCRYPT'2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE. At the heart of our scheme is a new construction of compact and statistically witness-indistinguishable ZAP arguments for NP $\cap$ coNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assuming \emph{sub-exponential} LWE. We believe that this scheme might find further applications in the future.