4
$\begingroup$

With setup $p$ and $q$ where $p = 2q + 1$, and $g$ and $h$ is the generator with order $q$.

In Pedersen commitment, I commit the value m with $c=g^m h^r \bmod p$, then de-commit by revealing $(m, r)$. $c' = c$, then the commitment hold.

I am wondering if I don't need to reveal $r$ to verifier, instead I can reveal $m$ only and construct a proof of knowledge on $r$ to have the sample result. As $s = h^r$ if $s = {{c}\over{g^m}}$, I can use Schnorr Protocol to prove that I know $r$ in $s = h^r$ for $s = {{c}\over{g^m}}$.

If verification hold, mean that provers know $r$ with $m$ in a relationship $c=g^m h^r$. Am I right?


I would like to add follow-up question if the answer is yes.

To prove the knowledge of $r$ in $s = h^r$ for $s = {{c}\over{g^m}}$. I can use Schnorr Protocol to construct the proof. But if it is possible to make it only available for designated verifier to verify the proof?

I read a paper is about Designated Verifier Signature, but it is about creating proof on a signature $s=m^x$ where $m$ is the message and $x$ is the private key of signer.

So is it possible to make Schnorr Protocol only can be verified by a selected verifier with know public key?

$\endgroup$
3
  • 1
    $\begingroup$ Yes, you are correct. This feels too short to be an answer... $\endgroup$
    – poncho
    Apr 11, 2020 at 12:48
  • $\begingroup$ @poncho If yes, what is the benefit of revealing r comparing with constructing a knowledge proof of r? $\endgroup$
    – Jeff Lee
    Apr 11, 2020 at 14:08
  • $\begingroup$ @poncho Thanks for your answer!! I just edited by question. $\endgroup$
    – Jeff Lee
    Apr 11, 2020 at 14:15

1 Answer 1

4
$\begingroup$

So is it possible to make Schnorr Protocol only can be verified by a selected verifier with know public key?

Here's the obvious way using a two dimensional Schnorr proof; this is a proof that, given $A^xB^y = C$, you know $x, y$. It's a straight-forward extension of the regular Schnorr proof:

  • The prover selects random $r, s$, and computes $T = A^rB^s$. He also computes $t = \text{Hash}(T)$ and publishes $T$, $u = x + rt$ and $v = y + st$.

  • The verifier checks whether $A^uB^v = C T^t$

We'll denote $K$ as the public key of the verifier, that is, she knows the value $k$ such that $G^k = K$.

Then, to do a Selected Verifier Proof that the commitment $C = G^m H^r$ is to the value $m$, the prover generates a two dimensional Schnorr proof that he knows the values $x, y$ such that $H^x K^y = C G^{-m}$. The valid prover can generate such a proof, because he knows such a pair $(x = r, y = 0)$. On the other hand, the verifier can not convince anyone else that this proves any specific value $m$, because for any $m$, she can construct a $y$ that allows her to generate such a proof.


Here's another idea that occurs to me; it appears to be a way to have a designated verifier Schnorr proof:

  • The prover wants to prove knowledge of a value $x$ s.t. $A^x = B$, for public $A, B$. We'll denote $K$ as the public key of the verifier.

  • The prover selects two random values $r_1, r_2$, and computes $T_1 = A^{r_1}, T_2 = K^{r_2}$ and $U = G^{r_2}$ and computes $t = T_1 + T_2 \bmod q$ (where $q$ is the size of the subgroup). Then, he publishes $T_1, U$ and $u = x + r_1t$

  • The designated verifier uses her private key $k$ to compute $T_2 = U^k$, and $t = T_1 + T_2 \bmod q$. Then, it proceeds like a standard Schnorr proof, checking whether $A^u = BT_1^t$

No one can verify this proof without the knowledge of $k$ (as they cannot compute $t$). The designated verifier knows no one else knows $k$, and hence the prover cannot select $t$ arbitrarily. And, if the verifier tried to forward this proof (possibly by forwarding the value $T$), this doesn't work (even if she exposed her private key $k$), because it is straight-forward to generate a validating $T_1, U, u$ set with the knowledge of $k$ (for arbitrary $A, B$)

Somebody should vet this 'designated Schnorr' proof before you use it; it looks like it meets the requirements. Here's the reasoning for the 'proof of knowledge' portion: a putative prover can set an arbitrary $T_1 = A^c B^d$ (for arbitrary $c, d$). However, in that case, the verification equation is $A^{ckt-u}B^{dkt+1} = 1$; this can be satisfied only if $dkt+1 \equiv 0$ (but to set the value $d$ appropriately, the prover would need to know $k$); otherwise, the prover would know that $x = (ckt-u)(dkt+1)^{-1}$, and so knowledge of $k$ (and $c, d$) would imply knowledge of the discrete log.

$\endgroup$
10
  • $\begingroup$ Thanks for the reply. I would like to ask, in $𝐻_x 𝐾_y = 𝐶 𝐺^{-m} $, why need to use verifier's public key? In this case everyone can verify the proof because $K$ is the public key and everyone know it. Am I right? $\endgroup$
    – Jeff Lee
    Apr 11, 2020 at 17:58
  • 1
    $\begingroup$ @JeffLee: the idea is that the verifier is convinced (because she knows the prover does not know the dlog of $K$, and hence the pair $(x=r, y=0)$ is the only possible option. However, if she forwards the proof to someone else, then (if she knew $r$), she could have constructed a proof with any $m$. Or, were you looking for a construction where the proof could not be validated without knowledge of $k$? $\endgroup$
    – poncho
    Apr 11, 2020 at 20:04
  • 1
    $\begingroup$ @JeffLee: if the latter, just take the above proof, and encrypt it using $K$ as a public key. Only the verifier can read it, and if she tries to forward the decrypted version, well, the previous logic applies... $\endgroup$
    – poncho
    Apr 11, 2020 at 20:10
  • $\begingroup$ I am just thinking is it possible to use any other generator to replace K, seem it work too. $\endgroup$
    – Jeff Lee
    Apr 12, 2020 at 4:19
  • 1
    $\begingroup$ @JeffLee: $Hash( H^rK^s ) \ne Hash(H^rL^s)$ for a point $L \ne K$ and so, no, the verifier could not just change the $K$ used to another value $L$ $\endgroup$
    – poncho
    Apr 12, 2020 at 12:18

Your Answer

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

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