Commutative homomorphic encryption for zero-knowledge transfers

Question

I am trying to design a scheme that would allow the following:

• Alice has a number $a$ which she wants to keep secret
• Bob has a number $b$ which he wants to keep secret
• Alice can "transfer" a number to Bob such that whatever she transfers must be subtracted from her number (the sum of their numbers must remain the same)
• Victor is an independent observer and must be able to validate that the sum of the numbers does not change without learning any of the numbers

For example, suppose Alice's number is $10$ and Bob's number is $5$. If Alice transfers $2$ to Bob, his number will become $7$ and her number will become $8$. Victor, observing the transfer, should be sure that the total sum didn't change but he shouldn't be able to learn any of the numbers involved. Alice shouldn't be able to learn Bob's starting or ending number, and Bob shouldn't be able to learn Alice's starting or ending number.

I am thinking this is possible to implement using a deterministic encryption that is both commutative and homomorphic (additive). For example:

• Alice would use her public key to encrypt her number $a_1 = E(a, pub_a)$ and would share it with Victor
• Bob would do the same $b_1 = E(b, pub_b)$
• If Alice wanted to transfer $x$ to Bob, she would compute $a_2 = E(a-x, pub_a)$, $x_a = E(x, pub_a)$, $x_b = E(x, pub_b)$. She would then share $a_2$, $x_a$, and $x_b$ with Bob and Victor
• Bob would decrypt $x = D(x_b, priv_b)$, and then use it to compute $b_2 = E(b + x, pub_b)$. He would then share $b_2$ with Victor

Using this info, Victor would be able to verify that Alice's number was updated properly, because $a_1 = a_2 * x_a$. He would also know that Bob's number was updated properly because $b_2 = b_1 * x_b$. And finally, he would know that $x_a$ and $x_b$ encode the same number because $E(x_a, pub_b) = E(x_b, pub_a)$.

Deterministic encryption should not compromise security because the numbers themselves can be randomly "padded". For example, the numbers could be 128-bit integers where lower 64 bits are randomized. So, essentially, instead of sending $2$, Alice could be sending something like $2.00034094035343043$.

It seems to me that El Gamal could work to implement something like this, but I'm not sure if there is anything better. Also, there are some concerns for El Gamal:

1. Homomorphism for regular El Gamal is multiplicative, not additive
2. Ciphertext and public key size may be quite big - and I'm trying to make them as small as possible

Answer 1

Your protocol won't work if the encryption scheme is randomized. In fact, the commutative property would be that $D(D(x,priv_a),priv_b)=D(D(x,priv_b),priv_a)$, which is different than $E(E(x,pub_a),pub_b)=E(E(x,pub_b),pub_a)$.

A deterministic encryption scheme cannot be semantically secure. So if a scheme could meet the requirements to be used in this protocol, it wouldn't have the security guarantees you would want from an encryption scheme.

This is not to mention that $*$ could also be non-deterministic.

Answer 2

Homomorphism for regular El Gamal is multiplicative, not additive

Isn't that what the algorithm used to do additive? I think it was secured by the way that you choose some prime number, pow it with the number you want. Multiply them, then log the result you then get secured addition

Suppose

    var a = myNumber;
    var b = yourNumber;
    var pA = BigInteger.Pow(somePrime,myNumber); // p^a
    var pB = BigInteger.Pow(somePrime,yourNumber); // p^b

    var pResult = pA * pB; // p^a * p^b == p^(a + b)
    var result = BigInteger.Log(pResult,somePrime); // log_p(p^(a + b)) == a + b