Welcome to the resource topic for 2017/390
Title:
On the Security of Classic Protocols for Unique Witness Relations
Authors: Yi Deng, Xuyang Song, Jingyue Yu, 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.
ePrint: https://eprint.iacr.org/2017/390
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .