I have several problems approaching the following problem: Let's assume that we have Alice, Bob and Cathy. Alice wants to present a message to Cathy, showing her that someone else has signed it (Bob), but without disclosing Bob's identity. She needs to show that the signature does not belong to her.

If we use blind signatures. then Alice could be the one who signed it, so we cannot be sure that it was signed from someone else.

By using group signatures, more or less we have the same problem, sure there's the group manager who could certify that, but we break the anonymity...

With ring signatures, we have the needed anonymity, Bob presents a message having himself along with others, however, if you want to make it efficient, the ring has to be quite small.

Any other ideas?

  • $\begingroup$ Basically, Alice would have to prove that she does NOT know the secret key used for signing. And unless I'm missing something, that should be impossible, because the instance of Alice that knows the key can always simulate an instance of Alice that has less knowledge. $\endgroup$ – Maeher Feb 2 '14 at 18:18
  • $\begingroup$ simple: just have Alice not be part of the (signature) group. $\;$ $\endgroup$ – user991 Feb 2 '14 at 21:50
  • $\begingroup$ To Maeher: If you're thinking with blinding, then yes that's the loophole that I see. To Ricky Not having Alice in the signature group would mean that if you have n use users, then you need to generate n groups, which for large number of users is not practical, as you might have users joining and leaving. $\endgroup$ – absinthe_minded Feb 3 '14 at 0:06
  • 1
    $\begingroup$ How about a zero-knowledge argument of knowledge of a signing key for one verification key and a signature for a different verification key? $\;$ $\endgroup$ – user991 Feb 3 '14 at 0:18
  • 1
    $\begingroup$ Your problem could be addressed by including an identity in the keys and replacing "different verification key" with "verification key for a different identity". $\:$ Additionally, I now realize that the protocol would need to be concurrent zero-knowledge. $\:$ (Although I would normally recommend replacing stage 2 of that paper's protocol with something that has a ppt knowledge extractor, such a modification is not necessary in this case.) $\;\;\;$ $\endgroup$ – user991 Feb 3 '14 at 1:00

Your Answer

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

Browse other questions tagged or ask your own question.