"Sigurd Torkel Meldgaard" <[EMAIL PROTECTED]> writes: > An (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. > It 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. > Sigurd > > 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. > +compute the inputs from your own value and the output) Ditto :-) > + > +The program can be run as follows for each player (min 3) where 24 is > +the number we would like to divide by: > + > +$ 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? > +""" > + > +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 > + > + > +def bits_to_val(bits): > + b_r = bits[:] > + b_r.reverse() > + return sum([2**i * b for (i, b) in enumerate(b_r)]) > + > + > +def divide(x, y, l): > + """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. > + Also works for simple integers: > + >>>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... > + bits = [] > + for i in range(l, -1, -1): > + t = 2**i * y > + cmp = t <= x > + bits.append(cmp) > + x = x - t * cmp > + return bits_to_val(bits) > + > + > +def main(): > + # 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 > + parser.set_defaults(modulus=2**65, number=None) > + > + Runtime.add_options(parser) > + > + options, args = parser.parse_args() > + > + if len(args) == 0: > + 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) > + > + def run(runtime): > + print "Connected." > + > + # Is our player id among the two first? > + if runtime.id <= 2: > + 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) > + else: > + 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() > + > +if __name__ == "__main__": > + main() -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. _______________________________________________ viff-patches mailing list [email protected] http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
