New answers tagged

1

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). ...


Top 50 recent answers are included