Post by Sigurd Torkel MeldgaardAn (proof-of-concept) app doing secret shared division.
Very nice! I've tried it and -- gasp! -- it works :-)
Tord might have a fancy log(l) comparison protocol, but until that is
written or implemented somewhere I definitely think we should include
this example.
As usual, I have some comments below... :-) Please let me know if you
agree and send an updated patch when you get around to it.
Post by Sigurd Torkel MeldgaardIt is a very simple algorithm (basically finding one bit of the
result at a time by doing comparisons), and could probably be put in
the runtime, but I am not sure exactly where, because it requires an
precision parameter, and thus does not lend itself well to operator
overloading.
Right. But don't we know the precision parameter from the field size?
So using math.log(x.field.modulus, 2) would work, wouldn't it? That
could be done in the __div__ method on Share so as to not mess up the
nice property that divide works with both ints and Shares.
Post by Sigurd Torkel MeldgaardSigurd
Added application doing division.
diff -r bf314f0580fc apps/divide.py
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/apps/divide.py Wed Oct 08 14:16:40 2008 +0200
@@ -0,0 +1,132 @@
+#!/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/>.
+#
+
+"""This program does a secret division between two secret shared
+values It is of course mostly meaningless for this example (you can
Missing full stop.
Post by Sigurd Torkel Meldgaard+compute the inputs from your own value and the output)
Ditto :-)
Post by Sigurd Torkel Meldgaard+
+The program can be run as follows for each player (min 3) where 24 is
+
+$ python equality.py player-X.ini -n 24
+
+Only the numbers of player 1 and player 2 are actually compared, but
+more players are necessary for the security.
"compared" looks like a cut-and-paste mistake?
Post by Sigurd Torkel Meldgaard+"""
+
+from optparse import OptionParser
+from twisted.internet import reactor
+
+from viff.field import GF
+from viff.runtime import Runtime, create_runtime
+from viff.runtime import make_runtime_class
+from viff.comparison import ComparisonToft07Mixin
+from viff.config import load_config
+from viff.util import find_prime, dprint
+
+
+ b_r = bits[:]
+ b_r.reverse()
+ return sum([2**i * b for (i, b) in enumerate(b_r)])
+
+
+ """Returns a share of of `x*y` (rounded down).
+
+ Precondition: `2**l * y < x.field.modulus.`
+
+ If `y == 0` return `(2**(l+1) - 1)`.
+
+ The division is done by making a comparison for every
+ i with `(2**i)*y` and *x*.
+
+ Communication cost: *l* rounds of comparison.
+
+
Double empty line.
Post by Sigurd Torkel Meldgaard+ >>>divide(3, 3, 2)
+ 1
+ >>>divide(50, 10, 10)
+ 10"""
Oh, that is cool -- a function that works on int and Share arguments!
I guess that says something about how well our overloading works and
how nice our FieldElement objects behave...
Post by Sigurd Torkel Meldgaard+ bits = []
+ t = 2**i * y
+ cmp = t <= x
+ bits.append(cmp)
+ x = x - t * cmp
+ return bits_to_val(bits)
+
+
+ # Parse command line arguments.
+ parser = OptionParser(usage=__doc__)
+
+
+ parser.add_option("--modulus",
+ help="lower limit for modulus (can be an expression)")
+ parser.add_option("-n", "--number", type="int",
+ help="number to compare")
This "option" is not an option at all, it is a required argument :-)
The optparse documentation has something to say about this:
http://docs.python.org/library/optparse.html#what-are-positional-arguments-for
Post by Sigurd Torkel Meldgaard+ parser.set_defaults(modulus=2**65, number=None)
+
+ Runtime.add_options(parser)
+
+ options, args = parser.parse_args()
+
+ parser.error("you must specify a config file")
+
+ Zp = GF(find_prime(options.modulus, blum=True))
+
+ # Load configuration file.
+ id, players = load_config(args[0])
+
+ runtime_class = make_runtime_class(mixins=[ComparisonToft07Mixin])
+ pre_runtime = create_runtime(id, players, 1, options, runtime_class)
+
+ print "Connected."
+
+ # Is our player id among the two first?
+ print "My number: %d." % options.number
+ # Players 1 and two are doing a sharing over the field ZP
+ # our input is options number
+ (x, y) = runtime.shamir_share([1, 2], Zp, options.number)
+ print "I do not have a number."
+ (x, y) = runtime.shamir_share([1, 2], Zp, None)
+
+ # Do the secret computation
+ result = divide(x, y, 27) # 27 bits for the result
+
+ # Now open the result so that we can see it
+ dprint("The two numbers divided are: %s", runtime.open(result))
+
+ result.addCallback(lambda _: runtime.shutdown())
+
+ pre_runtime.addCallback(run)
+
+ # Start the Twisted event loop.
+ reactor.run()
+
+ main()
--
Martin Geisler
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.