# Ring Signatures: Why is the combination function easy to solve?

I'm reading Rivest's How To Leak A Secret and am on the part where they describe their signature scheme ("Generating a ring signature").

Why is computing $C_{k, v}(y_1, ..., y_r) = v$ easy? The computation seems to be "linear" or single-threaded, i.e. of the form $E_k(y_r \oplus E_k(y_{r-1} \oplus E_k(...E_k(y_1 \oplus v))))$. So let's say $r_i=s$ -- we require the value of $y_i$ to proceed with the computation (i.e. we can't continue to encrypt if we don't know its value), and so wouldn't we just be stuck trying all values of $y_i$ until we hit one that results in $v$ when the computation finishes?

Wikipedia also says that $C_{k, v}$ is trivially invertible given $r - 1$ parameters. I'm blanking out - why is this the case?

I did look at this answer but I didn't understand the line

Start again at 12 o'clock and calculate going counter-clockwise until you arrive at 6 o'clock.

How can you "go counter-clockwise" when all the computations counter-clockwise have inputs dependent on all previous computation? All of the XORs have the previous computation as input.

Sorry if I've made any gaffs, this is my first *Exchange question.

• Does reading this question make it understandable? – Ruben De Smet Aug 10 at 8:11
• It does, thank you! – tusing Aug 10 at 17:05
• I think there may be a bug in that OP @Ruben. For some pre-computed random value $v'$, the full formation of $v$ is: $$v = H(... \oplus H(y_s \oplus H(y_{s - 1} ...)))$$ $$= H(... \oplus H(v'))$$ Following: $$v' = y_s \oplus H(y_{s - 1} ...)$$ $$h = H(y_{s-1} ...)$$ $$v' = y_s \oplus h$$ $$y_s = v' \oplus h$$ which works. But OP is defines $h = H(y_s ...)$ - not $H(y_{s-1}...)$. So their full computation looks like: $$v = H(... \oplus H(y_s \oplus H(y_{s} \oplus H(y_{s -1} ...))))$$ which doesn't match the algorithm RST describes (ring backtracks on $y_s$). – tusing Aug 10 at 17:26
• That's an amazing attention to detail there, have a vote. I'll edit the question to read $\mathcal{H}(y_{s-1})$. Could you confirm that I made the right edit? It's a real index madness. – Ruben De Smet Aug 11 at 9:10
• Thanks, that looks good! – tusing Aug 12 at 12:32

I think I might have a potential solution, anyone care to confirm this? Let's take an example with 5 public keys (including ours). Let's assume our $s = 3$.

Let's borrow from that previous Stack Overflow post. Let's define a left var as

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

and we know that

$$z = r = E(E(l \oplus y_4) \oplus y_5))$$

Now let's start decrypting $z$:

$$D(z) = E(l \oplus y_4) \oplus y_5$$ $$D(z) \oplus y_5 = E(l \oplus y_4)$$ $$D(D(z) \oplus y_5) = l \oplus y_4$$ $$D(D(z) \oplus y_5) \oplus y_4 = l$$

We've solved for $l$! Solving for $y_s = y_3$ is easy now:

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

$$D(l) = E(E(v \oplus y_1) \oplus y_2) \oplus y_3$$

$$D(l) \oplus E(E(v \oplus y_1) \oplus y_2) = y_3$$

And then we just do $g^{-1}(y_3)=x_3$, giving us our full signature.