Is this a safe way to prove the knowledge of an ECDSA Signature?

Question

I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it. 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$

So what is done to prove the knowledge of the $s$ part from the signature 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'$

Is this process vulnerable to forgery? Are there other known proof of signature knowledge for ECDSA signatures?

Answer 1

Any EU-CMA-secure signature is indeed a proof of knowledge of either a signature of this document or the private key. So, what you have done is using of second ECDSA signature as a proof of knowledge of discrete logarithm $s$. This completely makes sense, and I don't see any attacks on this. Between, as a proof of $s$ you can use also Schnorr signature or Schnorr NIZKP - it has a property of zero-knowledge in random oracle model (while DSA has no such property). Also, this idea of chaining signatures in this way is used in identity-based Galindo-Garcia signature, where 2 Schnorr signatures are chained.

But I can't answer you completely with a proof of security. At first, we need a rigorous formal model of attacker. This cryptographic primitive (proof of knowledge of signature) is not very widespread and seldom considered. Some works are devoted to this problem though, you can look here: https://link.springer.com/chapter/10.1007/978-3-540-47942-0_9# . Aldo, DSA signature has poor provable security in general (compare to Schnorr one). E.g., if you used Schnorr signatures in this way - I would exactly say that it's secure (because Galinda-Garcia identity-based scheme is provably secure). And, this solution could be safe on practice, but it lacks ZKP property for sure, so researchers mostly devote their efforts on other constructions, which provide ZKP.

Don't consider my answer as complete and accurate, this is just general abstract thoughts. I hope it will help you a bit.