# 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 '18 at 8:11
• 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 '18 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 '18 at 9:10

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.

• yes, you're right – Mikhail Koipish Dec 8 '18 at 13:22

You can "go counter-clockwise" because XOR and symmetric encryption E are both invertible functions.

Specifically, you have an equation $$C_{k,v}(y_1, ..., y_r) = v$$. You know only $$s-th$$ private key, right? so you can invert only $$y_s$$ (find $$x_s$$ so that $$g_s(x_s) = y_s; here$$g_i(x) means encryption of $$x$$ with $$i$$-th public key). So, by the algorithm, you choose just random $$x_i$$ for all $$i \neq s$$, and set $$y_i = g_i(x_i)$$. But it's not for $$y_s$$, which you will find from the equestion: $$C_{k,v}(y_1, ..., y_r) = v.$$ Worth to note, that in this equasion you know all variables (all $$y_i$$, $$v$$, $$k$$) except $$y_s$$. How you can solve it? You understand that it's simple in a forward direction to evaluate the function $$C_{k,v}(y_1, ..., y_r)$$, unless you comes to a position $$s$$, where you have:

$$y_s \oplus E(y_{s-1} \oplus ...) = y_s \oplus V_1,$$ where $$V_1$$ is some easy calculated value.

Then, to find which value should the last expression equal, you need to evaluate that our equation ($$C_{k,v}(y_1, ..., y_r) = v$$) "from another end", or "counter clockwise". We have: $$E(y_r \oplus X_r) = v,$$ where $$X_r$$ stands for $$E(y_{r-1} \oplus E(y_{r-2}...))$$. Could we find $$X_r$$? Sure, because XOR is invertible, and encryption $$E$$ is invertible too: $$X_r = E^{-1}(v) \oplus y_r.$$ Then, having $$X_r$$, you could solve the next equation $$E(y_{r-1} \oplus X_{r-1}) = X_r$$ in the same way. We repeat this "inverting of $$C_{k,v}$$" until we come to a position $$s$$. Now, combining results of "clockwise" and "counter-clockwise" evaluations, we have a fixed equation: $$E(y_s \oplus V_1) = X_s.$$ Not worth to say that it's easy to solve. When you find $$y_s$$, you will find $$x_s$$ by reverting $$g_s$$, thanks for you having the secret key.