1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$?

No, the scheme is not secure, in the sense that the Prover can construct a $\pi, w$ pair that validates.

All the Prover needs to do is select an arbitrary $\pi$ and compute $w = \pi^e \cdot h(m)^{-1}$.

$\endgroup$
1
  • $\begingroup$ Good eyes! You are correct, it is not secure. So this is why GQ signatures commit to the $T$ first and later have the challenge value $d$ sent over? The more I think about it, the more I probably just want GQ signatures $\endgroup$ Mar 16 at 21:04

Your Answer

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

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