Is it easily provable by a third party that the key image used in a transaction is associated with the spent output without revealing the (P,I) pair?

Question

What I'm getting at is I'd like to know how the Monero network can know that a key image used in a transaction is not either forged (probably an easy answer) or created from a different output owned by the same wallet (perhaps a more technical, but hopefully straightforward, answer).

The transaction private key, x, probably signs the ring and the key image, right? My hunch is that the distinctive ring signature provides a way to check the math that P (the output public key) being spent is a ring member, and is also associated with I, the key image that's attached to the ring signature.

How does it work? I don't understand how the verification works without revealing the actual tx pub key being spent.

I've been reading other SE questions and answers here, here, and here. I haven't found an answer expressed in the way I'd like to understand it.

Answer 1

The signature verification algorithm will only return a "correct signature" result if P is equal to x·G (i.e. the real spent output's public key is derived from the output's secret spend key x) and if I is equal to x·Hp(P) (i.e. the key image I is derived from the output's secret spend key x).

If you can understand the algorithms on page 6 of MRL-0003, you will see that the Li elements check the public key and the Ri elements check the key image.

Signature algorithm:
--------------------
i ← 0
while i < numkeys do
  if i = s then
    k ← random Fq element
    Li ← k·G
    Ri ← k·Hp(Pi)
  else
    k1 ← random Fq element
    k2 ← random Fq element
    Li ← k1·Pi + k2·G
    Ri ← k1·I + k2·Hp(Pi)
    ci ← k1
    ri ← k2
  end if
  i ← i + 1
end while
h ← Hs(prefix + {Li} + {Ri})
cs ← h − ∑ci   (with i ≠ s)
rs ← k − x·cs
return (I, {ci}, {ri})


Verification algorithm:
-----------------------
i ← 0
while i < numkeys do
  L′i ← ci·Pi + ri·G
  R′i ← ri·Hp(Pi) + ci·I
  i ← i + 1
end while
h ← Hs(prefix + {L′i} + {R′i})
h ← h − ∑ci
return (h = 0 (mod q))

The verification algorithm will give a "correct signature" result when ∑ci is equal to Hs(prefix + {L′i} + {R′i}). For this to be true, {L'i} must be equal to {Li} and {R'i} must be equal to {Ri}.

For the decoy keys (i.e. i ≠ s) it is obvious that L'i = Li and R'i = Ri as they are generated with identical formulas.

For the real key (i.e. i = s):

    L's = Ls
<=> cs·Ps + rs·G = k·G
<=> cs·Ps + (k - cs·x)·G = k·G
<=> cs·Ps + k·G - cs·x·G = k·G
<=> cs·Ps = cs·x·G

    R's = Rs
<=> rs·Hp(Ps) + cs·I = k·Hp(Ps)
<=> (k - cs·x)·Hp(Ps) + cs·I = k·Hp(Ps)
<=> k·Hp(Ps) - cs·x·Hp(Ps) + cs·I = k·Hp(Ps)
<=> cs·I = cs·x·Hp(Ps)

So for the signature to be valid, the signer has to know the secret key x so that x·G = Ps and x·Hp(Ps) = I.