5
$\begingroup$

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 trap door function $g^{-1}()$.

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

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

$\endgroup$
  • $\begingroup$ how certain, exactly, are we that the implementation actually works? I was never able to convince myself that the code available on wikipedia was equivalent to the description given in HTLAS. $\endgroup$ – muhmuhten May 16 '13 at 2:01
  • 1
    $\begingroup$ in part, I'm puzzled by that code -- it seems to have suddenly appeared one day, without citation, ex nihilo, after the page remained unchanged for years, written in strange and arcane and almost obfuscated style. picking a line, the only sources google finds are that page and ... citations of that article. $\endgroup$ – muhmuhten May 16 '13 at 2:09
  • $\begingroup$ I just found that same Wikipedia page! I posted a very relevant question (which is basically the answer to your question) here: crypto.stackexchange.com/questions/52608/… $\endgroup$ – Ruben De Smet Oct 28 '17 at 17:52
1
$\begingroup$

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.

$\endgroup$

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.