Proof of equality without involving Peggy after the fact

Question

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

Answer 1

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$