2
$\begingroup$

I have a protocol that operates in the malicious setting which involves parties sending each other group elements $u\in \mathbb{G}$ of a specific form (For example, these are messages of the form $u=g^{\alpha}\cdot h^{\beta}$ with generators $h,g\in \mathbb{G}$ and $\alpha, \beta \in \mathbb{Z}_q$ for some prime $q$).

Additionally, these parties attach non-interactive zero-knowledge proofs of knowledge that show that the group elements sent are indeed of that form (for instance, the group elements sent were not picked in an oblivious manner). So, if a party in the protocol sends $u=g^{\alpha}\cdot h^{\beta}$ it also has to attach $\pi_{g,h}(u)$ which is a ZKPOK that proves that $u$ is in the desired form.

In my attempts to prove soundness of a protocol, I am assuming in contradiction that there exists a PPT adversary $\mathcal{A}$ which breaks the protocol, and then I use $\mathcal{A}$ as a subroutine in a new PPT $\mathcal{B}$ which breaks an intractable problem (specifically, Discrete Logarithm in $\mathbb{G}$).

However, my problem is that I want $\mathcal{B}$ to use $\mathcal{A}$ in a black box manner, but I also want to use its "exponents" (discrete logarithms) $\alpha, \beta$ after running $\mathcal{A}$ in order to compute the discrete logarithm of an arbitrary group element $a\in \mathbb{G}$. However, $\mathcal{A}$ can choose $\alpha, \beta$ in any manner which $\mathcal{B}$ running $\mathcal{A}$ may not know.

How do I resolve this disparity?

What I had in mind, is to have $\mathcal{A}$ output $\alpha, \beta$ as part of its output, and reason that since $\mathcal{A}$ has to attach a ZKPOK of $\alpha, \beta$ when sending its group element(s), it computed $\alpha, \beta$ on its own and therefore it can also output them.

  1. Can I alter $\mathcal{A}$'s output in such a manner to fit my needs?
  2. Is there a different / better approach to solve the problem where I need access to discrete logarithms sent by a party controlled by a black boxed PPT ?
  3. Can anyone point me to a paper that entails a proof with a similar technique?

Many thanks in advance.

$\endgroup$
4
  • 1
    $\begingroup$ A proof of knowledge by definition allows extracting the witness. Why can you not simply do that in your reduction? $\endgroup$
    – Maeher
    Commented Oct 17, 2021 at 10:17
  • $\begingroup$ Because the ZKPOK is sent in my protocol as a NIZK, so I cannot use any "rewinding" techniques on $\mathcal{A}$ that extract the witness. I edited my question to emphasize that these are NIZKs. Thanks for the question. $\endgroup$
    – yacovm
    Commented Oct 17, 2021 at 12:02
  • 1
    $\begingroup$ If it's a PoK, you can extract. That's simply the definition of a PoK. With a NIZKPoK that generally works either by trapdooring the CRS or via a forking Lemma type extraction. $\endgroup$
    – Maeher
    Commented Oct 17, 2021 at 12:35
  • $\begingroup$ (1) can you please link to an example in a paper? (2) Is the method I described in the question something sound or not? $\endgroup$
    – yacovm
    Commented Oct 17, 2021 at 13:07

1 Answer 1

2
+50
$\begingroup$

You cannot modify $\mathcal A$ in this way. If you need $\alpha$ and $\beta$ for the reduction, then you will need to use a zero-knowledge proof of knowledge from which you can extract them. I understand that you want to use a NIZK. However, this actually isn't a problem. If you take a Sigma-protocol (3-round proof) for Pedersen commitments (which is essentially what you have here) and then apply the Fiat-Shamir transform to it, then the result is a non-interactive zero-knowledge proof of knowledge where you can extract the witness $\alpha,\beta$, in the random-oracle model. This is very standard. A tutorial on Sigma-protocols by Ivan Damgård can be found here. The fact that you can extract follows from the forking lemma for Fiat-Shamir by Pointcheval and Stern (see also this paper by Bellare and Neven on the forking lemma).

$\endgroup$
6
  • $\begingroup$ I think I understand what you're trying to say, however, what if the nested PPT (the adversaries PPT) has private input and as a result the requirements for applying the forking lemma do not hold? Perhaps I should then divide the adversary to two different algorithms - (i) one that produces the ZKPOK and (ii) one that receives the ZKPOK NIZK as input and does the rest , and then apply the forking on the first adversary? Is that something possible? $\endgroup$
    – yacovm
    Commented Oct 19, 2021 at 23:15
  • 1
    $\begingroup$ You always apply the knowledge extractor to the machine who generates the ZKPOK. This is typically important regarding previous messages sent. So, one looks at the "residual adversary" which is the adversary who has hardwired the state of the adversary up to that point. You actually don't care what happens after the ZKPOK since you never get there. $\endgroup$ Commented Oct 20, 2021 at 11:41
  • $\begingroup$ Thanks for your reply (and for the answer, of course). I'm not sure I fully understand. Can you perhaps point me to a paper (or a chapter in a book) where such residual adversary is described so I can learn from a concrete example? Many thanks in advance. $\endgroup$
    – yacovm
    Commented Oct 20, 2021 at 11:57
  • $\begingroup$ See Section 5.3 of eprint.iacr.org/2016/046.pdf. It describes a residual verifier used for proving ZK, and how the rewinding technically works. It's the same thing as you will need here. $\endgroup$ Commented Oct 21, 2021 at 7:17
  • $\begingroup$ Thanks for your reply. However, in my protocol, there is no commit-reveal going on - all parties send messages accompanied with ZKPOKs, and I am having trouble with proving soundness, not zero knowledge property. Section 5.3 deals with proving the zero-knowledge property. $\endgroup$
    – yacovm
    Commented Oct 21, 2021 at 8:20

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.