4
$\begingroup$

Currently I have a DLP as following, $y = g^x \bmod p$, I can easily construct a proof of knowledge by using Schnorr Protocol.

But I would like to put it a a system of 2 parties with public key and private key as following.

  • Prover has private key $x_p$ and public key $y_p = g^{x_p}$
  • Verifier has private key $x_v$ and public key $y_p = g^{x_v}$

Is it possible i can construct a proof of knowledge that prover knowing $x$ in $y = g^x \bmod p$ and only can be verified by designated verifier with public key $y_p$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I"m sure you want that the Verifier public be called $y_v$. So, are you asking about a designated verifier with a public key $y_v$ and the private key $x_v$? $\endgroup$ – Crypto Learner Apr 13 '20 at 1:21
  • 1
    $\begingroup$ Isn't this already covered in at least one of my two constructions in crypto.stackexchange.com/questions/79862/… ? $\endgroup$ – poncho Apr 13 '20 at 2:56
1
$\begingroup$

I try to add a trap door commitment to a non-interactive schnoor protocol. Trap door protocol provide a back door for selected verifier by public key.

Cryptography setup

  • $y=g^x$ where $r$ is the secret to prove
  • $y'=g^{x'}$ where $y$ is the public key of the verifier and $x'$ is the private key of the verifier

Construct the proof

  • Pick $w$, $r$, $d$ randomly in $Z_q$
  • $c=g^wy'^r$
  • $t=g^d$
  • $h=hash_q(c, t)$
  • $s=d + (h + w)x$
  • $(w, r, t, s)$ is the proof and send to verifier

Verification

  • $c=g^w y'^r$
  • $h = hash_q(c, t)$
  • verify $g^s = ty^{h+w}$

Simulating Transcript

  • Pick $\alpha$, $\beta$ randomly in $Z_q$
  • $c=g^\alpha$
  • $t=g^sy^{-\beta}$
  • $h=hash_q(c ,t)$
  • $r = (\alpha - w)(-x')$
  • $w = \beta - h$
  • $(w, r, t, s)$ is the transcript

Because of the trap door commitment, designated verifier ($y'$) can create a valid proof. But only the designated verifier know the proof is come from himself or prover. For others, they can't tell the proof is come from designated verifier or prover. Only designated verifier or prover know the proof is created by who. So only designated verifier can be convinced in this protocol.

So this protocol, can convince designated verifier knowledge of r in Schnorr Protocol. The verifier can't transfer the proof to others and he is the only one can be convinced.

Improve this answer
$\endgroup$
4
  • $\begingroup$ from the paper: "Efficient Strong Designated Verifier Signature Scheme", Shahrokh Saeednia, Steve Kremer, and Olivier Markowitch ??? $\endgroup$ – Crypto Learner Apr 14 '20 at 14:25
  • $\begingroup$ @McFly Yes, but they are using undeniable signature with trapdoor commitment, i change it to schnorr protocol with trapdoor commitment to have similar effect. But instead of proving the signature, it prove the knowledge of x only. But I am not sure I am modifying it correct, as I am very new to crypto, please comment to it thanks. $\endgroup$ – Jeff Lee Apr 14 '20 at 14:30
  • $\begingroup$ @McFly I reference mainly from "Designated Verifier Proofs and Their Applications", Markus Jakobssonl Kazue Sako and Russell Impagliazzol, But i also read "Efficient Strong Designated Verifier Signature Scheme" too. Many thanks. $\endgroup$ – Jeff Lee Apr 14 '20 at 14:31
  • $\begingroup$ This is not my question, but I would doubt this solution. This protocol is very similar to an OR-proof. $\endgroup$ – Vadym Fedyukovych Apr 14 at 11:32
0
$\begingroup$

Ok, let's try without the Prover's keys.

  1. The Prover chooses $k,t$ and commits to a random value $k$, and calculates $c= y_v^k$;
  2. The Verifier sends a $m$ chosen at random;
  3. Prover calculates $r=h(m,c)$; and $s = kt^{-1} -rx$. Finally sends $(r,s,t)$ to the Verifier.
  4. Verifier can check if $h(m,(g^sy^r)^{tx_v} \bmod p) = r$
Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see how that works - given $t$ and the public key $y_v$, anyone can recover $g^r$. $\endgroup$ – poncho Apr 13 '20 at 2:52
  • 1
    $\begingroup$ @poncho you're right. I was trying get an idea similar to Jakobsson Designated Verifier Proofs. $\endgroup$ – Crypto Learner Apr 13 '20 at 3:33
  • $\begingroup$ Here is @poncho work, crypto.stackexchange.com/questions/79862/… $\endgroup$ – Jeff Lee Apr 13 '20 at 4:21
  • $\begingroup$ @poncho, can you please check my revised answer? $\endgroup$ – Crypto Learner Apr 13 '20 at 4:29
0
$\begingroup$

Designated verifier is an OR proof against verifier public key. It goes like "either something holds, OR I know verifier' secret". OR is the well-known "add two challenges" scheme of Schoenmakers et al.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is designated verifier mean the verifier can also create same transcript so he can't transfer the proof to others and only selected verifier can verify the proof? How OR-proof have a relationship with it? Thanks. $\endgroup$ – Jeff Lee Apr 13 '20 at 12:29
  • $\begingroup$ @Vadym, this OR is what you need to make the protocol resistant to an adversary who enters the Verifier device and see s/he private keys; or resistant to a Verifier that was owned by an adversary and that publish h/is/er keys and the proof transcript. That is, this is what we need to make the proof untransferable. But Jeff is not demanding it... B.T.W., my construction is untransferable. $\endgroup$ – Crypto Learner Apr 13 '20 at 13:04
  • $\begingroup$ Verifier can send/transfer the proof to a 3rd party, but how would that party believe the original statement holds? It could be just the second OR part that holds. $\endgroup$ – Vadym Fedyukovych Apr 13 '20 at 13:07
  • $\begingroup$ @VadymFedyukovych this is a good point. When I first read the Jakobsson paper "Designated Verifier Proofs and Their Applications" this was a concern. But look: up to the Receiver's private key leak, s/he doenst have any reason to think s/he has a dual personality, that is, forging a proof to cheat him/herself. $\endgroup$ – Crypto Learner Apr 13 '20 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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