Additive proof of discrete log? Let's say someone has $K$, and I want to prove to them that I know $k$ such $K = k*g$ (where $g$ is some sort of group element). I can use a Schnorr signature.

Is there some protocol for mergable proofs of the above kind. Namely, that given a proof for $k_1$ and $k_2$, you get a proof for $k' = k_1 + k_2$. (Note that you don't necessarily know $k_1$ and $k_2$. You have just seen proofs for them.)

Note that the proof is much weaker, of course. You are not proving that you know $k'$. You are only proving that you have seen proofs of $k_x$ that add to $k'$.

It should also take $\mathcal O (1)$ space in the number of $k_x$ (this would be a corollary if the number of $k_x$ where a secret). Otherwise, the proof would be easy. Simply list the proofs for all the $k_x$. ($\mathcal O(\log x)$ is also acceptable.)

(This is open problem two of the mimble wimble white paper.)

EDIT: Another nice property would that for a proof of $k$, finding a proof for $-k$ should be hard.
Chase et al.: Malleable Proof Systems and Applications. Eurocrypt 2012


This paper is the only one I know of that discuss a problem like this. They consider the problem of combining/modifying NIZK proofs -- for example, if I see a proof that $(A,B,C)=(g^a, g^b, g^c)$ is a DH-tuple ($c = ab$), then I can produce a proof that $(A^2, B^2, C^4)$ is a DH-tuple, even though I don't know their discrete logs.

Their focus is Groth-Sahai-style proofs in groups with bilinear pairings. I don't know how helpful the techniques will be for Schnorr-style proofs.