# Ring Signature Verification

When a receiver is verifying signed message, it has all the public keys of possible senders.

Sender

$S(M)$ denotes signed message $m\in M$, private key $s$, and public key $p$ giving us:

$(m, \ s_i, \ p_1, \ p_2 \ , ... , \ p_n)$

$(m, \ p_1, \ p_2, \ ..., \ p_n )$

I am a little bit confused. How are these keys reconciled?

When validating the message, does the receiver try each public key one by one?

If the receiver has to conduct an exhaustive search, does it mean the receiver knows the exact public key used to validate the signed message?

Does knowing the public key mean knowing the owner of the private key?

How can a receiver know who signed the message?

• There was an extensive edit by @floorcat (thanks for that), piskil, can you verify that your question is still as intended? – Maarten Bodewes Feb 16 '17 at 22:49

I am a little bit confused. How are these keys reconciled?

Since this question is more or less specific to the ring signature system. I will assume you are talking about ring signatures as proposed by Rivest, Shamir and Tauman in 2001.

I took the liberty to reorder your questions a bit.

Does knowing the public key mean knowing the owner of the private key?

Rivest et al. use standard RSA or Rabin keys, so every private key has an associated public key, just like in classical public key cryptography.

How can a receiver know who signed the message?

They cannot know; this is the whole point of ring signatures! The only thing that the receiver learns, is that the signature was crafted by one in the ring: $\{p_1, p_2,\dots, p_n\}$. The receiver can verify that the signature was generated by one of the associated private keys, without figuring out which one it was.

When validating the message, does the receiver try each public key one by one?

If the receiver has to conduct an exhaustive search, does it mean the receiver knows the exact public key used to validate the signed message?

The receiver does not try each and every public key once; they combine all public keys in the ring to verify the integrity of the signature.

They get combined in a ring equation:

$$C_{k,v}(y_1,y_2,\dots,y_n)=v$$

where $y_i$ is the result of a public key operation with public key $p_i$. This equation is constructed as such, that the signer needs access to at least one private key to make it satisfied.

Let me know if you want me to go more in detail here. I got to this question while studying ring signatures myself :-)