New answers tagged interactive-proof-systems
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
Related Tags
interactive-proof-systems × 37complexity-theory × 24
satisfiability × 4
complexity-classes × 4
cryptography × 3
proof-assistants × 3
graph-isomorphism × 3
algorithms × 2
space-complexity × 2
hash × 2
probabilistic-algorithms × 2
time-complexity × 1
data-structures × 1
algorithm-analysis × 1
reductions × 1
logic × 1
proof-techniques × 1
np × 1
artificial-intelligence × 1
functional-programming × 1
hashing × 1
security × 1
term-rewriting × 1
co-np × 1
knowledge-representation × 1