# 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.

• @poncho The proof doesn't reveal the $K_x$, and by your reasoning, cannot. It just reveals $K$. The verifier need not have any idea what the $K_x$ are, so they don't need be included in the proof. – PyRulez Sep 1 '16 at 14:00
• @poncho Its similar to homomorphic encryption. – PyRulez Sep 1 '16 at 14:01
• As for finding the proof for $-k$ being hard, I don't believe that is achievable if the group has known order. Given a proof of $k$, a proof for $nk$ can be generated in $O(\log n)$ steps of the $k' = k_1 + k_2$ proof combination procedure); if the order of the group is $q$, then $-k = (q-1)k$, hence we can generate such a proof in $O(\log q)$ steps – poncho Sep 1 '16 at 14:20
• @poncho Perhaps if the space requirement is weakend to $O(\log x)$, you could include $x$ with the proof, and therefore see if $x=q-1$. – PyRulez Sep 1 '16 at 14:24
• @poncho a group of infinite order might also work. – PyRulez Sep 1 '16 at 14:33

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.