Article

On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols

Authors:

Iftach Haitner,

Ronen ShaltielAuthors Info & Claims

TCC '09: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography

Pages 220 - 237

https://doi.org/10.1007/978-3-642-00457-5_14

Published: 20 February 2009 Publication History

Abstract

The concept of <em>witness-hiding</em> suggested by Feige and Shamir is a natural relaxation of zero-knowledge. In this paper we identify languages and distributions for which many known constant-round public-coin protocols with negligible soundness cannot be shown to be witness-hiding using black-box techniques. One particular consequence of our results is that parallel repetition of either 3-Colorability or Hamiltonicity cannot be shown to be witness hiding with respect to some probability distribution over the inputs assuming that:

the distribution assigns positive probability only to instances with <em>exactly one</em> witness.

Polynomial size circuits cannot find a witness with noticeable probability on a random input chosen according to the distribution.

The proof of security relies on a black-box reduction that is <em>independent</em> of the choice of the commitment scheme used in the protocol.

These impossibility results conceptually match results of Feige and Shamir that use such black-box reductions to show that parallel repetition of 3-Colorability or Hamiltonicity <em>is</em> witness-hiding for distributions with "two independent witnesses".

We also consider black-box reductions for parallel repetition of 3-Colorability or Hamiltonicity that <em>depend</em> on a specific implementation of the commitment scheme. While we cannot rule out such reductions completely, we show that "natural reductions" cannot bypass the limitations above.

Our proofs use techniques developed by Goldreich and Krawczyk for the case of zero knowledge. The setup of witness-hiding, however, presents new technical and conceptual difficulties that do not arise in the zero-knowledge setting. The high level idea is that if a black-box reduction establishes the witness-hiding property for a protocol, and the protocol also happens to be a proof of knowledge, then this latter property can be actually used "against the reduction" to find witnesses unconditionally.

References

[1]

Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on np-hardness. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 701-710 (2006).

[2]

Babai, L., Moran, S.: Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254-276 (1988).

[3]

Barak, B.: How to go beyond the black-box simulation barrier. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 106-115 (2001).

[4]

Barak, B., Lindell, Y., Vadhan, S.: Lower bounds for non-black-box zero knowledge. Journal of Computer and System Sciences 72(2), 321-391 (2006).

[5]

Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, pp. 1444-1451 (1987).

[6]

Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for np problems. SIAM Journal on Computing 36(4), 1119-1159 (2006).

[7]

Dwork, C., Naor, M.: Zaps and their applications. SIAM Journal on Computing 36(6), 1513-1543 (2007).

[8]

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM Journal on Computing 29(1), 1-28 (1999).

[9]

Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 416-426. ACM, New York (1990).

[10]

Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM Journal on Computing 22(5), 994-1005 (1993).

[11]

Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001).

[12]

Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM J. Comput. 25(1), 169-192 (1996); Preliminary version in ICALP 1990.

[13]

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: FOCS, pp. 174-187. IEEE, Los Alamitos (1986).

[14]

Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7(1), 1-32 (1994).

[15]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186-208 (1989); Preliminary version in STOC 1985.

[16]

Kilian, J., Petrank, E.: An efficient noninteractive zero-knowledge proof system for np with general assumptions. J. Cryptology 11(1), 1-27 (1998).

[17]

Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on np-hardness. In: IEEE Conference on Computational Complexity, pp. 96-110 (2006).

[18]

Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1-20. Springer, Heidelberg (2004).

[19]

Santis, A.D., Persiano, G.: Zero-knowledge proofs of knowledge without interaction. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 427-436 (1992).

Cited By

Kiyoshima S(2021)Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial HardnessTheory of Cryptography10.1007/978-3-030-90459-3_13(369-400)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90459-3_13
Morgan APass RShi E(2020)On the Adaptive Security of MACs and PRFsAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64837-4_24(724-753)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64837-4_24
Kuykendall BZhandry M(2020)Towards Non-interactive Witness HidingTheory of Cryptography10.1007/978-3-030-64375-1_22(627-656)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64375-1_22
Show More Cited By

Recommendations

Zero-knowledge from secure multiparty computation
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small ...
Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin class. Our main results are the following: $$\circ\quad{\rm BPP}^{{\rm NP}}_{||} \subseteq {{\rm P}^{{{\rm pr}{\rm AM}}}_{||}}...
Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity
Abstract
In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length ...
$^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC '09: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography

February 2009

613 pages

ISBN:9783642004568

Editor:
Omer Reingold
Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel 76100

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 February 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kiyoshima S(2021)Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial HardnessTheory of Cryptography10.1007/978-3-030-90459-3_13(369-400)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90459-3_13
Morgan APass RShi E(2020)On the Adaptive Security of MACs and PRFsAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64837-4_24(724-753)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64837-4_24
Kuykendall BZhandry M(2020)Towards Non-interactive Witness HidingTheory of Cryptography10.1007/978-3-030-64375-1_22(627-656)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64375-1_22
Bitansky NKhurana DPaneth OCharikar MCohen E(2019)Weak zero-knowledge beyond the black-box barrierProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316382(1091-1102)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316382
Morgan APass R(2018)On the Security Loss of Unique SignaturesTheory of Cryptography10.1007/978-3-030-03807-6_19(507-536)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1007/978-3-030-03807-6_19
Chung KLin HMahmoody MPass RKleinberg R(2013)On the power of nonuniformity in proofs of securityProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422480(389-400)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422480
Pass R(2013)Unprovable security of perfect NIZK and non-interactive non-malleable commitmentsProceedings of the 10th theory of cryptography conference on Theory of Cryptography10.1007/978-3-642-36594-2_19(334-354)Online publication date: 3-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-36594-2_19
Chung KPass RTseng W(2012)The knowledge tightness of parallel zero-knowledgeProceedings of the 9th international conference on Theory of Cryptography10.1007/978-3-642-28914-9_29(512-529)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28914-9_29
Bitansky NPaneth O(2012)Point obfuscation and 3-round zero-knowledgeProceedings of the 9th international conference on Theory of Cryptography10.1007/978-3-642-28914-9_11(190-208)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28914-9_11
Pass RFortnow LVadhan S(2011)Limits of provable security from standard assumptionsProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993652(109-118)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993652
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents