Take the 2-minute tour ×
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.

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

1 Answer 1

up vote 2 down vote accepted

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
    
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 at 13:20
2  
@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 at 20:05

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.