Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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. – Maeher Feb 2 '14 at 18:18
simple: just have Alice not be part of the (signature) group. $\;$ – Ricky Demer Feb 2 '14 at 21:50
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. – absinthe Feb 3 '14 at 0:06
How about a zero-knowledge argument of knowledge of a signing key for one verification key and a signature for a different verification key? $\;$ – Ricky Demer Feb 3 '14 at 0:18
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.) $\;\;\;$ – Ricky Demer Feb 3 '14 at 1:00

Your Answer


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

Browse other questions tagged or ask your own question.