Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 2 down vote accepted

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'$
share|improve this answer
    
It is clear that verification of this signature is non-trivial, so this could be a kind of solution. However, proving knowledge of $(r,s)$ only makes sense to keep signatures indistinguishable. An obvious distinguisher algorithm would be to compare the "R" part. – Vadym Fedyukovych Feb 10 at 13:45
    
Keeping the original $(r,s)$ signature indistinguishable is exactly what we want to do according to the original question: "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.". – 109fa68a145b Feb 10 at 14:14
    
Revealing $r$ allows for distinguisher algorithm by comparing it to candidate pairs. – Vadym Fedyukovych Feb 12 at 12:41
    
Sorry but I'm not getting your point :/ – 109fa68a145b Feb 12 at 12:58
    
I think Vadim means that if the other person has many signatures in hand, they can know which one I'm using to generate the proof. For my use case (where I'm trying to avoid leaking to signatures because it can be used for bad things™), it doesn't matter. – Christophe Biocca Feb 12 at 14:27

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.

share|improve this answer
1  
The ones I've seen for that are interactive. For my use case that wouldn't work very well. But thanks for the pointer. – Christophe Biocca Mar 28 '14 at 13:20
4  
@ChristopheBiocca, you can turn any interactive ZKPoK into a non-interactive ZKPoK using the Fiat-Shamir heuristic (basically, use a hash function to choose the challenge). That should give you what you want. – D.W. Mar 28 '14 at 20:05
    
@D.W. Can you give some links or more explanations on how this works? – 109fa68a145b Feb 11 at 20:25

As i understand, you have Alice Signature(r,s) and you want to prove to Bob that you have Alice's Signature on m.

Is Bob aware of the signature (r,s)? If yes, then you sign (r,s) with you private key, generate (Rn,Sn) and give it to Bob. Bob can verify it using you public key!

share|improve this answer
    
Bob shouldn't be able to know (r,s)! Otherwise it would have been too easy. – 109fa68a145b Feb 15 at 20:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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