# Questions tagged [interactive-proof-systems]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
35 views

### Statement of the Goldwasser-Sipser Set Low Bound Protocol

I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak. In particular, I'm ...
153 views

### How to remove a universal quantifier in Lean theorem prover

I am working with two binary relations: g_o and pw_o, and I've defined pw_o below: constants {A : Type} (g_o : A → A → Prop) ...
15 views

### Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of ...
39 views

### Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
199 views

### Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
61 views

### Proving a pattern exist in a string without revealing where

Some time ago i read the following problem (i don't remember the article from which i read it from) : "Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
48 views

### Interactive proof system for graph nonisomorphism

$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$ GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each ...
15 views

### Why the soundness error in the $\mathrm{IP}$ of GNI can implicate $\mathrm{\Sigma_2} \subseteq \mathrm{\Pi_2}$ if GNI is co-NP-Complete?

PDF here shows a way to proof GI is NP-Complete $\implies \Sigma_2 = \Pi_2$. In the last step, it writes following: In other words, (1) is false in this case as required. Book Computational ...
24 views

### Proving (relativized) upper bounds against SZK

Does anyone know of any instances where we've been able to show that some complexity class is strictly harder than SZK relative to some oracle? In general, it seems that SZK is really hard (for ...
390 views

### Are there deterministic and/or non-interactive zero-knowledge proofs?

The Wikipedia page on zero-knowledge proof says Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a ...
14 views

### Practical applications of multi-prover interactive proof protocols

A multi-prover interactive proof protocol, as described here, consists of computationally unbound provers $P_1,P_2,\ldots$ which together convince a polynomial-time verifier $V$ of some proposition, ...
231 views

### Perfect Completeness of AM protocols?

I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...
29 views

433 views

### How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such ...
Given two graphs $G_1$ and $G_2$, a zero-knowledge interactive protocol for a prover to convince a verifier that $G_1\not\cong G_2$ entails: The verifier choosing a random $i\in\{1,2\}$ The verifier ...