Perfect Zero Knowledge: New Upperbounds and Relativized Separations

Peter Dixon, Sutanu Gayen, A. Pavan, N. V. Vinodchandran

TL;DR

This paper delves into the complexity of "perfect zero-knowledge" interactive proof systems, establishing new unconditional upper bounds and demonstrating separations between these systems and traditional complexity classes. The authors achieve this by analyzing distribution testing problems, revealing that the complexity class SBP plays a crucial role and that perfect zero-knowledge classes are not as powerful as previously thought in certain relativized worlds.

What Problem Does This Paper Address?

The paper tackles the intricate landscape of zero-knowledge interactive proofs, a cornerstone of modern cryptography. Specifically, it focuses on "perfect zero-knowledge" (PZK) and its non-interactive counterpart (NIPZK). While the foundational work established the existence of these proof systems, understanding their precise relationship with established complexity classes like PP, AM, and SBP has remained a significant challenge. The authors aim to refine this understanding by establishing new unconditional upper bounds for NIPZK and by constructing "relativized worlds" (theoretical scenarios with oracle access) to demonstrate separations between PZK/NIPZK and other complexity classes. This helps clarify what can and cannot be achieved with perfect zero-knowledge proofs, especially in relation to computational power.

Methods

The core of the paper's methodology involves analyzing specific computational problems related to distribution testing. These problems involve determining properties of probability distributions represented by succinct Boolean circuits. The authors leverage two key distribution testing problems:

  • ENTROPY APPROXIMATION (EA): Determining if the entropy of a samplable distribution is above or below a certain threshold. This problem is known to be complete for NISZK (Non-Interactive Statistical Zero Knowledge).
  • UNIFORM: A problem related to distinguishing a uniform distribution from one that is "close" to uniform. This problem is shown to be complete for NIPZK.

By constructing algorithms for these problems within specific complexity classes (like CoSBP) and by designing oracle separations, the authors establish their main results. The oracle separation technique involves creating hypothetical worlds where certain machines have access to an "oracle" (a black box that can solve a specific problem). By showing that a machine cannot solve a problem even with oracle access, they demonstrate that the problem is inherently harder than what the machine's class can handle.

Datasets

Not discussed in the paper. The paper deals with theoretical complexity classes and computational problems defined by circuits, rather than empirical datasets.

Key Insights and Ideas

  • SBP's Central Role: The complexity class SBP (Small Bounded-error Probability) emerges as a key player in bounding NIPZK. The paper establishes an unconditional inclusion NIPZK ⊆ CoSBP, refining previous bounds.
  • Relativized Separations are Crucial: The authors demonstrate that unconditional proofs of upper bounds are difficult. They use oracle separations to show that NIPZK is not closed under complement in a relativized world, and that PZK can be separated from CoSBP. This highlights the limitations of current proof techniques and suggests that PZK/NIPZK might be strictly weaker than certain other complexity classes.
  • Distribution Testing as a Bridge: The paper elegantly connects the abstract world of complexity classes with concrete problems in distribution testing. It shows how problems like UNIFORM and its variants serve as powerful tools for proving results about PZK and NIPZK.
  • Min-Entropy vs. Entropy: An interesting observation is that while ENTROPY APPROXIMATION is NISZK-complete, the analogous MIN-ENTROPY APPROXIMATION problem is complete for SBP. This subtle difference in problem definition leads to different complexity class memberships.

Key Results

  • Unconditional Inclusion: NIPZK ⊆ CoSBP. This is a new unconditional upper bound on the complexity class NIPZK.
  • Relativized Separation 1: There exists a relativized world where NIPZK (and thus PZK) is not contained in SBP. This implies NIPZK is not closed under complement in a relativized setting.
  • Relativized Separation 2: There exists a relativized world where PZK is not contained in CoSBP.

Limitations and Future Work

The paper primarily focuses on relativized separations, which are powerful tools but do not directly imply separations in the real, non-relativized world. The authors acknowledge that their results refine the landscape of perfect zero-knowledge classes but do not resolve all open questions.

Future work could explore:

  • Unconditional Separations: Investigating whether the demonstrated relativized separations can be translated into unconditional separations between PZK/NIPZK and classes like SBP or CoSBP.
  • Other Complexity Classes: Further exploring the relationships between PZK/NIPZK and other complexity classes, potentially using the distribution testing framework.
  • Statistical Zero-Knowledge: Extending these investigations to the broader class of statistical zero-knowledge (SZK) proofs.

Summary updated

Abstract

We investigate the complexity of problems that admit perfect zero-knowledge interactive protocols and establish new unconditional upper bounds and oracle separation results. We establish our results by investigating certain distribution testing problems: computational problems over high-dimensional distributions represented by succinct Boolean circuits. A relatively less-investigated complexity class SBP emerged as significant in this study. The main results we establish are: 1. A unconditional inclusion that NIPZK is in CoSBP. 2. Construction of a relativized world in which there is a distribution testing problem that lies in NIPZK but not in SBP, thus giving a relativized separation of NIPZK (and hence PZK) from SBP. 3. Construction of a relativized world in which there is a distribution testing problem that lies in PZK but not in CoSBP, thus giving a relativized separation of PZK from CoSBP. These results refine the landscape of perfect zero-knowledge classes in relation to traditional complexity classes.
BibTeX
@article{dixon2020perfect,
  author = {Peter Dixon and Sutanu Gayen and A. Pavan and N. V. Vinodchandran},
  title = {{Perfect Zero Knowledge: New Upperbounds and Relativized Separations}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
}
Figure