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:
- Homomorphism for regular El Gamal is multiplicative, not additive
- Ciphertext and public key size may be quite big - and I'm trying to make them as small as possible