Ring Signature - paper/code difference in trying to solve inverse trapdoor function?

Question

There is a paper on ring signatures and a python implementation of it here.

The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The next step is to find a unique $x_s$ for the signer's computed $y_s$. This is done by solving $x_s = g_s^{-1}(y_s)$

However, in the python example, to find the unique $x_s$:

s,u = [None]*self.n,random.randint(0,self.q)

s[z] = self.g(v^u,self.k[z].d,self.k[z].n)

It looks like it's generating a random integer $u$ as though $x_s$= $u$, then XOR'ing it with $y_s$ found in step 4, and then it applies the inverse trapdoor function $g^{-1}()$.

Why does the paper's implementation seem different from the one in the code?

That is, why $x_s = g^{-1}(y_s)$ or $x_s = g^{-1}(y_s \oplus x_s)$ ?

Answer 1

I'm taking some stuff from my relevant question at Rivest's ring signatures with hashes instead of symmetric encryption

---

Remarkably, Wikipedia's Python code does not use a symmetric encryption function ($E_k$, as in "How to leak a secret"), but a hash function ($\mathcal{H}$). Indeed, the encryption function does not need to be invertible, if we close the ring of the signature at the very last (take $v^\prime$ random, $m$ is the hashed plaintext):

$$ \mathcal{H'}(x) = \mathcal{H}(x||m)\\ v=\mathcal{H'}(y_{r} \oplus \mathcal{H'}(y_{r-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(v'))))\quad r-s\enspace\text{times}\\ h=\mathcal{H'}(y_{s} \oplus \mathcal{H'}(y_{s-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(y_1 \oplus v)))) $$

now notice that $$ v'=y_s \oplus h \Leftrightarrow y_s=v'\oplus h\\ x_s=g_s^{-1}(y_s) $$

which "closes" the ring.

My question is, why is the paper's implementation seem different than the one in the code?

To answer this question, I think we can only guess (or ask the authors). My guess would be that the authors didn't think of this trick, or that they didn't find it interesting enough to mention the possibility.

In my opinion, solving $C_{k,v}(y_1,y_2,\dots,y_3)=v$ by inverting $E_k$ (i.e., $E_k^{-1}=D_k$) seems more natural that "closing" the ring at the very last.

In terms of security, I think it has no influence on the proof in HTLAS, since they already modelled $E_k$ as a random oracle (and $\mathcal{H}'$ would be one too). I posted a new question about the security of this substitution.

That is, why $x_s = g^{-1}(y_s)$ or $x_s = g^{-1}(y_s \oplus x_s)$ ?

Don't get fooled here; what they denote in the code as u is what HTLAS calls $v$, so the sole thing they actually do in that step is $x_s=g_s^{-1}(y_s) = g_s^{-1}(v'\oplus h)$ (in my notation above).

---

The code on that page is very illegible to say the least, and may get removed soon. For future reference, here is the version in Wikipedia's history.