International Association
for Cryptologic Research

We initiate the study of witness authenticating NIZK proof systems (waNIZKs), in which one can use a witness $w$ of a statement $x$ to identify whether a valid proof for $x$ is indeed generated using $w$. Such a new identification functionality enables more diverse applications, and it also puts new requirements on soundness that: (1) no adversary can generate a valid proof that will not be identified by any witness; (2) or forge a proof using her valid witness to frame others. To work around the obvious obstacle towards conventional zero-knowledgeness, we define entropic zero-knowledgeness that requires the proof to leak no partial information, if the witness has sufficient computational entropy. We give a formal treatment of this new primitive. The modeling turns out to be quite involved and multiple subtle points arise and particular cares are required. We present general constructions from standard assumptions. We also demonstrate three applications in non-malleable (perfect one-way) hash, group signatures with verifier-local revocations and plaintext-checkable public-key encryption. Our waNIZK provides a new tool to advance the state of the art in all these applications.

Robust (fuzzy) extractors are very useful for, e.g., authenticated key exchange from a shared weak secret and remote biometric authentication against active adversaries. They enable two parties to extract the same uniform randomness with a ``helper'' string. More importantly, they have an authentication mechanism built in that tampering of the ``helper'' string will be detected. Unfortunately, as shown by Dodis and Wichs, in the information-theoretic setting, a robust extractor for an $(n,k)$-source requires $k>n/2$, which is in sharp contrast with randomness extractors which only require $k=\omega(\log n)$. Existing works either rely on random oracles or introduce CRS and work only for CRS-independent sources (even in the computational setting). In this work, we give a systematic study about robust (fuzzy) extractors for general CRS {\em dependent} sources. We show in the information-theoretic setting, the same entropy lower bound holds even in the CRS model; we then show we {\em can} have robust extractors in the computational setting for general CRS-dependent source that is only with minimal entropy. We further extend our construction to robust fuzzy extractors. Along the way, we propose a new primitive called $\kappa$-MAC, which is unforgeable with a weak key and hides all partial information about the key (both against auxiliary input); it may be of independent interests.