# Proof of equality without involving Peggy after the fact

The setup is the following:

• Alice has a secret x
• Alice can generate proofs P1, P2, P3, ...
• Bob (an outsider) should be able to prove that any two proofs come from the same x without communicating with Alice

Does such a proving protocol exist?

This feels like a problem belonging to the realms of non-interactive zero-knowledge protocols.

I've been reading on Fiat-Shamir, Chaum-Pedersen and Schnorr protocols.

• Fiat-shamir: requires that Alice and Bob agree on two public values G and H beforehand
• Chaum-pedersen: This should work, but I need a quick confirmation to know whether this is what i'm looking for. Is it safe to have only two public values that Alice generates proofs for, even though she needs to generate more than two proofs?
• Schnorr: is meant to prove knowledge of x, but not equality of a proof of x so this doesn't work

Is there a simpler way than ZK or am I overthinking this? Many thanks in advance

Does such a proving protocol exist?

I'm not certain what each 'proof' is supposed to prove, and so I'm make a simple suggestion that appears to meet the end goal.

Suppose we have a pairing friendly curve of prime order; Alice picks a generator $$G \in G_1$$ and a generator $$H \in G_2$$ (which Bob doesn't need to know).

Then, for each proof, Alice selects a random value $$r \ne 0$$, and publishes the pair $$(rG, xrH)$$.

Then, when Bob wants to verify if two 'proofs' $$(X, Y), (Z, W)$$ corresponds to the same secret $$x$$, he first validates that $$X, Z \in G_1$$, and $$Y, W \in G_2$$, and that none of them are the neutral element. Then, he checks whether $$e(X, W) = e(Y, Z) \ne 1$$. If $$X = r_1G$$, $$Y = r_1x_1H$$, $$Z = r_2G$$, $$W = r_2x_2H$$ (which will always be true for some $$r_1, x_1, r_2, x_2$$), then:

$$e(X, W) = e(r_1G, r_2x_2H) = (e(G, H)^{r_1r_2})^{x_2}$$

$$e(Y, Z) = e(r_2G, r_1x_1H) = (e(G, H)^{r_1r_2})^{x_1}$$

These are equal only if $$x_1 = x_2$$

• Thanks for the amazing breakdown, Poncho! I'll read up on crypto pairings, but a couple of questions immediately jump up to my unintiated eyes: A) How would one find $G_1$ and $G_2$ from a curve and extract two generators from them? B) What is the e() function here? Commented Oct 2, 2022 at 7:09
• Answering my own question: e() is a pairing operation and BN254 is a good curve. Most programmatic implementations would have a very clear G1 and G2 in the implementation. See this for an example blog.cloudflare.com/circl-pairings-update Commented Oct 2, 2022 at 7:35
• Actually, don't use BN254. That's weak for this purpose. Use BLS12-381 Commented Oct 2, 2022 at 11:30