On the Power of Statistical Zero Knowledge
Open Access
- 1 October 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 23 (02725428) , 708-719
Abstract
We 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. Second, we “lift” this oracle separation to the setting of communication complexity, thereby answering a question of Goos 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 which separate SZK from PZK, NISZK from NIPZK and PZK from coPZK. The first of these results answers a question raised in 1991 by Aiello and Hastad (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.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- The Pattern Matrix MethodSIAM Journal on Computing, 2011
- The Sign-Rank of AC$^0$SIAM Journal on Computing, 2010
- Quantum computing and hidden variablesPhysical Review A, 2005
- A complete problem for statistical zero knowledgeJournal of the ACM, 2003
- The random oracle hypothesis is falseJournal of Computer and System Sciences, 1994
- Relativized perfect zero knowledge is not BPPInformation and Computation, 1991
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Statistical zero-knowledge languages can be recognized in two roundsJournal of Computer and System Sciences, 1991
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- Probabilistic communication complexityJournal of Computer and System Sciences, 1986