1
$\begingroup$

Given two Schnorr Signatures that were made from the same $x$, where each $x$ is private. Is there a way to prove that they came from the same $x$ without revealing $x$?

I heard about Chaum-Pedersen Protocol and how it is supposed to address this, but I am a bit confused how it should work. The book I'm reading has the following notation:

Equality is proven so long as:

$r_1 == g^{s_1}$. $y_1^{c_1}$

and

$r_2 == h^{s_2}$. $y_2^{c_2}$

Where $g$ and $h$ are generators $s$ is the proof $y_1$ and $y_2$ are the public keys of the the secret $x_1$ and $x_2$ and $c_1$ and $c_2$ are the challenges

I am seriously confused about what the relation between those numbers are: With the above, you prove that each Schnorr Signature came from a different $x$, but not that they came from the same $x$, right?

Answering some questions that came up:

Are $g$ and $h$ different generators from the same group?

Yes, they are.

Are $c_1$ and $c_2$ hashes?

Yes they are. Made with a random oracle. The term "challenge" might be weak here since they are non-interactive.

I'm just really trying to wrap my head around the possibility of proving equality for Schnorr signatures.

$\endgroup$
  • $\begingroup$ I'm seriously confused by the different generators $g$ and $h$. What else differs in the two signatures, are they at least using the same group? Are $c_1$ and $c_2$ the hashes (the "challenge" terminology is unusual for a signature scheme, since that's non-interactive)? Are these hashes part of the signature (as in the original Schnorr signature scheme, but not some variants also named Schnorr signature which essentially use $y^c$ instead)? $\endgroup$ – fgrieu Jun 26 at 10:26
  • $\begingroup$ What is $x$? The message, the private key, the signature-unique random? Also it remains unclear if $c$ or $y^c$ is in the signature. And the title asks to prove equality of signatures, when the body of the question asks a way to prove (in zero knowledge) that the mysterious $x$ is identical in the signatures. Perhaps if you linked to public material with the context this could clarify. $\endgroup$ – fgrieu Jun 26 at 16:47
  • $\begingroup$ If you are given two Schnorr signatures, you can simply run the verification for both and see if they verify with the same public key, which clearly would not reveal the secret key. Or am I missing something here? $\endgroup$ – DrLecter Jun 26 at 17:51
  • $\begingroup$ @DrLecter You can only verify if you know the input. I think $x$ is supposed to be kept private. $\endgroup$ – tylo Jun 26 at 18:27
  • $\begingroup$ Could be, but it's a bit underspecified :) $\endgroup$ – DrLecter Jun 26 at 18:55
1
$\begingroup$

I don't think that works with keeping the message private - unless you break the signature scheme by reusing the nonce.

Your variables $c_1$ and $c_2$ are the results of the hash function. And those can not be the same by the definition of $r$ being a nonce. Moreover: the hash function does not retain any algebraic structure. By the definition of hash functions, the resulting hash only shows if two inputs wre the same or not. No partial matching or any type of relation between two inputs.

But they are also the only variables, that depend on the private message $x$. And from that, I don't see any way to distinguish $c$-values , where $x$ is the same or $x$ is different. Unless you allow $r_1=r_2$, which breaks the security of the signature.

The main misconception with using Chaum-Pedersen: They don't use signature schemes. They use commitments. From the statement, that you want to keep $x$ private, maybe you should use commitments instead of digital signatures. They give the privacy requirement, and you can use Chaum-Pedersen directly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer @tylo. How would one do that? Can you give me an example of using Chaum-Pedersen that fits my example? $\endgroup$ – JohnnyP Jun 27 at 15:38

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.