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.

  • $\begingroup$ What are $g_1$ and $g_2$? $\endgroup$
    – 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).

  • $\begingroup$ 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? $\endgroup$
    – curious
    Jan 4 '18 at 13:06
  • $\begingroup$ 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. $\endgroup$ Jan 4 '18 at 21:34
  • $\begingroup$ 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 $\endgroup$
    – curious
    Jan 5 '18 at 9:24
  • $\begingroup$ As with Pedersen commitment scheme, this only works if Alice does not know discrete logs and cant solve it while running the protocol. $\endgroup$ Jan 5 '18 at 10:11
  • 1
    $\begingroup$ 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$. $\endgroup$ 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.

  • $\begingroup$ That's is useful statement now the question is how $\endgroup$
    – curious
    Oct 6 '17 at 14:58
  • $\begingroup$ 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 $\endgroup$
    – curious
    Oct 6 '17 at 15:03
  • $\begingroup$ *$m_2=g_1^yg_2^{rt}$ $\endgroup$
    – curious
    Oct 6 '17 at 16:35
  • $\begingroup$ If the prover has sufficient comouting power he can obviously select b to match. Perhaps you want to define better what should be proved. $\endgroup$
    – Meir Maor
    Oct 6 '17 at 17:32
  • $\begingroup$ I edited the question $\endgroup$
    – 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 ?)

  • $\begingroup$ I do not think Schnoor scheme demonstrates what i need. At least I do not see anything close from your very vague answer. $\endgroup$
    – curious
    Oct 25 '17 at 16:07
  • $\begingroup$ 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? $\endgroup$
    – Hillfias
    Oct 26 '17 at 7:32
  • $\begingroup$ It does not depend at any scenario. I very clearly described my desired functionality $\endgroup$
    – curious
    Oct 26 '17 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.