Cryptology ePrint Archive: Report 2017/390

On the Security of Classic Protocols for Unique Witness Relations

Yi Deng and Xuyang Song and Jingyue Yu and Yu Chen

Abstract: 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.

Category / Keywords: witness hiding and unique witness and instance compression

Original Publication (with minor differences): IACR-PKC-2018

Date: received 5 May 2017, last revised 1 Jan 2018

Contact author: deng at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20180101:111307 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]