Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.