# Sigma-protocol for 3SAT problem

I have some questions from previous years exams, I hope you could help me with them. :)

Let $g,h$ denote generators of a group $G$ of large prime order $n$ such that $\log_g h$ is unknown to anyone. Consider an instance of the 3SAT problem for Boolean variables $v_1, \ldots , v_l$, given by a Boolean formula $\Phi$ consisting of $m$ clauses, which each consist of $3$ literals:

$\Phi = (l_{1,1} \vee l_{1,2} \vee l_{1,3}) \wedge \ldots \wedge (l_{m,1} \vee l_{m,2} \vee l_{m,3})$.

Each literal is of the form $l_{i,j}=v_k$ or $l_{i,j}=\overline{v_k}=1-v_k$ (negation of $v_k$), $1 \le k \le l$. Construct a $\Sigma$-protocol for the following relation:

$R_{\Phi}=\{ (B_1, \ldots, B_l;x_1,y_1,\ldots,x_l,y_l)\colon \Phi(x_1,\ldots,x_l), \forall_{k=1}^l B_k=g^{x_k}h^{y_k}, x_k \in \{ 0,1 \} \}$.

Thanks, Peter.

-
Could you add the definition of $\Sigma$-protocol? – Paŭlo Ebermann Dec 4 '12 at 13:11
Welcome to Crypto.SE! This looks like an interesting question, but it would help to have a little more information. What have you tried so far? What research have you done on your own so far? As the faq suggests, it is important to "do your homework" and show us what you've done so far. I encourage you to read the links in this comment -- they may provide helpful background about this site! – D.W. Dec 4 '12 at 23:07

This is doable by (1) opening all commitments $B_k$ with standard responses $Q_{k}(z)$ that are linear in challenge, (2) proving that all $x_k \in \{0,1\}$ (with at most second-degree polynomials in challenge), and (3) proving $m$ polynomial identities for (at most) third-degree polynomials in challenge $$U_i(z) = T_{i,1}(z) T_{i,2}(z) T_{i,3}(z)$$ where $T_{i,j}(z) = Q_{i,j}(z) - z l_{i,j}$ and $Q_k(z) = v_k z + \alpha_k$ considered over the ring modulo group order and $\alpha_k$ are initial random coins.
With such a $\Sigma$-like protocol, prover will send commitments to 3 coefficients of polynomials $U_k(z)$. It is actually proven that such a polynomial is of 2nd degree, not 3rd. Informally, we need at least one TRUE out of each triple for satifstiability, so at least one constant (degree 0) polynomial for each $(T_{i,1}(z), T_{i,2}(z), T_{i,3}(z))$. The well-known $\Sigma$-protocol would evaluate a linear (degree 1) polynomial at a random point chosen as a challenge.
(Soundness) For any (that is, dishonest) prover, there are at most 3 chances (unlike just 1 for the well-known $\Sigma$-protocol) for such a polynomial to evaluate to zero by choosing some random value for the free variable $z$. See Schwartz-Zippel lemma for details.
For point (2), one would prove that $Q_k(z) (Q_k(z) - z)$ is linear (not quadratic) by sending commitments to two coefficients.