0
$\begingroup$

For example perhaps deriving the same PRF from RSA signatures on different messages from a (not known) private key?

Struggling to find the proof of why not.

$\endgroup$
3
  • $\begingroup$ When you say value you mean function isn't? $\endgroup$
    – Ievgeni
    Sep 15, 2020 at 10:52
  • 2
    $\begingroup$ As the question stands, "Sure, just output 0." is a valid answer. So there are probably details missing. What properties does this value need to have? Which signature scheme are you talking about? $\endgroup$
    – Maeher
    Sep 15, 2020 at 12:36
  • $\begingroup$ Please answer the question that Maeher asked of you. Gilles has provided a nice answer, but given the details it is not clear if this matches your requirements. $\endgroup$
    – Maarten Bodewes
    Sep 16, 2020 at 15:45

1 Answer 1

3
$\begingroup$

I understand the question to mean: is there a function $F$ whose domain is signatures under a public-key signature scheme such that, given a signature $s_1$ made with a key $k_1$ and a signature $s_2$ made with a key $k_2$, $F(s_1) = f(s_2)$ if and only if $k_1 = k_2$? Or in simple terms: can you tell who made a signature by looking at it?

You aren't going to find a generic proof of impossibility because it is possible to build signature schemes for which $F$ exists. In fact, any signature scheme can be adjusted to make $F$ possible. Given a signature scheme whose signature function is $S$, define a new scheme whose signature function is $S'(k_{\mathrm{priv}}, x) = (S'(k_{\mathsf{priv}}, x), k_{\mathsf{pub}})$ where $k_{\mathsf{pub}}$ is the public key associated with $k_{\mathsf{priv}}$. In simple terms: attach the public key to the signature. This new scheme is just as secure as the original since the new signature function doesn't reveal any more information than the original and doesn't have equality cases that the original doesn't have.

For ECDSA, given a curve with the generator $G$, its order $n$, and two key pairs on this curve $(d_1, Q_1)$ and $(d_2, Q_2)$, here's a way to construct signatures that are valid with both keys. Note that they are signatures of different messages. Given a nonce $k$ and a message $m_1$, the signature under the first key is $(r, s)$ where $r$ is the x-coordinate of $k G$ modulo $n$ and $s = k^{-1} (H(m_1) + r d_1)$. Let $e_2 = k s - r d_2$. If there exists $m_2$ such that $H(m_2) = e_2$ then $(r,s)$ is the signature of $m_2$ under the second key. Hash functions are not necessarily surjective, so $m_2$ might not exist, but if $H$ is sufficiently indistinguishable from a random oracle, the proportion of values of $k$ such that $m_2$ exists is the size of the image of $H$ among bit-strings of the appropriate length, so many values of $k$ are suitable.

Note that this is a (sketch of a) proof of existence. Finding actual examples (at least with this method) is infeasible since it requires calculating a pre-image under the hash function.

I haven't worked out the math for RSA. I think that due to the longer signatures, it is not the case in general that given two key pairs, there exists a pair of messages such that the signature of the first message with the first key is equal to the signature of the second message with the second key. I expect that this is true with high probability when the hash is sufficiently longer than half the key and false with high probability when the hash is sufficiently smaller than half the key.

Note that if you require the signatures to be of the same message, the answer is completely different. With a known message, ECDSA allows key recovery. This is not true for RSA.

A more interesting version of this question in practice is, given a signature, or more generally a set of signatures made with the same key, and a collection of public keys, is it possible to tell with a non-negligible probability which key made this or these signature? This is the problem of key privacy for signature. RSA does not have key privacy. Ed25519 looks like it might have key privacy.

$\endgroup$
1
  • $\begingroup$ For RSA I suppose you can have signatures with giving message recovery to fill the gap, you choose a specific random value, use that each time to create the signature and then extract it using the public key. Of course this requires the user to be able to choose the signature generation method used. $\endgroup$
    – Maarten Bodewes
    Sep 16, 2020 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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