Zero-knowledge transfer of value protocol II [closed]

Question

This is an improvement of the protocol described here. The protocol does not require trusted setup and is very efficient (much more efficient than anything else I could find). The protocol allows the following:

• Alice and Bob hold secret values $a$ and $b$ respectively.
• 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 so without learning any of the amounts involved.

If anyone sees holes in the protocol described below, or, if there is a better (more efficient) way to do it, I would greatly appreciate feedback.

---

Setup

To facilitate the transfer, two elliptic curves of different orders are used. These curves are $g_1$ and $g_2$ of orders $q_1$ and $q_2$ and generators $G_1$ and $G_2$. The orders $q_1$ and $q_2$ should be distinct but very close to each other, with $q_1 < q_2$.

Using these curves, Alice and Bob can create public commitments to their values. For example, committing to value $a$ would work as follows:

1. Map value $a$ to points on both curves as $A_1 = a ⋅ G_1$ and $A_2 = a ⋅ G_2$
2. Choose a random value $r$ and calculate $T=r⋅G_1$, $S=r⋅G_2$
3. Calculate $u=H(G_1,G_2,A_1,A_2,T,S)$, where $H$ is a hash function
4. Calculate $v=r+a⋅u$ such that $\frac{v}{u} < q_1$. This may require iterating through several values of $r$
5. The commitment to $a$ is then defined as $A = (A_1,A_2, T, S, v)$

An observer can verify that $A_1$ and $A_2$ are derived from the same $a$ and that $a < q_1$ by doing the following:

1. Compute $u$
2. Check that $\frac{v}{u} < q_1$
3. Check that $v⋅G_1=T+u⋅A_1$ and $v⋅G_2=S+u⋅A_2$

Initial State

• Alice has publicly committed to $a$ using the methodology described above and publishing $A = (A_1,A_2, T_a, S_a, v_a)$. We assume that is known for a fact that $A_1$ and $A_2$ refer to the same value $a$.
• Bob has publicly committed to $b$ using the methodology described above and publishing $B = (B_1,B_2, T_b, S_b, v_b)$. We assume that it is known for a fact that $B_1$ and $B_2$ refer to the same value $b$.

Transfer

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

1. Calculates commitment for the new value $a'$ as $A' = (A_1', A_2', T_{a'}, S_{a'}, v_{a'})$
2. Calculates commitment for value $k$ as $K = (K_1,K_2,T_k,S_k,v_k)$
3. Makes both commitments public by publishing $A'$ and $K$

Bob receives value $k$ from Alice via a secure channel and does the following:

1. Verifies that $K_1 = k ⋅ G_1$ and $K_2 = k ⋅ G_2$
2. Calculates his new value $b'$ as $b' = b + k$
3. Calculates commitment to $b'$ as $B' = (B_1', B_2', T_{b'}, S_{b'}, v_{b'})$
4. Makes the new commitment to $b$ public by sharing $B'$

Verification

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

1. Verify that each pair of points $(A_1', A_2'), (B_1', B_2'), (K_1, K_2)$ was derived from the same values and that each of the underlying values is less than $q_1$ using the methodology described previously
2. Verify that $A_1 = A_1' + K_1$ and $A_2 = A_2' + K_2$
3. Verify that $B_1' = B_1 + K_1$ and $B_2' = B_2 + K_2$

---

The scheme above should be secure because all values are effectively padded. The numbers are 256-bit integers that have the following properties:

• A single "coin" consists $10^{69}$ indivisible "units"
• This implies that a single coin requires 230 bits to express
• When transferring values, users randomize the lower bits (e.g. lower 220 bits) such that the same value is never sent twice

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

---

Note: to prevent forgery, Alice and Bob could also sign their commitments - but this is not covered by the description above.

Answer 1

A few remarks:

• You should try to abstract out the primitives you are using, instead of describing everything "from scratch". Typically, you describe a non-interactive zero-knowledge proof for the relation $\exists a, A_1 = a\cdot G_1 \wedge A_2 = a\cdot G_2$. Rather than giving the exact description of this proof from the Fiat-Shamir transform applied to a $\Sigma$-protocol (which is what you're doing), it would be better to just say "Alice publicly proves that this relation is satisfied using a non-interactive zero-knowledge proof". This abstracts the actual properties you want from the concrete implementation you consider, which should make it considerably easier to analyze security.
• Similarly, you should try to simplify your problem as much as you can. For example here you're adding signatures to authenticate Alice and Bob; but this is not the core of your problem. You could simply assume that Alice and Bob are interacting over authenticated channel, separating your specific problem from the unrelated problem of actually authenticated players with signatures.
• To get a security result, you need to first formalize the exact security guarantee you want from the protocol. The current description that you give is not formal enough to exactly state the precise security property that your protocol should satisfy.
• I see a few issues with the current protocol. First, your protocol would not work if $a,b,k$ do not have a lot of entropy (e.g. if they are small integers, as in your example). For example, given $G_1$ and $K_1 = k\cdot G_1$, Victor could easily try to compute $i\cdot G_1$ for many values of $i$, and will find $k$ this way unless $k$ comes from a high-entropy distribution. Usually, one relies on Pedersen commitments of the form $m\cdot G_1 + r\cdot H_1$ for some random $r$ instead of just $k\cdot G_1$ to fix this kind of issues, so as to perfectly hide $k$ (and not simply making it hard to find it when it has a lot of entropy). Second, there is a trivial way to break your proof that the same $a$ is used in $A_1$ and $A_2$: assuming that $\gcd(q_1,q_2) = 1$ (which will be the case if they are different primes), one can easily find for any pair $(a_1, a_2)$ over $\mathbb{Z}_{q_1}\times \mathbb{Z}_{q_2}$ a value $a$ such that $a = a_1 \bmod q_1$ and $a = a_2 \bmod q_2$. Then one can use this $a$ to prove that $A_1 = a\cdot G_1$ and $A_2 = a\cdot G_2$ (as it's indeed the case). That means that the proof can always be constructed for any $A_1 = a_1\cdot G_1, A_2 = a_2\cdot G_2$, for arbitrary values $a_1, a_2$. Hence, this proof does in fact not give any useful information.
• What happens if $K_e$ is not really an encryption of the value $k$ such that $K_1 = k\cdot G_1$? What proves to Victor that Alice and Bob are actually using this value $k$? Nothing seems to bind the value $k$ to the value encrypted in $K_e$.
• Unless I did not understood well, what you want can be realized as follows: (I abstract out the details) there are two public homomorphic commitments, to $a$ and $b$. Alice sends a commitment to $k$, allowing Victor to publicly compute commitments to $a-k$ and $b-k$ using the homomorphic properties, and Alice securely sends k to Bob (using e.g. a secure key exchanged followed by some encryption of $k$), while proving publicly that what she securely sent to Bob is indeed the committed value $k$. You should try to build what you want with this kind of reasoning, using the abstract primitives you need and formalizing the exact security properties you want to guarantee. Currently, I really don't get what you're trying to achieve by using two different curves with two different moduli (could you explain why you want those different moduli?).