# Mathematics behind the paper “how to leak a secret” for ring signature

I'm reading the paper "How to Leak a Secret" (Rivest, Shamir, Tauman; 2001).

On page 8/14, in chapter 3.4, the authors present the following "combining function":

$$C_{k,v}(y_1, y_2,\ldots,y_r) = E_k(y_r \oplus E_k(y_{r−1} \oplus E_k(y_{r−2} \oplus E_k(\ldots \oplus E_k(y_1 \oplus v)\ldots)))) .$$

Is there any explanation for why this function satisfies the second one of the three properties listed on the previous page:

1. Efficiently solvable for any single input: For each $$s, 1 \leq s \leq r$$, given a $$b$$-bit value $$z$$ and values for all inputs $$y_i$$ except $$y_s$$, it is possible to efficiently find a $$b$$-bit value for $$y_s$$ such that $$C_{k,v}(y_1, y_2,\ldots,y_r) = z$$.

A concrete example of how to solve it would be ideal.

From the paper, $$E$$ is a cipher, i.e., $$E_k$$ is a permutation. That is, given a secret key $$k$$, one can compute both the encryption $$y=E_k(x)$$ (for any $$x$$) and the decryption $$x=E^{-1}_k(y)$$ (for any $$y$$). Therefore, if you know $$z$$ and all but one $$y_i$$, you can pick a $$v$$ (which equals $$z$$ in the context of ring signature) and get the missing $$y_s$$ by computing the XOR of $$s-1$$ $$E_k$$ encryptions starting from "inside" of the $$E(E(...))$$ expression and $$r-s$$ $$E_k^{-1}$$ decryptions starting from "outside". For instance, if $$r=3$$ and $$s=2$$, then $$y_2=E_k(y_1\oplus v)\oplus E^{-1}_k(E^{-1}_k(z)\oplus y_3)$$.