Linkable ring signature scheme

Question

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?

Answer 1

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.

Answer 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.