ECDSA signature verifiable 1-way transformations

Question

Alice signs a message $m$ with her private key, yielding a signature ($r$,$s$).

I want to prove to someone else that I have this signature, but I don't want them to have the knowledge of what ($r$,$s$) is.

Is there a transformation I can apply to ($r$,$s$) to yield a new signature ($r'$,$s'$), such that someone who knows the original message and Alice's public key can see that it was derived from an original signature (without being able to reconstruct it)?

I'm thinking multiplying both the public key and signature components by some large number mod $n$. Am I on the right track or is this a fool's errand?

Answer 1

I think that I've found a good solution to this problem. In short terms it consists in generating an ECDSA signature using the point $R$ as generator, $s$ as private key and the result of $s*R$ as public key. So the $r$ part of the signature would be revealed but the $s$ part is still kept secret.

The usual ECDSA signature generation consists in proving that given a point $Qa$ where $Qa = da*G$ you know the number $da$ without revealing it.

To do so, the signing process works as following:

• step 1. The signer calculates a new point R such that $R = k*G$ and where $k$ is a nonce that needs to be changed for every new signature.
• step 2. The signer sets $r$ such that $r$ is the x coordinate of the point $R$
• Step 3. The signer calculates $m$ such that $m = HASH(message)$.
• Step 4. The signer calculates $s$ such that $s = k^{-1}(m+da*r)$
• Finally the signature are the values $(r,s)$

The verification of the signature's authenticity is verified by ensuring that:

• $R = s^{-1}m*G + s^{-1}r*Qa$

or that:

• $s*R = m*G + r*Qa$

Multiplying this equation by a big secret number $x$ as you suggested would result in having:

• $(xs)*R = (xm)*G + (xr)*Qa$

Although the verification of the equation is correct there are numerous traps that make it unsuitable to guarantee the authenticity without revealing $(r,s)$. For example if you reveal $R$ you know $r$ and if you know $r$ you can calculate $x$.

What you need to do is prove that you know a value $s$ such that $s*R = m*G + r*Qa$ and this without revealing $s$. This is exactly what we already did with $Qa = da*G$! The only difference is that instead of using the point $G$ as a generator we use $R$ and instead of generating a private key $da$ we use $s$

So the solution is to reveal:

• $m$
• $R$
• $Qa'$ such that $Qa' = s*R$
• $R'$ such that $R' = k'*R$ where k' is a nonce you generated
• $s'$ such that $s' = k'^{-1}(m'+r'*s)$ and where $m'$ is the hash of a message you want to sign with your derived private key $s$.

The verification is done in a two step process:

• step 1. verify that $Qa' = m*G + r*Qa$
• step 2. verify that $s'*R' = m'*R + r'*Qa'$

Answer 2

Use a zero-knowledge proof of knowledge (ZKPoK) of a value $(r,s)$ that is a valid signature. For instance, you might be able to adapt existing ZKPoKs for proof of knowledge of a discrete logarithm to this problem. Because it is zero-knowledge, you will know that it reveals nothing about $(r,s)$ and is not transferable.