Join Log in
Score:3
Elias Strehle avatar Crypto

Prove that $x$ is the sum of digitally signed numbers without revealing the summands

pg flag
Elias Strehle

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!

91
0 + 0
Score:4
poncho avatar Crypto
my flag
poncho

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

0 + 0
Elias Strehle avatar
pg flag
Elias Strehle
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).
0
Reply
poncho avatar
my flag
poncho
@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)
1
Reply
Elias Strehle avatar
pg flag
Elias Strehle
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.
0
Reply
Elias Strehle avatar
pg flag
Elias Strehle
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...
0
Reply
poncho avatar
my flag
poncho
@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...
1
Reply
Score:1
Mark avatar Crypto
ng flag
Mark

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.