Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.
Samuel Ranellucci, Alain Tapp, Rasmus Winther Zakarias
Abstract. Even though Zero-knowledge has existed for more than 30 years, few generic constructions for Zero-knowledge exist. In this paper we present a new kind of commitment scheme on which we build a novel and efficient Zero-knowledge protocol for circuit satisfiability. 1
The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the unpredictability property of random oracles [12]: If O is a random oracle then it is infeasible to find an inputx such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of CIFEs, where multi-input means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.
We give a sufficient condition for a family of pseudoresolvents in a Banach algebra to be trivially zero. As an important consequence, we provide an alternate proof of the classical result that the spectrum of any linear bounded operator on a Banach space is nonempty. The proofs are elementary, requiring only a basic knowledge of real and complex analysis.
This paper presents a perfect zero knowledge proof system for a decision problem which is computationally equivalent to the Discrete Root Problem,and its zero knowledge property does not rely on any assumptions.Thus we provide additional evidence to the belief that perfect zero knowledge proof systems exist in a non trivial manner (i.e.,for language not in BPP).
Abstract Abstract. Recent approaches to the notions of randomness and proofs are surveyed. The new notions differ from the traditional ones in being subjective to the capabilities of the observer rather than reflecting âidealâ entities. The new notion of randomness regards probability distributions as equal if they cannot be told apart by efficient procedures. This notion is constructive and is suited for many applications. The new notion of a proof allows the introduction of the notion of zero-knowledge proofs: convincing arguments which yield nothing but the validity of the assertion. The new approaches to randomness and proofs are based on basic concepts and results from the theory of resource-bounded computation. Elements of this theory are presented only to the extent required for the description of the new approaches. This survey is not intended to provide an account of the more traditional approaches to randomness (e.g., Kolmogorov Complexity; see also Bennettâs account in this volume) and proofs (i.e., traditional logic systems). Whenever these approaches are described it is only in order to confront them with the new approaches.