2
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ @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. $\endgroup$
    – Christopher King
    Commented Sep 1, 2016 at 14:00
  • $\begingroup$ @poncho Its similar to homomorphic encryption. $\endgroup$
    – Christopher King
    Commented Sep 1, 2016 at 14:01
  • $\begingroup$ 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 $\endgroup$
    – poncho
    Commented Sep 1, 2016 at 14:20
  • $\begingroup$ @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$. $\endgroup$
    – Christopher King
    Commented Sep 1, 2016 at 14:24
  • $\begingroup$ @poncho a group of infinite order might also work. $\endgroup$
    – Christopher King
    Commented Sep 1, 2016 at 14:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.