[PATCH 4 of 4] Test program for ElGamal based multiplication

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214215643 -7200
# Node ID cc937fbd7ac31e921fce1d374e982d5061b43081
# Parent 926f19ca9b83e6e803894369e654dee0e1129a0d
Test program for ElGamal based multiplication.

diff --git a/apps/elgamal.py b/apps/elgamal.py
new file mode 100755
--- /dev/null
+++ b/apps/elgamal.py
@@ -0,0 +1,57 @@
+#!/usr/bin/python
+
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+import sys
+
+from twisted.internet import reactor
+
+from viff.field import GF256
+from viff.runtime import create_runtime, Share
+from viff.elgamal import ElGamalRuntime, _dummy_field
+from viff.config import load_config
+from viff.util import dprint
+
+id, players = load_config(sys.argv[1])
+input = int(sys.argv[2])
+
+print "I am player %d and will input %s" % (id, input)
+
+
+def protocol(runtime):
+ print "-" * 64
+ print "Program started"
+ print
+
+ a, b = runtime.share([1, 2], input)
+ c = a * b
+ a = runtime.open(a)
+ b = runtime.open(b)
+ c = runtime.open(c)
+
+ dprint("### opened a: %s ###", a)
+ dprint("### opened b: %s ###", b)
+ dprint("### opened c: %s ###", c)
+
+ runtime.wait_for(a, b, c)
+
+pre_runtime = create_runtime(id, players, 1, runtime_class=ElGamalRuntime)
+pre_runtime.addCallback(protocol)
+
+print "#### Starting reactor ###"
+reactor.run()

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214046177 -7200
# Node ID dc3106ba60700a2cfa1faf1a62ac011875db2275
# Parent 48f52da60f334d77732e73cb3af2c04c7a07d91d
Generate and load ElGamal keys.

The names "pubkey" and "seckey" are not perfect since we might want
other types of public and secret keys in the future.

diff --git a/viff/config.py b/viff/config.py
--- a/viff/config.py
+++ b/viff/config.py
@@ -34,17 +34,20 @@
from configobj import ConfigObj

from viff.prss import generate_subsets, PRF
-from viff.util import rand
+from viff.util import rand, find_random_prime
+from viff.elgamal import generate_key_pair


class Player:
"""Wrapper for information about a player in the protocol."""

- def __init__(self, id, host, port, keys=None, dealer_keys=None):
+ def __init__(self, id, host, port, pubkey, seckey=None, keys=None, dealer_keys=None):
"""Initialize a player."""
self.id = id
self.host = host
self.port = port
+ self.pubkey = pubkey
+ self.seckey = seckey
self.keys = keys
self.dealer_keys = dealer_keys

@@ -123,8 +126,10 @@
id = p_unstr(player)
host = config[player]['host']
port = int(config[player]['port'])
+ pubkey = tuple(map(int, config[player]['pubkey']))

if 'prss_keys' in config[player]:
+ seckey = tuple(map(int, config[player]['seckey']))
keys = {}
for subset in config[player]['prss_keys']:
keys[s_unstr(subset)] = config[player]['prss_keys'][subset]
@@ -138,12 +143,12 @@
for subset in config[player]['prss_dealer_keys'][dealer]:
dealer_keys[d][s_unstr(subset)] = config[player]['prss_dealer_keys'][dealer][subset]

- players[id] = Player(id, host, port, keys, dealer_keys)
+ players[id] = Player(id, host, port, pubkey, seckey, keys, dealer_keys)

# ID of player for which this config file was made
owner_id = id
else:
- players[id] = Player(id, host, port)
+ players[id] = Player(id, host, port, pubkey)

return owner_id, players

@@ -183,6 +188,10 @@
"""Convert a dealer ID to a string."""
return "Dealer " + str(dealer)

+ # TODO: remove hard-coded key size.
+ prime = long(find_random_prime(256))
+ key_pairs = dict([(p, generate_key_pair(prime)) for p in players])
+
configs = {}
for p in players:
config = ConfigObj(indent_type=' ')
@@ -203,7 +212,11 @@
# in the configuration file, making it slightly easier to read
config.comments[p_str(p)] = ['']

+ config[p_str(p)]['pubkey'] = key_pairs[p][0]
+
if player == p:
+ config[p_str(p)]['seckey'] = key_pairs[p][1]
+
# Prepare the config file for the keys
config[p_str(p)]['prss_keys'] = {}
config[p_str(p)]['prss_dealer_keys'] = {}

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# 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

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214169868 -7200
# Node ID 48f52da60f334d77732e73cb3af2c04c7a07d91d
# Parent 33f8fbf147a76ce6aec9c36ddea41d6920084968
Basic implementation of the ElGamal crypto system.

diff --git a/viff/elgamal.py b/viff/elgamal.py
new file mode 100644
--- /dev/null
+++ b/viff/elgamal.py
@@ -0,0 +1,48 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+"""The ElGamal crypto system."""
+
+from viff.util import rand
+from viff.field import GF
+
+# Common generator for all keys.
+G = 3
+
+def generate_key_pair(p):
+ """Generate a ``(pk, sk)`` key pair for the group Zp^*."""
+ # We calculate with normal Python (long) integers to ensure that
+ # we can easily save/load keys.
+ a = rand.randint(1, p - 2)
+ g_a = pow(G, a, p)
+ pk = (p, g_a)
+ sk = (p, a)
+ return (pk, sk)
+
+def encrypt(m, pk):
+ """ElGamal encryption."""
+ p, g_a = pk
+ k = rand.randint(1, p - 2)
+ gamma = pow(G, k, p)
+ delta = (m * pow(g_a, k, p)) % p
+ return (gamma, delta)
+
+def decrypt(c, sk):
+ """ElGamal decryption."""
+ gamma, delta = c
+ p, a = sk
+ return (pow(gamma, p - 1 - a, p) * delta) % p