0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – jimmytann
    Oct 2, 2022 at 7:09
  • $\begingroup$ 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 $\endgroup$
    – jimmytann
    Oct 2, 2022 at 7:35
  • $\begingroup$ Actually, don't use BN254. That's weak for this purpose. Use BLS12-381 $\endgroup$
    – jimmytann
    Oct 2, 2022 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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