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
  • 1
    $\begingroup$ I didn't get the part where $E(x_a,pub_b)=E(x_b,pub_a)$, where does that come from? $\endgroup$ – Florian Bourse Jun 15 '18 at 9:33
  • $\begingroup$ I am assuming that the encryption is deterministic so $E(E(x, pub_a), pub_b) = E(E(x, pub_b), pub_a)$. I'll update the question to reflect that. $\endgroup$ – irakliy Jun 15 '18 at 18:03

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.

  • $\begingroup$ Thanks! Couldn't the number itself be used as a source of randomness though? Let's say $x$ is a 128-bit integer where lower 64 bits are always randomized - but they are not significant enough to make a difference. So, effectively, you are sending something like 2.00043893439548032 instead of 2. This way, the encryption scheme can be deterministic, but you will actually never use it to encrypt the same number more than once. $\endgroup$ – irakliy Jun 15 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.