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.

I need an implementation of linkable ring signature, a ring signature which allows identifying whether two signatures belong to the same signer. It has important privacy-related applications, like e-voting, but unfortunately there seems to be no public implementation. So I'm going to roll my own.

The simplest method seems to me is described in this highly cited paper: http://eprint.iacr.org/2004/027.pdf . Is it a sane scheme? Are there any known vulnerabilities in it? Are there any standards for linkable ring signatures which describe a good way of doing it?

share|improve this question
3  
Welcome to Crypto.SE, sor.rge! Regarding your question about known vulnerabilities, have you done a literature search to look for follow-on work? Any published work that describes vulnerabilities in the scheme is likely to cite this paper, so a literature search should give you a better sense whether there are any known vulnerabilities and whether the scheme is state-of-the-art. –  D.W. May 28 '13 at 2:29

2 Answers 2

This may be way too late, but you could have a look at CryptoNote. It's designed for cryptocurrencys but should be suitable for your purposes. I think there is an implementation somewhere in the Bytecoin code.

share|improve this answer

After looking through some papers, I feel qualified to answer my question, for the record. The scheme works and I've found no evidence that it has been broken. A good review is given in "A survey of ring signature" by L. Wang, which contains a section on linkable signatures.

The technique used in Liu's 2004 paper from the question makes O(n)-long signatures, where n is the number of public keys. There are more recent schemes commonly called "short LRS", which produce O(1) signatures. However, all schemes that I saw require some kind of trusted party to be involved in the generation of key pairs. This defeats the purpose of LRS I think, and anyway is unsuitable for my applications. From my superficial understanding, in O(1) schemes the danger of chosen key attack is somehow greater, and has to be compensated by including this key managing authority.

As for real applications, I found one (unfinished?) implementation of the 2004 scheme, and that's it.

So I've implemented the 2004 scheme and a similar, but more efficient scheme by the same authors. It's here: https://github.com/sorrge/LSAG . Public domain. Not reviewed by anyone yet, so no promises of its security.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.