1
$\begingroup$

Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ are of some prime order $p$.

For a trapdoor $s$, let $[g_1,g_1^s,\cdots,g_1^{s^N}], [g_2,g_2^s,\cdots,g_2^{s^N}]$ be the common reference string (although for some Snarks and polynomial commitment schemes, the public parameter does not contain $g_2^{s^i}$ for $i\geq 2$).

Given elements $a,b\in \mathbb{G}_1$, I would like to prove in ZK that I know a constant (as opposed to a larger degree polynomial) $\alpha$ such that $a^{\alpha} = b$. What's the most efficient way to do this?

A couple of ideas I had:

Idea 1:

  1. For a randomly generated element $a_2\in \mathbb{G}_2$ (the challenge), the Prover sends the element $b_2:= a_2^{\alpha}$.

  2. The Verifier performs the pairing check $\mathbb{e}(a,b_2) = \mathbb{e}(a_2,b)$

Idea 2

  1. The Prover proves in zero knowledge that he knows some polynomial $f(X)$ such that $a^{f(s)} = b$ (there are straightforward ways to do this, not too different from Schnorr's protocol for PoKs of discrete logs)

  2. The Prover sends the element $b_2:= g_2^{s^N\cdot \alpha}$ (which is not possible if $\alpha = f(s)$ for some non-constant polynomial $f(X)$).

  3. The Verifier verifies the proof sent in Step 1.

  4. The Verifier performs the pairing check $\mathbb{e}(a,b_2) = \mathbb{e}(b,g_2^{s^N}) $

Are there more efficient protocols that would do the job? I am not particularly fond of the idea of relying on a hashing algorithm that generates random elements of the group $\mathbb{G}_2$ as challenges.

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't think that either of these ideas is zero knowledge, as I don't see how the verifier would be able to produce valid transcripts without the co-operation of the prover.

On the other hand if we just do the Schnorr protocol for $\mathbb G_1$ without using the bilinear structure, that would seem to do the job. Is there a reason why this would not be acceptable?

$\endgroup$
1
  • $\begingroup$ Thanks. You are right, Schnorr's protocol should work without any modifications. I thought there would be a gap in the protocol because the blinding factor chosen by the Prover could be a non-constant polynomial. But if the polynomial $\gamma\cdot f(X) + c(X)$ is a constant for a committed blinding polynomial $c(X)$ and a randomly generated challenge $\gamma$, it would follow that the polynomial $f(X)$ is constant. No need for pairings or common reference strings. $\endgroup$ Feb 3, 2022 at 8:13

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.