4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What's your view on using bilinear pairings? These are in the CRS so need some 'trusted party' to generate parameters and then through away the material that would allow a malicious party to forge proofs, but yield constant size ring signatures? If so then you have at least this, if you're okay with ROM (necessary due to an impossibility result) as well as work on snarks, etc. $\endgroup$ – bekah May 7 '17 at 11:10
  • $\begingroup$ @bekah thanks, I'll first go over the article you linked $\endgroup$ – stromboli May 7 '17 at 11:37
  • $\begingroup$ @bekah Yes the article is very interesting. To further discuss I edited the question with a detailed description of my use case, and opened a chat room which, I hope, is more convenient then the comment system. The chat is at chat.stackexchange.com/rooms/58358/…, I hope to discuss with you over there. $\endgroup$ – stromboli May 7 '17 at 19:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Many thanks, not the answer I hoped for but it precisely addresses what I was looking for in a definitive way. The Groth-Kohlweiss paper is very interesting and I will try to see if it is feasible considering the ring sizes I was aiming at. $\endgroup$ – stromboli May 18 '17 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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