Suppose Alice has a verifiable (message, signature) pair from Cedric, who would not cooperate and routinely uses an algo (ecdsa, eddsa, rsa, or insert yours here) to sign messages.

Alice wants to interactively prove to Bob she has that (message, signature) pair with the valid signature, obviously. It doesn't have to be "zero-knowledge" - she might divulge bits and pieces, but it shouldn't be less hard for Bob to recover complete (message, signature) pair than for Alice to forge the signature altogether.

Obviously, Alice and Bob both have Cedric's public key. I look for an interactive procedure and stochastic proof. Is it even achievable at present point?


1 Answer 1


This is a NP statement, so there is a zero-knowledge proof for it (as there is a zero-knowledge proof for every NP statement). The exact form of the proof will depend on which signature algorithm is chosen, and what is already known to Bob (e.g., does Bob know the message? can it be disclosed to him safely?).

If you can choose the signature algorithm, and you can assume Bob knows the message or are willing to disclose the message to Bob, then you can find signature algorithms that allow very efficient and simple zero-knowledge proofs. For instance, you can use RSA with full-domain hashing, and the following ZKP: https://crypto.stackexchange.com/q/16015/351

  • $\begingroup$ Thanks. As per my question... "which signature algorithm is chosen?" This is not a limitation; I am happy to consider an algo of your choice. I prefer EdDSA (aka Ed25519 algo). "does Bob know the message?" As long as he doesn't know the signature, again: "it shouldn't be less hard for Bob to recover complete (message, signature) pair than for Alice to forge the signature altogether." $\endgroup$
    – wick
    Nov 22, 2022 at 9:54
  • $\begingroup$ I am not entirely sure about "safety" in "can message be disclosed to Bob safely?". If we have 25 Bobs, to whom that one message in disclosed in private, what's the point of privacy requirement?? $\endgroup$
    – wick
    Nov 22, 2022 at 9:58
  • $\begingroup$ @wick, see edited answer $\endgroup$
    – D.W.
    Nov 22, 2022 at 18:45
  • $\begingroup$ Is there any such scheme for EdDSA? $\endgroup$
    – wick
    Nov 27, 2022 at 14:43
  • $\begingroup$ @wick, that sounds like a good question to ask on Crypto.SE. I've tried to answer the question that was posted. This site doesn't work well for back-and-forth or interactive discussions, so I encourage you to specify your requirements clearly when you ask on Crypto.SE. $\endgroup$
    – D.W.
    Nov 28, 2022 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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