2
$\begingroup$

I am currently in the process of understanding ring signatures.

Now I have arrived at Linkable/Tracable Ring Signatures, however I don't really understand them.

Can someone explain me how the principle behind it works? An example would also be very helpful.

Thank you very much!

$\endgroup$

1 Answer 1

1
$\begingroup$

Consider a ring where each item in the ring is based on a hash of the prior item in the ring.

$i_0 = H(i_3)$
$i_1 = H(i_0)$
$i_2 = H(i_1)$
$i_3 = H(i_2)$

First, note that anyone can reconstruct the ring if they are told one of the $i$ values.

Second, note that if the hash is collision resistant, it should not be possible to form such a ring. This is because when creating $i_0$, you would need to "time travel" to find out what the value of $i_3$ is going to be.

If we used a "Chameleon hash" instead of a regular hash, we could construct such a ring. This is because a "Chameleon hash" can be controlled to produce the necessary output if a particular secret is known.

For example, the Chameleon hash for this answer Linkable Spontaneous Anonymous Group Signature is based on an EC Schnorr construction.

Being able to control the Chameleon hash requires knowledge of one of the private keys corresponding to one of the public keys in the ring. Therefore being able to construct a ring proves you knew one of the private keys. Once the ring is constructed, anyone can verify that the ring exists, but cannot tell where the ring was "joined together" through knowledge of a particular private key.

A linkable ring signature extends this concept by including a "key image". When you create the ring and use a particular private key to "join the ring", a key image is declared which is a public key corresponding to that private key, except on a different generator point.

Because of the EC discrete-log problem, no one can tell which public key in the ring the key image is based on. However, the construction of the ring effectively contains a "discrete-log equivalence proof", which verifies that the public key in the ring where the ring was joined must have shared the same private key with the declared key image.

Thus,

  1. The verifier can tell that at least one of the private keys corresponding to one of the public keys in the ring is known by the signer.

  2. The verifier knows that the key image is correctly formed to share the same private key that was used to join the ring.

This means that if the key image is ever seen again, the same private key must have been used to join this ring. There is no way to "fool" a verifier by creating a different key image when signing with the same private key twice, because the discrete-log equivalence proof proves the key image was created and declared correctly, and must correspond to the same public key in the ring where the private key was known.

$\endgroup$
4
  • $\begingroup$ my 2 (poor ;) ) cents with an actual "visual" example coming from current Monero implementation (i.e. CLSAG): getmonero.org/library/RingsCheatsheet20210301.pdf $\endgroup$
    – baro77
    Mar 17, 2022 at 7:27
  • $\begingroup$ Thank you very much for the detailed answer and I think that I am almost there. The only thing I do not completely understand is the generation of the key image. Maybe I lack on the understanding somewhere else? $\endgroup$
    – Bagheera
    Mar 17, 2022 at 10:18
  • $\begingroup$ @Bagheera If the public key in the ring that you know the private key for is $X=xG$ where $x$ is your private key, then your key image is $X' = xH_p(X)$ where $H_p()$ means to hash the contents into a new public key. When you sign, you declare $X'$, and the verification process proves that you knew the private key $x$ for the key image and that it is the same private key as for one of the public keys in the ring. If you ever signed using $x$ again in the future, you'd be forced to declare the same $X'$ key image again, so it will be clear to observers that you've signed twice. $\endgroup$
    – knaccc
    Mar 17, 2022 at 14:22
  • $\begingroup$ Thank u very much! I think it is clear now. :) $\endgroup$
    – Bagheera
    Apr 11, 2022 at 12:22

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.