Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$ ?

share|improve this question
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. – muhmuhten May 16 '13 at 2:01
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. – muhmuhten May 16 '13 at 2:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.