Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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. –  sreservoir 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. –  sreservoir May 16 '13 at 2:09
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.