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.