3
$\begingroup$

Alice sends to Bob a value $B$ in $\mathbb{G}$ a group of high order. There are distinct elements $h_1$ and $h_2$ of high order of $\mathbb{G}$, and Alice wants to prove to Bob that she knows some values $b_1, b_2 \in \mathbb{Z}_q$ such that $B=h_1^{b_1}h_2^{b_2}$.

I have found the following related post (quite old and without answer), but I could not find any information about the mentioned Okamoto protocol.

1/ Is this kind of proof possible and what are the techniques used in the literature to construct such a zero knowledge proof of knowledge?

2/ Is the Okamoto protocol in the related post correct? Where can we find information about it?

$\endgroup$
5
  • $\begingroup$ What research have you done? What have you found and tried? $\endgroup$
    – e-sushi
    Commented Apr 12 at 20:03
  • $\begingroup$ @e-sushi I am not aware about the techniques we could use. Some pointers, courses, videos, could help $\endgroup$
    – Adam54
    Commented Apr 12 at 21:49
  • $\begingroup$ Note: If I understand the question correctly, it's about Zero knowledge proof of knowledge of coefficients in a linear expression. The term linear becomes clearer is we rewrite the expression $B=h_1^{b_1}h_2^{b_2}$ with the group $\mathbb G$ noted additively rather than multiplicatively. The problem then is proving knowledge of scalars $b_1$ and $b_2$ such that $B=b_1\cdot H_1+b_2\cdot H_2$, without disclosing anything about these $b_1$ and $b_2$. (continued) $\endgroup$
    – fgrieu
    Commented May 12 at 7:57
  • $\begingroup$ With that additive notation, the protocol proposed in the related post is: Prover picks random secret $r_1,r_2\in\mathbb Z_q$, sends $A=r_1\cdot H_1+r_2\cdot H_2$. Verifier picks and sends random $c\in\mathbb Z_q$. Prover computes and sends $z_1=r_1+c\,b_1\bmod q$, $z_2=r_2+c\,b_2\bmod q$. Verifier checks that $z_1\cdot H_1+z_2\cdot H_2=A+c\cdot B$, and if that holds accepts that prover knows $b_1$ and $b_2$. I'm not able to answer the question (in particular I fail to decide if this proof is "zero-knowledge"). $\endgroup$
    – fgrieu
    Commented May 12 at 8:49
  • $\begingroup$ Thank you @fgrieu $\endgroup$
    – Adam54
    Commented May 15 at 7:26

1 Answer 1

2
$\begingroup$

Search "Okamoto protocol" in google(quotation involved), you can find the lecture notes and some other slides.

So the Okamoto protocol is a WI and WH protocol, but not ZK. Besides, it's also HVZK, but not ZK. You can also have a reference here.

$\endgroup$
2
  • $\begingroup$ Thanks very much Yang. Why do you say it is not ZK? Are you referring to the malicious setting? I am new in this topic. But I have read somewhere that any hvzk proof can be transformed into something ZK in the malicious setting by way of a FS transform. $\endgroup$
    – Adam54
    Commented May 15 at 7:26
  • $\begingroup$ @Adam54 Yes. I mean malicious verifier, who may deviate the protocol. You are right there is some general method from HVZK to ZK(like it in sec 8). But I think what you want is not FS transform. Because FS outputs a non-interactive ZK under random oracle model( FS always used to get a signature scheme from a identification scheme). So you can do some transform, but that's a new protocol. The okamoto's protocol is ZK only against honest verifier. $\endgroup$
    – Yang
    Commented May 15 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.