1
$\begingroup$

I'm trying to understand the concept of ring signatures. So as it seems there is a way where you have a group of public keys which can be signed by only one private key of that group without revealing which private key was actually used. On the other hand you have a keyImage to prevent a double spend, so that the observer can be sure that this specific private key was not used yet.

What I don't get is how this keyImage is produced and verified.It is somehow derived from the private key and hashed in a way that it can't be reverse engineered. But how do I know that a private key was in fact used for the keyImage? I mean I could just use a random keyImage to have its uniqueness.

So it must be linked somehow to the signature so that one can be sure it is really derived and hashed from the private key.Of course without revealing which private key of the group was used. So how is this linked together?

$\endgroup$
10
  • 1
    $\begingroup$ this question seems more suitable for monero.stackexchange.com imho ...and the "hash-signature" tag seems wrong $\endgroup$
    – baro77
    Oct 11 at 10:07
  • 2
    $\begingroup$ "keyImage" is not a standard cryptographic term. Thus the question should be stated with a reference to what "keyImage" means from a cryptographic standpoint. If the question is specific to Monero, I can migrate it there (they have at least one related question). However if the question's focus is on ring signature and whatever "keyImage" is (rather than on Monero specifics) it can be kept here, if clarified. $\endgroup$
    – fgrieu
    Oct 11 at 10:47
  • $\begingroup$ I totally agree @fgrieu. I have assumed the OP was thinking to cryptocurrency related stuff because of citing "double spend" in the question. Anyway better to give him opportunity to unambiguously clarify $\endgroup$
    – baro77
    Oct 11 at 12:20
  • 1
    $\begingroup$ @user3776738 got it! So, just a comment because I don't know the Shadowcash implementation: in Monero your doubt "But how do I know that a private key was in fact used for the keyImage?" is solved with a structure by which ring verification succeed only if the keyImage is built from privkey.... I wouldn't know how to describe it by words, but perhaps this could be useful to you: getmonero.org/library/RingsCheatsheet20210301.pdf (disclaimer: I'm the author of the cheatsheet) PS RingCT doesn't matter $\endgroup$
    – baro77
    Oct 11 at 14:21
  • 1
    $\begingroup$ @fgrieu ok, I'm going to try... just let me take some time, 'cause these are busy days of mines and the topic is a bit awkward to be summarized $\endgroup$
    – baro77
    Oct 12 at 12:43
2
$\begingroup$

Hoping to satisfy @fgrieu invite in comments, I try an answer coming from Monero's implementation. The source of these words is the cheatsheet I have written https://getmonero.org/library/RingsCheatsheet20210301.pdf while studying https://www.getmonero.org/library/Zero-to-Monero-2-0-0.pdf

I think the right thing is to start from non-interactive (in the Fiat-Shamir flavour) Schnorr signature for keys over elliptic curve. Let's quickly recap it.

Let's say $(x,X)$ is the private/public keys pair, where $X\triangleq xG$ with $G$ the generator point of the EC; $tx$ is the transaction/text/whichever stuff we need to sign; Signing $tx$ with $x$ means being able to generate a pair $(c,r)$ such that:

$H(tx, rG + cX)=c$

where $H$ is an hash (no matter here which one) and $c$ and $r$ are called "challenge" and "response", with the terms coming from the interactive schema. $c$ is obtained from a secret random unique $\alpha$ known only by the signer and never reused in two signatures, and the foregoing equality is equivalent to:

$rG + cX = \alpha G$

(btw, by substituting you get how $c$ is defined ;) )

So, looking at it from a bird view, we can say that verification of $tx$ signature by $x$ is a function of the signed stuff, the public key, the challenge and the response:

$f(tx, X, r, c)$

Ring signatures are about finding flavours of this schema with decoys, while still retaining just only one ACTUAL signer (from a technical point of view: needing many $X_i$ -let's say $n$- in verifying algo but single $x$ in signing algo); and all without coordination between involved key owners.

There are a challenge and a response for each $X_i$, so we have $c_i$ and $r_i$, however things are arranged so that from $c_i$ we can calculate $c_{i+1}$, with "overflow" when $i=n$ (here it is the "ring"), so:

$H(tx, r_{i}G + c_{i}X_{i})=c_{i+1}$ with $1 \le i \le n-1$

$H(tx, r_{n}G + c_{n}X_{n})=c_1$ with $i=n$

given we can regress from $c_n$ to $c_1$ the above conditions lead to the signature verification function:

$f(tx, X_i, r_i, c_1)$

But where does the "magic" come from? How is the arrangement made to have $c_i$ forming a closed chain in which given one challenge value you can calculate all the others (note we have chosen $c_1$ as special one, but that's really nothing special about it)? Well, thanks to these facts:

  1. if we indicate as $c_\pi$ the challenge associated to the ACTUAL signer, $c_{\pi+1}$ is calculated from a random secret $\alpha$ known only to the ACTUAL signer (does it recall anything? ;) );
  2. all other $c_i$ are calculated with the above chain formula;
  3. all $r_i$ are just random numbers, except $r_\pi$ wich is chosen so to let $c_{\pi+1}$ to respect the chain formula as well (even if it comes from $\alpha$)

And now eventually the Key Image $X^*$! A part from being advertised in the transaction to prevent double spending, it is also part of $c_i$ calculus, and again the $\alpha$/chain formula trick is used: and it holds only if Key Image $X^*$ is obtained in a very specific way, function of the private and public keys of ACTUAL signer.

That's why you cannot just choose a random still-unused one!

I understand this is only the main line of the reasoning, missing many details, but I hope you can find them in the cheatsheet with the help of these companion words (I guess for your needs you can care only about "Non-interactive (Fiat-Shamir) Schnorr", "SAG" and "bLSAG")

$\endgroup$
2
  • $\begingroup$ I accepted your answer, because it looks very detailed and I might understand it someday. Despite I'm not really understanding it to be honest. I will need to read through it a dozen times and do some research about the mathematical knowledge I'm lacking of. Maybe I will ask a new question based on your answer someday, if I don't get it. Thanks so far. $\endgroup$ Oct 13 at 11:07
  • 1
    $\begingroup$ if you are looking a more gradual introduction to the topic you can read chap 2 of getmonero.org/library/Zero-to-Monero-2-0-0.pdf (it's far from being complete as cryptography reference books, but I guess it's enough as background for your problem); chapter 3 is interesting as well but imho it's easy to get lost inside it. So the recipe could be: read chapter 2 as far as you need; then study the left column, the SAG and bLSAG rings and their notes on the right column of my cheatsheet, using my words here in SE as a tour guide. Wish you a good work! $\endgroup$
    – baro77
    Oct 13 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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