OR Proofs (Disjunctions)

What if you want to prove: "I know x for y = g^x OR I know x' for y' = g^x'"?

A naive approach reveals which side you know. We want to hide it.

OR composition (Cramer, Damgård, Schoenmakers 1994):

Prover knows x for y. Wants to claim "I know x or x'" without revealing which.

For the side they DON'T know (say y'): SIMULATE the proof.
  Pick random c', z'. Compute r' = g^z' * y'^(-c').
For the side they DO know (y):
  Pick random k. Compute r = g^k.
Compute the global challenge c = hash(r, r', m).
Compute c_known = c XOR c'  (or: c = c_known + c_simulated mod something).
Compute z = k + c_known * x.

Send: (r, r', c_simulated, z, z_simulated).

Verifier:

c = hash(r, r', m)
c_known = c XOR c_simulated  (or c_known = c - c_simulated)
Check: g^z == r * y^c_known   AND   g^z' == r' * y'^c_simulated

Both branches verify, but verifier can't tell which one used the real witness.

This generalizes: ring signatures (1-of-N), threshold signatures, anonymous credentials.

Example use:

• "I'm a member of this group of 100" — without revealing which member you are.
• Monero (the privacy coin) uses ring signatures based on this idea.

Many ZK applications boil down to: "I know SOMETHING such that..." — and OR proofs are how you prove it without revealing what.