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?

  • $\begingroup$ In theory it "easy" (in the complexity theoretical sense) to construct a zero-knowledge proof that proves knowledge of an ECDSA signature of a message (but this is probably not as practical as you're looking for). $\endgroup$ – SEJPM May 31 at 11:49
  • $\begingroup$ @SEJPM Should I go for another approach? $\endgroup$ – Jan Moritz May 31 at 11:57
  • $\begingroup$ What's the difference between $m$ and $m'$? $\endgroup$ – Aman Grewal Jun 1 at 16:39
  • $\begingroup$ @Aman $m$ is the hash of message signed by the signature we want to prove the knowledge of. $m'$ is the hash of the challenge used to prove we know the signature. $\endgroup$ – Jan Moritz Jun 1 at 18:37

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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