Martin Geisler
2008-06-23 10:28:21 UTC
These patches are an example of a runtime for two players based on
ElGamal. It is not secure, but it is simple :-)
The inspiration for this came from Mikkel who sent me some code that
implemented the Paillier crypto system, which is additively
homomorphic. So I figured that I could use this for two player MPC by
implementing multiplication of additively secret shared values as
follows: a = a1 + a2 and b = b1 + b2, where Pi has ai and bi.
So
a * b + (a1 + a2) * (b1 + b2) = a1 b1 + a1 b2 + a2 b1 + a2 b2
which means that the only difficulity is calculating the mixed
products. But here I figured that P1 could simply send E(a1) to P2 who
would then use the homomorphic property of the Paillier encryption to
calculate E(a1 b2) and send that back to P1. Likewise for a2 b1.
But with Paillier each player calculates in a different field! So we
would get (a1 b2) mod m1 and (a2 b1) mod m2 and have no good way of
combining them... Actually the players would want to calculate
a1 b2 - r and r
such that seeing a1 b2 - r does not reveal anything about b2.
With ElGamal all players can do calculations in the same field, but
alas, the scheme is multiplicatively homomorphic instead of additively
homomorphic. So although we can easily calculate a1 b2, we cannot
easily calculate a1 b2 - r which is needed for security.
I'm posting it anyway so that people can see how one could implement
something like a two player protocol in VIFF.
ElGamal. It is not secure, but it is simple :-)
The inspiration for this came from Mikkel who sent me some code that
implemented the Paillier crypto system, which is additively
homomorphic. So I figured that I could use this for two player MPC by
implementing multiplication of additively secret shared values as
follows: a = a1 + a2 and b = b1 + b2, where Pi has ai and bi.
So
a * b + (a1 + a2) * (b1 + b2) = a1 b1 + a1 b2 + a2 b1 + a2 b2
which means that the only difficulity is calculating the mixed
products. But here I figured that P1 could simply send E(a1) to P2 who
would then use the homomorphic property of the Paillier encryption to
calculate E(a1 b2) and send that back to P1. Likewise for a2 b1.
But with Paillier each player calculates in a different field! So we
would get (a1 b2) mod m1 and (a2 b1) mod m2 and have no good way of
combining them... Actually the players would want to calculate
a1 b2 - r and r
such that seeing a1 b2 - r does not reveal anything about b2.
With ElGamal all players can do calculations in the same field, but
alas, the scheme is multiplicatively homomorphic instead of additively
homomorphic. So although we can easily calculate a1 b2, we cannot
easily calculate a1 b2 - r which is needed for security.
I'm posting it anyway so that people can see how one could implement
something like a two player protocol in VIFF.