Paper 2017/390

On the Security of Classic Protocols for Unique Witness Relations

Yi Deng, Xuyang Song, Jingyue Yu, and Yu Chen


We revisit the problem of whether the known classic constant-round public-coin argument/proof systems are witness hiding for languages/distributions with unique witnesses. Though strong black-box \emph{impossibility} results are known, we provide some less unexpected \emph{positive} results on the witness hiding security of these classic protocols: --We give sufficient conditions on a hard distribution over \emph{unique} witness NP relation for which all witness indistinguishable protocols (including all public-coin ones, such as ZAPs, Blum protocol and GMW protocol) are indeed witness hiding. We also show a wide range of cryptographic problems with unique witnesses satisfy these conditions, and thus admit constant-round public-coin witness hiding proof system. ---For the classic Schnorr protocol (for which the distribution of statements being proven seems not to satisfy the above sufficient conditions), we develop an embedding technique and extend the result of Bellare and Palacio to base the witness hiding property of the Schnorr protocol in the standalone setting on a \emph{relaxed} version of one-more like discrete logarithm (DL) assumption, and show that breaking this assumption would lead to some surprising consequences, such as instance compression for DL problem, zero knowledge protocols for the AND-DL language with extremely efficient communication and highly non-trivial hash combiner for hash functions based on DL problem. Similar results hold for the Guillou-Quisquater protocol.

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2018
Contact author(s)
deng @ iie ac cn
2018-01-01: last of 2 revisions
2017-05-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi Deng and Xuyang Song and Jingyue Yu and Yu Chen},
      title = {On the Security of Classic Protocols for Unique Witness Relations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/390},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.