Tag Info

4

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$. When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$. I believe this can be proven using ...

2

The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial time whether to accept or reject). Since $BPP\subseteq \Sigma_2\cap \Pi_2$ it immediately follows that $MA\subseteq \Sigma_2\cap \Pi_2$, which is believed to be a ...

2

As usual with zero-knowledge proofs, this is an interactive proof. A prover is trying to prove that he has a satisfying assignment to some 3-SAT formula without giving away the assignment. A verifier is trying to build up enough statistical evidence to believe the prover. The proof proceeds as a series of rounds and continues until the verifier is ...

1

Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals. Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. Prover chooses a color in $\{1,2,3,4\}$ for each of the following: Variable literals $V(x_i), V(\lnot x_i)$ ($2n$ colors in total). ...

Only top voted, non community-wiki answers of a minimum length are eligible