O(1) EC Linkable Ring Signature Without Group Manager

Question

I'm looking for a practical example for creating an EC Ring Signature, very much at the level of detail as found in the CryptoNote Whitepaper but with O(1). I saw Short Linkable Ring Signatures for E-voting, E-cash and Attestation, but I'm not sure about two things:

1. Does it actually require a group manager or did I miss something? I need a solution where the signer sets-up the signature with no need for a trusted party.

2. The paper's Appendix A doesn't include a setup for the SLRS, and I don't trust myself with an implementation, I prefer something that went through some public review. I'm looking specifically for EC, not RSA.

I'd appreciate any help in either clarifying these issues about the above paper or alternatively suggesting some reviewed source for another implementation.

Answer 1

So, non-interactive zero knowledge proofs, including the ring signature zero-knowledge proof that you want, are impossible in the standard model, as shown by Goldreich and Oren somewhere on this stylish webpage.

So this means we need some trusted party like the group manager, or we need some trusted setup in order to generate a common reference string, or we need to model hash function as random oracles in order for security definitions to hold. I linked an article in the comments (here it is again... :D) that gives constant size ring signatures, which also offers membership revocation (which might be something useful to you depending on the use case).

The other option at this point in time is using a signature scheme in which the signature grows logarithmically with the size of the group over which it is signed -- even with constant size ring signatures, the verification may be O(n) in which case a group of 1 million would be infeasible. If log(n) sized signatures are okay, then something like this could be used, which doesn't need a trusted setup/group manager (the protocol is secure even if the CRS is generated maliciously).

I don't think you're going to be able to find an actual peer reviewed implementation of something like this though -- even Monero, a cryptocurrency which is worth ~$ 400 million at the moment, hasn't been peer reviewed, except kind of by this paper, which reviews the blockchain metadata more than the code anyway...

If privacy of resources is really necessary, and proof generation time doesn't matter too much, looking into using something like libsnark might be your best bet, as their signatures are ~288 bytes, I think (+ ~700 byte verification key). The time taken to generate a proof can be upwards of a minute, though.