Score:1

Proof of knowledge of constant discrete log in the bilinear setting

cn flag

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.

Score:1
ru flag

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?

Mathdropout avatar
cn flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.