# Interactive ZKP of possession of a signed message

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?

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

• 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."
– wick
Nov 22, 2022 at 9:54
• 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??
– wick
Nov 22, 2022 at 9:58