I'm looking for a protocol in which a Prover transforms a RSA signature $\sigma$ on a message $m$ that verifies under a public key $vk$ into a NIZK proof of knowledge, $\pi$ of that signature. A verifier should then be able to verify that the prover saw a signature for that message and that the signature would have verified under the public key, $vk$.
The protocol has three parties: a signer, a prover and a verifier. The signer is the only party that knows the signing key $sk=d$. The signer is not aware the protocol is being run and just sends signatures to the prover.
We assume the public key $vk$, message $m$, and $\pi$ are all public, the original signature $\sigma$ is known to the prover, but is kept secret from the verifier. The verifier should not be able to learn the signature $\sigma$.
The purpose of this protocol is to create a public transparency log of signatures and messages that can be audited without leaking the actual signatures and presenting the risk of an attacker replaying these signatures. Unlike this
Below I provide my draft of such a protocol:
RSA Public key: $vk=(e, n)$; RSA Signing key: $sk=(d)$; Hash function: $y \gets h(x)$
Signer receives message $m$ and computes the RSA signature:
$\sigma \gets h(m)^d \mod n$ and then transmits $(\sigma,m)$ to the Prover.
Prover on receiving $(\sigma,m)$ computes $\pi$ via the following steps:
$$r \xleftarrow{\\\$} \mathbb{Z}_n^* \phantom{\mod n}$$
$$w \gets r^{e} \mod n$$
$$\pi \gets \sigma r \mod n \equiv h(m)^d r \mod n$$
and publishes $(\pi, w, m)$
Verifier on learning $(\pi, w, m)$ verifies these values under the verification key of the signer, $e$.
If computed honestly by the prover $\pi^e$ should be: $\pi^e \mod n \equiv
(h(m)^d r)^e \mod n \equiv (h(m) r^e) \mod n \equiv h(m) w \mod n$$
...so to verify the verifier checks that
$$ \pi^e \mod n \stackrel{?}{=} h(m) w \mod n$$
Since $r$ is randomly chosen it functions like a blinding factor hiding $\sigma$ from the Verifier. An adversary A that can recover $\sigma$ from $(\pi, w)$ can be used to invert the function RSA on $w$ by choosing $\pi$ randomly, getting $\sigma$ and the dividing $\sigma$ from $\pi$ to learn $w^d$.
Edit: As pointed out by https://crypto.stackexchange.com/users/452/poncho in their answer, my draft protocol is very insecure. Do not use.
Questions:
- Is the above scheme actually secure i.e., can the Prover construct a $\pi$ which the Verifier will accept without having seen the signature and can the Verifier recover $\sigma$ from $\pi$?
- If it is secure what is the name of the paper from the 1990s that
first did it?
- What other approaches are there?
Unlike Proving the possession of signature in zero-knowledge we aren't interested in privacy. It is perfectly fine if $\pi$ can be linked to a particular $\sigma$ by a party that already knows $\sigma$.
This problem seems very similar to GQ signatures but GQ signatures assume the prover is generating the message and binding it to their identity where their identity is also a signature.
