Paper 2021/1214

Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial Hardness

Susumu Kiyoshima

Abstract

We study the problem of obtaining 2-round interactive arguments for NP with weak zero-knowledge (weak ZK) [Dwork et al., 2003] or with strong witness indistinguishability (strong WI) [Goldreich, 2001] under polynomially hard falsifiable assumptions. We consider both the delayed-input setting [Jain et al., 2017] and the standard non-delayed-input setting, where in the delayed-input setting, (i) prover privacy is only required to hold against delayed-input verifiers (which learn statements in the last round of the protocol) and (ii) soundness is required to hold even against adaptive provers (which choose statements in the last round of the protocol). Concretely, we show the following black-box (BB) impossibility results by relying on standard cryptographic primitives (such as one-way functions and trapdoor permutations). 1. It is impossible to obtain 2-round delayed-input weak ZK arguments under polynomially hard falsifiable assumptions if BB reductions are used to prove soundness. This result holds even when non-black-box techniques are used to prove weak ZK. 2. It is impossible to obtain 2-round non-delayed-input strong WI arguments and 2-round publicly verifiable delayed-input strong WI arguments under polynomially hard falsifiable assumptions if a natural type of BB reductions, called oblivious BB reductions, are used to prove strong WI. (Concretely, a BB reduction for strong WI is called oblivious if it is black-box not only about the cheating verifier but also about the statement distributions.) 3. It is impossible to obtain 2-round delayed-input strong WI arguments under polynomially hard falsifiable assumptions if BB reductions are used to prove both soundness and strong WI (the BB reductions for strong WI are required to be oblivious as above). Compared with the above result, this result no longer requires public verifiability in the delayed-input setting.

Note: (Sep. 23, 2021) This is the full version of the paper was accepted to TCC 2021. From the proceeding version, we have slightly modified the proof of Lemma 2 to (hopefully) improve the readability.