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.

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?
• 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. Feb 3, 2022 at 8:13