Zero-knowledge transfer of value protocol inspired by EC El Gamal

Question

This is a follow up on the question I asked here. I designed a scheme that allows the following:

• Alice has a value $a$ which she wants to keep secret
• Bob has a value $b$ which he wants to keep secret
• Alice can "transfer" a part of her value to Bob such that whatever she transfers must be subtracted from her value (the sum of their value must remain the same). For example, if she has $10$ and Bob has $5$, after transferring $2$, she should have $8$ and Bob should have $7$
• Victor is an independent observer and must be able to verify that the sum of the values does not change as a result of the transfer. But he should do it without learning any of the numbers involved

The scheme below is inspired by EC El Gamal. If anyone can see holes in it, would really appreciate feedback.

---

Setup

• Alice and Bob hold pairs of EC keys generated using an Elliptic Curve with generator $G$ (an example of such curve could be secp256k1)
• Their private keys are $x_a, x_b$, and $X_a, X_b$ are corresponding public keys
• Alice has committed to her number by making $A = a*G + X_a$ public
• Bob has committed to his number by making $B = b*G + X_b$ public

Transfer

Alice wants to transfer value $c$ to Bob such that $a' = a - c$ and $b' = b + c$. To do this, she does the following:

1. Calculates commitment to the new number $A' = (a - c)*G + X_a$
2. Calculates commitment to the transferred number $C_1 = c*G$
3. Calculates shared secret with Bob and uses it to build a shared key $s = H(x_a * X_b$), where $H$ is a hashing function
4. Encrypts $c$ with the shared key $C_2 = E(c, s)$, where $E$ is a symmetric encryption function
5. Makes the following info public $(A', C_1, C_2)$

Bob receives the info and does the following:

1. Calculates shared secret with Alice and uses it to build a shared key $s = H(x_b * X_a$)
2. Uses the shared key to decrypt the value of $c = D(C_2, s)$, where $D$ is a symmetric decryption function
3. Verifies that $C_1 = c * G$
4. Calculates commitment to the new number $B' = (b + c) * G + X_b$
5. Makes $B'$ public

Verification

An independent observer (Victor) can verify that the total value in the system didn't change by doing the following:

1. Verify that $A = A' + C_1$
2. Verify that $B' = B + C_1$

---

The scheme above should be secure because all numbers are padded. The numbers are 256-bit integers with:

• 64 most significant bits containing the actual number
• The remaining 192 bits set randomly

So, effectively, instead of transferring something like $2$, Alice would be transferring something like $2.00034094035343043$

Answer 1

As is, there is nothing to prevent Alice from spending more than she holds by letting her $a$ underflow modulo the order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$ of $g$.

Update: and as pointed by VincBreaker in that answer, as is there is nothing to prevent Bob from computing Alice's commitment of transfer of $\bar c$ from Alice to Bob: the only use of Alice's private key is to compute $s$ that she shares with Bob, and with that $s$ Bob can do anything Alice can. A fix is considered in said answer.

Whether the above properties are a functional issue or not depends on the application, but these are something to watch for electronic money.

As proposed, the padding scheme for 64-bit value/amount $\bar x$ (with restriction to $0\le\bar x\le2^{64}-2$) is $x=P(\bar x,r)=\bar x\,2^{192}+r$ for $k=192$-bit uniform $r$, and $\bar x=Q(x)=\displaystyle\left\lfloor\frac x{2^{192}}\right\rfloor$ used to extract value/amount $\bar x$ from $x$, with $Q(P(\bar x))=\bar x$. It follows that if $a=b+c$ then either $\bar a=\bar b+\bar c$ or $\bar a+1=\bar b+\bar c$ hold, with next to equal odds. Whether this is a functional issue or not depends on the application (but see last section for a workaround).

Another security issue is that for $k$-bit random padding $r$ there is at best $k/2$-bit security against someone trying to confirm a guess, for example of a transaction amount $\bar c$ from $C_1=c*G=\bar c\,2^{192}*G+r*G$, by solving for $k$-bit $r$ the equation $r*G=C_1-\bar c\,2^{192}*G$ using e.g. the Baby-Step/Giant-Step algorithm. Same for values held $\bar a$ and $\bar b$.

Thus I'd say that 256-bit ECC is too little, especially if we want exact balance as follows.

---

If the uncertainty of one unit is an issue, we can improve on that with a sacrifice of some bits of $r$. That could be $k=176$-bit uniform $r$ with $P(\bar x,r)=\bar x\,2^{192}+r-2^{175}$ and $Q(x)=\displaystyle\left\lfloor\frac{x+2^{191}}{2^{192}}\right\rfloor$. In this way most transactions are exact, including the first $2^{16}$ with certainty, and in practice likely the first $2^{22}$.

Answer 2

Despite the potential flaws fgrieu stated, it is actually possible for Bob to forge a commit from Alice to Bob by first calculating $C_1 = c * G$ and then $A' = A - C_1$. Having done that, Bob can compute the shared key $s = H(x_b * X_a)$ and determine $C_2 = E(c, s)$ which allows him to publish $(A', C_1, C_2)$ which is a "valid" commit from Alice.

He then can go on and publish his commitment $B' = B + C_1$ which will result in a commitment Vector will accept.

However, this potential insecurity may actually become a feature since the commit no longer requires Bob to actually accept the commit so Alice could send $c$ coins to Bob at any time. Keep in mind that this scheme does not provide any overflow protection as fgrieu stated.

Also, Alice is able to calculate a secret key $k = a + x_a - c$ which leads to $k * G = A'$ so she can sign the commitment with $A'$ to ensure it's actually her committing it. Bob can to the same by calculating $k = b + x_b + c$. Since calculating $k_a$ or $k_b$ requires knowledge of $x_a$ or $x_b$, finding the private key for $A'$ or $B'$ should be as hard as finding the keys for $X_a$ or $X_b$.

Answer 3

What you did in the above can be achieved by the following much simpler protocol:

1 Alice and Bob publish a commitment of their values $A=a\cdot G+ X_a$ and $B=b\cdot G+ X_b$, and their public keys.

2 Alice sends $c$ through a secure channel to Bob, and publish $c\cdot G$.

3 Bob verifies that $c\cdot G$ published by Alice is the same as he computes locally. If not, abort the protocol.

4 If no one aborts (or upon receiving acknowledgements from both Alice and Bob), Victor updates the commitment $A'=A -c\cdot G$ and $B'=B+ c\cdot G$.