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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Tcc 2021
Keywords
weak zero-knowledgestrong witness indistinguishabilityblack-box impossibilitymeta-reduction
Contact author(s)
susumu kiyoshima @ ntt-research com
History
2021-09-24: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1214
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1214,
      author = {Susumu Kiyoshima},
      title = {Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial Hardness},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1214},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1214}},
      url = {https://eprint.iacr.org/2021/1214}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.