Paper 2017/390

On Instance Compression, Schnorr/Guillou-Quisquater, and 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 witness hiding property of classic 3-round public-coin proof systems for languages/distributions with unique witnesses are still witness hiding. Though strong black-box impossibility results are known for them, we provide some less unexpected positive results on the witness hiding security of classic protocols: 1. We develop an embedding technique and prove that the witness hiding property of the standalone Schnorr protocol based on a weaker version of one-more like discrete logarithm (DL) assumption asserting that, for an arbitrary constant $\ell$, it is infeasible for a PPT algorithm to solve $l$ DL instances with being restricted to query the DL oracle only once. Similar result holds for the Guillou-Quisquater protocol. This improves over the positive result of Bellare and Palacio in that when applying their technique to the standalone setting, the underlying assumption is stronger and required to hold only for $\ell=2$. 2. Following the framework of Harnik and Naor, we introduce the notion of tailored instance compression to capture the essence of the known one-more like assumptions, which provides new insight into the hardness of one-more DL/RSA problems and allows us to reveal some strong consequences of breaking our weaker version of one-more like assumption,including zero knowledge protocols for the AND-DL and AND-RSA languages with extremely efficient communication and non-trivial hash combiner for hash functions based on DL problem. These consequences can be viewed as positive evidences for the security of Schnorr and Guillou-Quisquater protocols. 3. We observe that the previously known impossibility results on the witness hiding of public-coin protocols for unique witness relation make certain restriction on the reduction. By introducing an input-distribution-switching technique, we bypass these known impossibility results and prove that, for any hard language $L$, if a distribution $(\mathbb{X}, \mathbb{W})$ over unique witness relation $R_{L}$ has an indistinguishable counterpart distribution over some multiple witnesses relation, then any witness indistinguishable protocols (including ZAPs and all known 3-round public-coin protocols, such as Blum protocol and GMW protocol) are indeed witness hiding for the distribution $(\mathbb{X}, \mathbb{W})$. We also show a wide range of cryptographic problems with unique witnesses satisfy the ``if condition'' of this result, and thus admit constant-round public-coin witness hiding proof system. This is the first positive result on the witness-hiding property of the classic protocols for non-trivial unique witness relations.