Paper 2017/390
On the Security of Classic Protocols for Unique Witness Relations
Yi Deng, Xuyang Song, 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- A minor revision of an IACR publication in PKC 2018
- Contact author(s)
- deng @ iie ac cn
- History
- 2018-01-01: last of 2 revisions
- 2017-05-05: received
- See all versions
- Short URL
- https://ia.cr/2017/390
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/390,
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},
url = {https://eprint.iacr.org/2017/390}
}