[PATCH 2 of 7] Paillier crypto system

[Martin Geisler]

# HG changeset patch
# User Mikkel Krøigård <***@daimi.au.dk>
# Date 1213999972 -7200
# Node ID 3971a1fd9c03ca686e68f3f58517fb6a942b0923
# Parent 65f882964e2061d6d5dee00fd9693f0e2c6b00cf
Paillier crypto system.

(Added by Martin, but written by Mikkel.)

diff --git a/viff/paillier.py b/viff/paillier.py
new file mode 100644
--- /dev/null
+++ b/viff/paillier.py
@@ -0,0 +1,54 @@
+# 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 gmpy
+from gmpy import mpz
+
+from viff.util import rand, find_random_prime
+
+def L(u, n):
+ return (u-1)/n
+
+def generate_keys(bit_length):
+ # Make an RSA modulus n.
+ p = find_random_prime(bit_length/2)
+ while True:
+ q = find_random_prime(bit_length/2)
+ if p<>q: break
+
+ n = p*q
+ nsq = n*n
+
+ # Calculate Carmichael's function.
+ lm = gmpy.lcm(p-1, q-1)
+
+ # Generate a generator g in B.
+ while True:
+ g = rand.randint(1, long(nsq))
+ if gmpy.gcd(L(pow(g, lm, nsq), n), n) == 1: break
+
+ return (n, g), (n, g, lm)
+
+def encrypt(m, (n, g)):
+ r = rand.randint(1, long(n))
+ nsq = n*n
+ return (pow(g, m, nsq)*pow(r, n, nsq)) % nsq
+
+def decrypt(c, (n, g, lm)):
+ numer = L(pow(c, lm, n*n), n)
+ denom = L(pow(g, lm, n*n), n)
+ return (numer*gmpy.invert(denom, n)) % n

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214740058 -7200
# Node ID 9187374f43b8069143f433d0c0d3c73dc5400a15
# Parent 9b48a61e040c8ec5ead21c104502edac9430f87f
Two player Paillier based runtime.

This implements a multiplication protocol for two players described
here by Claudio Orlandi:

http://article.gmane.org/gmane.comp.cryptography.viff.devel/290

diff --git a/viff/paillier.py b/viff/paillier.py
--- a/viff/paillier.py
+++ b/viff/paillier.py
@@ -15,10 +15,13 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

+from twisted.internet.defer import Deferred
import gmpy
from gmpy import mpz

-from viff.util import rand, find_random_prime
+from viff.util import rand, find_random_prime, dprint
+from viff.runtime import BasicRuntime, Share, increment_pc, gather_shares
+from viff.field import GF

def L(u, n):
return (u-1)/n
@@ -52,3 +55,136 @@
numer = L(pow(c, lm, n*n), n)
denom = L(pow(g, lm, n*n), n)
return (numer*gmpy.invert(denom, n)) % n
+
+
+class PaillierRuntime(BasicRuntime):
+
+ def add_player(self, player, protocol):
+ BasicRuntime.add_player(self, player, protocol)
+ if player.id == self.id:
+ self.player = player
+ else:
+ self.peer = player
+
+ @increment_pc
+ def share(self, inputters, field, 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 = field(rand.randint(0, field.modulus - 1))
+ b = number - a
+
+ results.append(Share(self, a.field, a))
+ pc = tuple(self.program_counter)
+ self.protocols[self.peer.id].sendShare(pc, b)
+ else:
+ share = self._expect_share(peer_id, field)
+ 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].sendShare(pc, a)
+ result = self._expect_share(self.peer.id, share.field)
+ result.addCallback(lambda b: a + b)
+ 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.
+ """
+ field = getattr(share_a, "field", getattr(share_b, "field", None))
+ if not isinstance(share_a, Share):
+ share_a = Share(self, field, share_a)
+ if not isinstance(share_b, Share):
+ share_b = Share(self, field, share_b)
+
+ result = gather_shares([share_a, share_b])
+ result.addCallback(lambda (a, b): a + b)
+ return result
+
+ def mul(self, share_a, share_b):
+ """Multiplication of shares."""
+ field = getattr(share_a, "field", getattr(share_b, "field", None))
+
+ k = self.options.security_parameter
+ n = min(self.player.pubkey[0], self.peer.pubkey[0])
+ assert field.modulus**2 + 2**k < n, \
+ "Need bigger Paillier keys to multiply."
+
+ if not isinstance(share_a, Share):
+ share_a = Share(self, field, share_a)
+ if not isinstance(share_b, Share):
+ share_b = Share(self, field, share_b)
+
+ def finish_mul((a1, b1)):
+ # The computations are symmetric for P1 and P2, and the
+ # code uses notation for P1, but the code uses notation as
+ # seen frmo the perspective of P1. Both players calculate
+ #
+ # a1 b1 + a1 b2 + a2 b1 + a2 b2
+ #
+ # but P1 has a zero share of the a2 b2 product and vice
+ # versa for P2. So the final sum has three parts which are
+ # additively secret shared like this:
+ #
+ # P1: a1 b1 + (a1 b2 + r2) + - r1
+ # P2: - r2 + (a2 b1 + r1) + a2 b2
+
+ pc = tuple(self.program_counter)
+ send_share = self.protocols[self.peer.id].sendShare
+ send_data = self.protocols[self.peer.id].sendData
+
+ # Our part of the sum which needs not be shared.
+ a1_b1 = a1 * b1
+
+ # Encrypt and send our sharing to our peer.
+ enc_a1 = encrypt(a1.value, self.player.pubkey)
+ send_data(pc, "paillier", enc_a1)
+ # and receive an encryption too.
+ enc_a2 = Deferred()
+ self._expect_data(self.peer.id, "paillier", enc_a2)
+
+ nsq = self.peer.pubkey[0]**2
+
+ # Multiply a2 with b1 inside the encryption.
+ enc_a2_b1 = enc_a2.addCallback(pow, b1.value, nsq)
+
+ # Chose and add r1 inside the encryption.
+ r1 = rand.randint(0, field.modulus**2 + 2**k)
+
+ enc_r1 = encrypt(r1, self.peer.pubkey)
+ enc_a2_b1_r1 = enc_a2_b1.addCallback(lambda c: (c * enc_r1) % nsq)
+ enc_a2_b1_r1.addCallback(lambda c: send_data(pc, "paillier", c))
+
+ # Now receive E(a1 b2 + r2) from the peer.
+ enc_a1_b2_r2 = Share(self, field)
+ self._expect_data(self.peer.id, "paillier", enc_a1_b2_r2)
+ a1_b2_r2 = enc_a1_b2_r2.addCallback(decrypt, self.player.seckey)
+ # Convert the received value from mpz to GFElement.
+ a1_b2_r2.addCallback(long)
+ a1_b2_r2.addCallback(field)
+
+ res = a1_b2_r2.addCallback(lambda a1_b2_r2: a1_b1 + a1_b2_r2 - r1)
+ return res
+
+ 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 1214740034 -7200
# Node ID 65f882964e2061d6d5dee00fd9693f0e2c6b00cf
# Parent 33f8fbf147a76ce6aec9c36ddea41d6920084968
Allow arbitrary thresholds when generating config files.

This is needed in the case where n=2 and t=1.

diff --git a/apps/generate-config-files.py b/apps/generate-config-files.py
--- a/apps/generate-config-files.py
+++ b/apps/generate-config-files.py
@@ -72,9 +72,6 @@

(options, args) = parser.parse_args()

-if not options.t < options.n/2:
- parser.error("must have t < n/2")
-
if len(args) != options.n:
parser.error("must supply a hostname:port argument for each player")

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214046177 -7200
# Node ID 9b48a61e040c8ec5ead21c104502edac9430f87f
# Parent 3971a1fd9c03ca686e68f3f58517fb6a942b0923
Generate and load Paillier 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
@@ -35,16 +35,19 @@

from viff.prss import generate_subsets, PRF
from viff.util import rand
+from viff import paillier


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,9 @@
"""Convert a dealer ID to a string."""
return "Dealer " + str(dealer)

+ # TODO: remove hard-coded key size.
+ key_pairs = dict([(p, paillier.generate_keys(1024)) for p in players])
+
configs = {}
for p in players:
config = ConfigObj(indent_type=' ')
@@ -203,7 +211,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 1214740770 -7200
# Node ID b10ab58865eb96c641fe028f201bce57b23933fe
# Parent 9187374f43b8069143f433d0c0d3c73dc5400a15
Added prss_share_random method.

This works by letting everybody pick a random number from their
private PRF. This is used as their share -- the sum will be random and
unknown to both parties.

diff --git a/viff/paillier.py b/viff/paillier.py
--- a/viff/paillier.py
+++ b/viff/paillier.py
@@ -65,6 +65,15 @@
self.player = player
else:
self.peer = player
+
+ @increment_pc
+ def prss_share_random(self, field):
+ """Generate a share of a uniformly random element."""
+ prfs = self.players[self.id].prfs(field.modulus)
+ # There can only be one PRF in the dictionary.
+ prf = prfs.values()[0]
+ share = field(prf(tuple(self.program_counter)))
+ return Share(self, field, share)

@increment_pc
def share(self, inputters, field, number=None):

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214740772 -7200
# Node ID 1020d7a99606dec7875ff0f25d3e3c3d3d001d15
# Parent b10ab58865eb96c641fe028f201bce57b23933fe
Test program for Paillier runtime.

diff --git a/apps/paillier.py b/apps/paillier.py
new file mode 100755
--- /dev/null
+++ b/apps/paillier.py
@@ -0,0 +1,62 @@
+#!/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 GF
+from viff.runtime import create_runtime, Share
+from viff.paillier import PaillierRuntime
+from viff.config import load_config
+from viff.util import dprint, find_prime
+
+id, players = load_config(sys.argv[1])
+Zp = GF(find_prime(2**64))
+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], Zp, input)
+
+ dprint("a%d: %s", runtime.id, a)
+ dprint("b%d: %s", runtime.id, b)
+
+ 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=PaillierRuntime)
+pre_runtime.addCallback(protocol)
+
+print "#### Starting reactor ###"
+reactor.run()

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1214740772 -7200
# Node ID a454120c508b622a005d0746253cd6f1927020f5
# Parent 1020d7a99606dec7875ff0f25d3e3c3d3d001d15
Benchmark support for Paillier runtime.

diff --git a/apps/benchmark.py b/apps/benchmark.py
--- a/apps/benchmark.py
+++ b/apps/benchmark.py
@@ -65,6 +65,7 @@
from viff.runtime import Runtime, ActiveRuntime, create_runtime, gather_shares
from viff.comparison import Toft05Runtime, Toft07Runtime
from viff.comparison import ActiveToft05Runtime, ActiveToft07Runtime
+from viff.paillier import PaillierRuntime
from viff.config import load_config
from viff.util import find_prime

@@ -94,7 +95,7 @@
help="number of operations")
parser.add_option("-o", "--operation", type="choice",
choices=["mul", "mul-active", "comp", "comp-active",
- "compII", "compII-active"],
+ "compII", "compII-active", "mul-paillier"],
help=("operation to benchmark, one of 'mul', 'mul-active', "
"'comp', 'comp-active', 'compII', 'compII-active'"))
parser.add_option("-p", "--parallel", action="store_true",
@@ -258,6 +259,9 @@
elif options.operation == "compII-active":
operation = operator.ge
runtime_class = ActiveToft07Runtime
+elif options.operation == "mul-paillier":
+ operation = operator.mul
+ runtime_class = PaillierRuntime

if options.parallel:
benchmark = ParallelBenchmark