3
$\begingroup$

Imagine this:

  • Charlie chooses two integers $x_1$ and $x_2$ and signs each of these integers with the same private key.
  • Charlie sends the following to Alice:
    • $x_1$ and $x_2$,
    • the two signatures, and
    • his public key.
  • Alice computes $x = x_1 + x_2$ and sends the following to Bob:
    • $x$ and
    • Charlie's public key.

Can Alice prove to Bob (without involving Charlie) that $x$ is the sum of two numbers which have been signed by Charlie, without revealing $x_1$ and $x_2$ to Bob?

A real-world example might be: Can I cryptographically prove that two of my credit cards together can cover a charge without revealing information about the individual credit cards?

I know very little about cryptography and do not really know where to look for a solution. I think this might go in the direction of privacy-preserving computation and perhaps zero-knowledge proofs? Any hint is welcome!

$\endgroup$
4
$\begingroup$

As Mark has said, it's, in theory, a solvable problem (we know how to do it; the known methods are not simple).

However, by tweaking things around a bit, we can make this problem easy.

My solution is based on Pedersen commitments; those are based on a large prime-sized group (where the discrete log problem is difficult) and two group members $g$ and $h$ (which have no known relationship; specifically, no one knows the solution $x$ to $g^x = h$).

A Pedersen commitment to the value $x$ is the value $g^x h^r$, for some random $r$; properties; we can issue the commitment (by publishing the value $g^x h^r$), and then later open the commitment (by publishing the values $x, r$; anyone can verify that those values give the commitment.

  • Someone looking at $g^x h^r$ cannot determine what $x$ is (in fact, for any possible value of $x$, there's a value $r$ that would give that commitment value)

  • The issuer is unable to open the commitment two ways; that is, if he issues a commitment $g^x h^r$, he is unable to find a value $r'$ such that $g^{x'} h^{r'}$ evaluates to the same value.

With that background in mind, he is my proposal:

Charlie sends the following values to Alice:

  • $x_1$ and $x_2$

  • Signed commitments to those values, that is, signed copies of $g^{x_1} h^{r_1}$ and $g^{x_2}h^{r_2}$

  • The random values $r_1$ and $r_2$ (because he already gave the values he committed to, giving him these random values is harmless)

  • His public key

Alice then computes $x = x_1 + x_2$, and generates a zero-knowledge proof that the sum of the two values committed to by $g^{x_1} h^{r_1}$ and $g^{x_2}h^{r_2}$ is $x$. This can be done by generating a proof of knowledge that Alice knows the value $s$ such that $h^s = g^{x_1} h^{r_1} \cdot g^{x_2}h^{r_2} \cdot g^{-x}$; Alice can generate such a proof only if $x_1 + x_2 = x$

Alice then forwards to Bob the value $x$, the two signed commitments, the public key (so Bob can verify the signatures) and the zero-knowledge proof (which Bob can also verify).

This appears to address the end goal (and fairly simplely; there are some details I only vaguely waved at, however a bit of research will turn those up).

$\endgroup$
5
  • $\begingroup$ Thanks, this might be exactly what I'm looking for! Can the approach also be made to work for $x_1 * x_2$? And is it possible to extend this to signed tuples $(c, x_1), (c, x_2)$ and prove not only that $x = x_1 + x_2$ but also that the constants $c$ are identical without revealing $c$? ... for the latter extension, the real-world interpretation would be that I can only use credit cards issued to my own name (= c). $\endgroup$ Nov 23 at 10:18
  • 1
    $\begingroup$ @EliasStrehle: signed tuples would be easy; generate commitments to $c$ and $x_1$ separately (and sign both commitments as a single message); same for $c$ and $x_2$. Then, generate proofs that both $x = x_1 + x_2$ and that the two $c$'s are the same value. As for the product, that is trickier. Not only doesn't an immediately easy way come to mind, but you also have the problem that (if you're multiplying in $\mathbb{Z}$), you can factor the product $x_1 \times x_2$ to come up with only a handful of possibilities for $x_1, x_2$ (and unless that product is quite large, it's easy) $\endgroup$
    – poncho
    Nov 23 at 13:40
  • $\begingroup$ Actually, it would be multiplication in $\mathbb{R}$ ... so I suppose that solves one problem at the cost of a bigger one ;-) But thanks so much for your comments! It's amazing what one can accomplish with cryptography. $\endgroup$ Nov 23 at 13:58
  • $\begingroup$ Would a log transformation work for multiplication? I.e., Charlie commits to $\log x_1$ and $\log x_2$ and Alice sends $x = x_1 * x_2$ to Bob and proves that $\log x = \log(x_1 * x_2) = \log x_1 + \log x_2$. Not sure if that's practical though, thinking of rounding errors... $\endgroup$ Nov 23 at 14:07
  • 1
    $\begingroup$ @EliasStrehle: that sounds workable (given that the $\log$ is being computed outside of crypto). Of course, you'd need to insert a scaling factor; however given that the sizes of the groups (and hence the sizes of the values we can commit to) are quite large (at least 256 bits, possibly larger), there is plenty of space to do so... $\endgroup$
    – poncho
    Nov 23 at 14:14
1
$\begingroup$

You are looking for the notion of a additively-homomorphic signature. In general, a homomorphism is a function which "respects an operation", meaning:

$$f : A\to B,\qquad f(a_0+a_1) = f(a_0)\oplus f(a_1)$$

here, I use $+, \oplus$ to write two (potentially different) "addition operations". So an additive homomorphism behaves well with respect to multiplication. Similarly,

$$f : A\to B,\qquad f(a_0\times a_1) = f(a_0) \otimes f(a_1)$$

would be a multiplicative homomorphism (although this isn't important here).

In this language, all you want is an additively homomorphic signature. Many exist, see for example this paper. Unfortunately, I don't know of any offhand that a are particularly simple (this is somewhat different from additively homomorphic encryption --- there are a number of simple schemes). But what you want is at least a theoretically well-known concept.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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