# Is there a malleable pubkey digital signature scheme?

I'm trying to find a special kind of Digital Signature Scheme.

The scheme should allow me to transform a signature $s=\text{sign}(sk,m)$ (for a private key $sk$ and a message $m$) into a signature $s'=\text{sign}(x,m)$ (for another private key $x$ related to $sk$) such as given $s'$ nobody can state with high probability that $s'$ was obtained by first signing with $sk$ and then transforming. Also one part of the signature must stay unchanged in the transformation.

More formally, the desired property is this:

For every private key $sk$, every other private key $x$, every message $m$, and every signature $s = (s_1,s_2) = \text{sign}(sk,m)$ there is a value $k$ and a value $s_2'$ such that $x = \text{g}(sk,k)$ and $s'= (s_1, s_2') = \text{sign}(x,m)$. $s_1$ is a random/pseudo-random value whose size should be at least $128$ bits. This should be part of the signature (if this value is changed, the signature should fails to verify) s2 is a part of the signature that changes after being transformed.

$\text{g}(sk,k)$ is an easy to compute injective function that takes a private key $sk$ and outputs another private key (e.g. $\text{g}(sk,k) = k*sk$ or $\text{g}(sk,k) = (sk^k) \mod p$, etc..)

Of course $\text{g}()$ does not allow you to choose the output key of $\text{g}()$ such that it matches a certain public key, because that would imply being able to create a forgery.

Even having obtained $sk$ (but not $s$, nor $k$), it should be infeasible for an attacker to detect if $s'$ was build by transforming $s$ into $s'$ or it was created using the private key $x$ directly.

-
What you're trying to build may be related to multi-signatures‌​. $\;$ – Ricky Demer Apr 8 '14 at 3:24
Not seems to be related to multi-signatures. I try to build a signature which has plausible deniability: If I sign a document I can always claim it was signed by another unknown party, but still nobody can sign with my pubkey. – SDL Apr 8 '14 at 3:53
I think something like this could at most give implausible deniability, since unforgeability implies that the probability of another party getting the same signature is negligible. $\;$ – Ricky Demer Apr 8 '14 at 3:58
OK. Now I have cleared my mind and I re-wrote the whole question. At least now I can be told it's impossible. – SDL Apr 8 '14 at 4:11
Just let s1 always be the bit zero. $\:$ I can't think of any role s1 might play that would make the resulting definition achievable but non-trivial. $\:$ You might be interested in ring signatures. $\;\;\;\;$ – Ricky Demer Apr 8 '14 at 4:17