Thanks for the review On Fri, Oct 24, 2008 at 11:56 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: > "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.
That could be done, but unfortunately the limits are lower, it seems it stops working at around 27-28-bits, you mentioned the other day that comparisons can only be done in half of the bits, is that true? Anyway the precision parameter times y must be less than the number of bits in the field (or half the number of bits) so I guess it is only rarely useful to do the division without specifying the precision. But maybe we can find an acceptable default. > >> 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 :-) > You are really sharp, I should install a spell-and-grammar-checker for my comments. >> + >> +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? > It is of course! >> +""" >> + >> +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 > Hmm, the players with id above 2 should not input a number. But I guess it makes sense to make it a positional argument anyway. >> + 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 > Attached is a revised patch - I am sorry my email client (gmail) does not allow me to specify the Mime-type... Sigurd
division.diff
Description: Binary data
_______________________________________________ viff-patches mailing list [email protected] http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
