ECCC-Report TR16-140https://eccc.weizmann.ac.il/report/2016/140Comments and Revisions published for TR16-140en-usMon, 08 May 2017 23:11:44 +0300
Revision 3
| On the Power of Statistical Zero Knowledge |
Adam Bouland,
Lijie Chen,
Dhiraj Holden,
Justin Thaler,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2016/140#revision3We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we "lift" this oracle separation to the setting of communication complexity, thereby answering a question of Göös et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK is not contained in PZK, NISZK is not contained in NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and Håstad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity.
The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.Mon, 08 May 2017 23:11:44 +0300https://eccc.weizmann.ac.il/report/2016/140#revision3
Revision 2
| On SZK and PP |
Adam Bouland,
Lijie Chen,
Dhiraj Holden,
Justin Thaler,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2016/140#revision2In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. This answers an open question of Watrous from 2002 [Aar]. The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree. Using our techniques, we also give oracles relative to which the following two separations hold: perfect zero knowledge (PZK) is not contained in its complement (coPZK) and SZK (indeed, even NISZK) is not contained in PZK (indeed, even HVPZK). Along the way, we show that HVPZK is contained in PP in a relativizing manner.
We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.
Tue, 29 Nov 2016 00:11:37 +0200https://eccc.weizmann.ac.il/report/2016/140#revision2
Revision 1
| On SZK and PP |
Adam Bouland,
Lijie Chen,
Dhiraj Holden,
Justin Thaler,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2016/140#revision1In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. This answers an open question of Watrous from 2002 [Aar]. The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.
Using our techniques, we also give oracles relative to which the following two separations hold: honest-verifier perfect zero knowledge (HVPZK) is not contained in its complement (coHVPZK), and SZK (indeed, even NISZK) is not contained in PZK (indeed, even HVPZK). Along the way, we show that HVPZK is contained in PP in a relativizing manner.
We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.
Wed, 14 Sep 2016 19:30:47 +0300https://eccc.weizmann.ac.il/report/2016/140#revision1
Paper TR16-140
| On SZK and PP |
Adam Bouland,
Lijie Chen,
Dhiraj Holden,
Justin Thaler,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2016/140In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. Equivalently, postselected quantum computers cannot break SZK or NISZK in a black-box manner. This answers an open question of Watrous from 2002 [Aar].
The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree. Using our techniques, we additionally prove an oracle separation between perfect zero knowledge (PZK) and its complement (coPZK). Therefore, in contrast with the case of SZK [SV03], one cannot show that perfect zero knowledge proof systems are closed under complement in a black-box manner. We also show an oracle relative to which NISZK (or SZK) is not contained in PZK - so even non-interactive statistical-zero-knowledge proofs may be more powerful than interactive perfect zero knowledge proofs.
We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results have implications for delegating computation; they imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.
Sat, 10 Sep 2016 04:06:04 +0300https://eccc.weizmann.ac.il/report/2016/140