# HG changeset patch
# User Martin Geisler <[EMAIL PROTECTED]>
# Date 1214215643 -7200
# Node ID 926f19ca9b83e6e803894369e654dee0e1129a0d
# Parent dc3106ba60700a2cfa1faf1a62ac011875db2275
Multiplication using ElGamal. Warning, it is insecure!
The multiplication protocol works, but unfortunately it reveals the
input shares while computing the result...
diff --git a/viff/elgamal.py b/viff/elgamal.py
--- a/viff/elgamal.py
+++ b/viff/elgamal.py
@@ -17,6 +17,7 @@
"""The ElGamal crypto system."""
+from viff.runtime import BasicRuntime, Share, increment_pc, gather_shares
from viff.util import rand
from viff.field import GF
@@ -46,3 +47,115 @@
gamma, delta = c
p, a = sk
return (pow(gamma, p - 1 - a, p) * delta) % p
+
+
+def _dummy_field(x):
+ raise Exception("This field should not be used")
+
+
+class AdditiveRuntime(BasicRuntime):
+ """Runtime for two players providing addition only."""
+
+ def add_player(self, player, protocol):
+ BasicRuntime.add_player(self, player, protocol)
+ if player.id == self.id:
+ self.player = player
+ # Size of message field.
+ self.p = self.player.pubkey[0]
+ else:
+ self.peer = player
+
+ @increment_pc
+ def share(self, inputters, number=None):
+ """Share *number* additively."""
+ assert number is None or self.id in inputters
+
+ results = []
+ for peer_id in inputters:
+ if peer_id == self.id:
+ a = rand.randint(0, self.p)
+ b = (number - a) % self.p
+
+ results.append(Share(self, _dummy_field, a))
+ pc = tuple(self.program_counter)
+ self.protocols[self.peer.id].sendData(pc, "additive_share", b)
+ else:
+ share = Share(self, _dummy_field)
+ self._expect_data(peer_id, "additive_share", share)
+ results.append(share)
+
+ # Unpack a singleton list.
+ if len(results) == 1:
+ return results[0]
+ else:
+ return results
+
+ @increment_pc
+ def open(self, share, receivers=None):
+ """Open *share* to *receivers* (defaults to both players)."""
+
+ def exchange(a):
+ pc = tuple(self.program_counter)
+ self.protocols[self.peer.id].sendData(pc, "additive_share", a)
+ result = Share(self, _dummy_field)
+ self._expect_data(self.peer.id, "additive_share", result)
+ result.addCallback(lambda b: (a + b) % self.p)
+ return result
+
+ result = share.clone()
+ self.schedule_callback(result, exchange)
+ return result
+
+ def add(self, share_a, share_b):
+ """Addition of shares.
+
+ Communication cost: none.
+ """
+ if not isinstance(share_a, Share):
+ share_a = Share(self, _dummy_field, share_a)
+ if not isinstance(share_b, Share):
+ share_b = Share(self, _dummy_field, share_b)
+
+ result = gather_shares([share_a, share_b])
+ result.addCallback(lambda (a, b): (a + b) % self.p)
+ return result
+
+
+class ElGamalRuntime(AdditiveRuntime):
+ """Runtime for two players which provides multiplication."""
+
+ def mul(self, share_a, share_b):
+ """Multiplication of shares."""
+ if not isinstance(share_a, Share):
+ share_a = Share(self, _dummy_field, share_a)
+ if not isinstance(share_b, Share):
+ share_b = Share(self, _dummy_field, share_b)
+
+ def finish_mul((a1, b1)):
+ pc = tuple(self.program_counter)
+ send_data = self.protocols[self.peer.id].sendData
+
+ # Encrypt and send our sharing to our peer.
+ enc_a1 = encrypt(a1, self.player.pubkey)
+ send_data(pc, "encrypted_share", enc_a1)
+ # and receive an encryption too.
+ enc_a2 = Share(self, _dummy_field)
+ self._expect_data(self.peer.id, "encrypted_share", enc_a2)
+
+ # Multiply a2 with b1 inside the encryption.
+ # TODO: This is unsecure and leaks b1! The recipient can
+ # just multiply with the inverse of a2.
+ enc_a2_b1 = enc_a2.addCallback(lambda (x, y): (x, b1 * y))
+ enc_a2_b1.addCallback(lambda c: send_data(pc, "encrypted_share",
c))
+
+ result = Share(self, _dummy_field)
+ self._expect_data(self.peer.id, "encrypted_share", result)
+
+ # result contains E(a1 * b2).
+ result.addCallback(decrypt, self.player.seckey)
+ result.addCallback(lambda a1_b2: (a1 * b1 + a1_b2) % self.p)
+ return result
+
+ result = gather_shares([share_a, share_b])
+ result.addCallback(finish_mul)
+ return result
_______________________________________________
viff-patches mailing list
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
