Zero knowledge proof of exponents

Assume a cyclic group $G=\langle g\rangle$ of order $q$ and $g_1,g_2$ are two generators of $G$. Alice computes and sends to Bob

$m_1=g_1^{a_1}g_2^{x_1}, a\gets R$ is a uniformly random element

$m_2=g_1^bg_2^{a_2x_2}, a,b\gets R$ are uniformly random elements

A malicious Alice selects $a_1 \ne a_2$ and $x_1 \ne x_2$ while a benign one chooses $x_1=x_2$ and $a_1=a_2$.

Is there a way to prove to Bob that in $m_1,m_2$: $x_1=x_2$ and $a_1=a_2$ in a zero knowledge manner? Recal that $a_1,a_2,b,x_1,x_2$ should be kept secret to Bob the verifier.

• What are $g_1$ and $g_2$? – fkraiem Oct 6 '17 at 13:18

On assumption $x_1 = x_2 = x$ and $a_1 = a_2 = a$, introduce linear polynomials over $F_q$: $X(z) = x z + \eta_x$, $A(z) = a z + \eta_a$, $B(z) = b z + \eta_b$. Consider two group elements: $g_1^{A(z)} g_2^{X(z)} m_1^{-z}$ and $g_1^{z B(z)} g_2^{A(z) X(z)} m_2^{-z^2}$. First element is a constant (zero degree in $z$) if and only if the assumption holds. Nothing unusual/new at this point yet. Second element is linear in $z$ if and only if assumption holds, and this might look like an extension of Schnorr protocol. Now evaluate polynomials at some $z$ chosen as a challenge and invoke Schwartz-Zippel lemma for a bound on soundness error. At last, Alice must not be able to solve DL in this group (computational soundness) and must not know linear relation with $g_1$ and $g_2$ (setup).

• Does $X(z)$ protect the value of $x$ to the verifier? the same for A(z) and B(z) for a and b. And if Yes how the verifier evaluates the polynomial without knowing x,a,b? – curious Jan 4 '18 at 13:06
• For $x$ and $X(z)$: it's the same as with Schnorr protocol: degree-0 coefficient $\eta_x$ is chosen by Alice at random from flat distribution over $F_q$, so distribution of $X(c)$ is flat and independent of $x$ for any fixed $z = c$ and for any secret $x$. Yes, the same for $a$ and $b$. Polynomials are evaluated by prover, just like as with Schnorr protocol. – Vadym Fedyukovych Jan 4 '18 at 21:34
• Alice is the prover so she knows all the secrets at the operated group. And how to solve discrete logs as well. She is the entity who sends $m_1$ and $m_2$. Bob does not and should not learn the secret values. It must only verify whether a_1==a_2 and x_1==x_2 in a zero knowledge manner without learning a_1,a_2,x_1,x_2 – curious Jan 5 '18 at 9:24
• As with Pedersen commitment scheme, this only works if Alice does not know discrete logs and cant solve it while running the protocol. – Vadym Fedyukovych Jan 5 '18 at 10:11
• Let me be specific: prover must not know some $e \in F_q$ such that $g_2 = g_1^e$ and must not be able to find some $d$ such that $g_1^d = g_r$ for a random group element. To be able to run this protocol, prover must know $a_1, a_2, x_1, x_2, b$ (witness). He would run his protocol if $a_1 = a_2 \land x_1 = x_2$. – Vadym Fedyukovych Jan 6 '18 at 18:57

You are asking to prove the existence of a,b,x which satisfy both equations. For any such triplet it is easily verifiable, and therefore the problem is in NP, and therefor there is a zero knowledge proof.

• That's is useful statement now the question is how – curious Oct 6 '17 at 14:58
• But maybe that is not true because at $m_2$ the prover may find different $x$ and $a$ to satisfy the equation. I want the prover to prove that both $x$ and $a$ are the same at $m_1$ and $m_2$. He can choose any r,t,y and send $m_2=g_1^bg_2^{rt}$ instead. Recal that $a,b,x$ should be kept secret to Bob the verifier – curious Oct 6 '17 at 15:03
• *$m_2=g_1^yg_2^{rt}$ – curious Oct 6 '17 at 16:35
• If the prover has sufficient comouting power he can obviously select b to match. Perhaps you want to define better what should be proved. – Meir Maor Oct 6 '17 at 17:32
• I edited the question – curious Oct 7 '17 at 6:41

Aren't you curious!

I don't fully grasp why you designed your constraints the way you did. Either

• you were given m1 and m2 and you wonder if it's possible to verify a1 = a2 and x1 = x2 in a ZK manner. In that case I won't answer your question but suggest looking towards Schnorr's scheme(s).

• Or I can imagine the following scenario:

P knows a secret x1. In a first phase of ZKP (signing in), P proves knowledge of x1 with a witness computed from some random element a1.

On later notice, before executing some important actions, the verifier/server V would like to know if P isn't being a victim of session hijacking/XSS/CSRF or whatever. So it'll ask again for a ZKP of x2.

Of course you want x1=x2 to assert P still knows the secret/pass and in the same way, P will commit to some certain value derived from some random element b.

But, in case the password has been compromised/ could be retrieved in some way, you also want to assert that P still knows the random element a1, used in the first ZKP.

In that case, P can first do a ZKP to prove knowledge of a1, and another to prove knowledge of x.

Schnorr's scheme uses the discrete logarithm as you do, to prove knowledge of exponents. Except there's only one generator.

Please provide some feedback, I'm not at all satisfied with my "answer" and I'm not confident in my precise understanding of your question (do want a ZKP of exponents ? Or a ZKP for this particular setup ? Why this setup ? Are you forced to work with such constraints or does this reside in some bigger picture ? I like context :) Or maybe you're just curious ?)

• I do not think Schnoor scheme demonstrates what i need. At least I do not see anything close from your very vague answer. – curious Oct 25 '17 at 16:07
• Well that depends which scenario we're in. Do you need to have two generators and messages m1 and m2? Or is the second scenario I'm proposing closer to the reality? – Hillfias Oct 26 '17 at 7:32
• It does not depend at any scenario. I very clearly described my desired functionality – curious Oct 26 '17 at 7:49