viff

changeset 1018:66096425fbc1

Added application doing division.
author Sigurd Meldgaard <stm@daimi.au.dk>
date Thu, 13 Nov 2008 17:39:14 +0100
parents ed614874c220
children d839791e2487
files apps/divide.py
diffstat 1 files changed, 129 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/apps/divide.py	Thu Nov 13 17:39:14 2008 +0100
     1.3 @@ -0,0 +1,129 @@
     1.4 +#!/usr/bin/python
     1.5 +
     1.6 +# Copyright 2008 VIFF Development Team.
     1.7 +#
     1.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.9 +#
    1.10 +# VIFF is free software: you can redistribute it and/or modify it
    1.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    1.12 +# published by the Free Software Foundation, either version 3 of the
    1.13 +# License, or (at your option) any later version.
    1.14 +#
    1.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.18 +# Public License for more details.
    1.19 +#
    1.20 +# You should have received a copy of the GNU Lesser General Public
    1.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.22 +#
    1.23 +
    1.24 +"""This program does a secret division between two secret shared
    1.25 +values. It is of course mostly meaningless for this example (you can
    1.26 +compute the inputs from your own value and the output).
    1.27 +
    1.28 +The program can be run as follows for each player (min 3) where 24 is
    1.29 +the number we would like to divide (by):
    1.30 +
    1.31 +$ python division.py player-X.ini 24
    1.32 +
    1.33 +Only the numbers of player 1 and player 2 are actually used, but
    1.34 +more players are necessary for the security.
    1.35 +"""
    1.36 +
    1.37 +from optparse import OptionParser
    1.38 +from twisted.internet import reactor
    1.39 +
    1.40 +from viff.field import GF
    1.41 +from viff.runtime import Runtime, create_runtime
    1.42 +from viff.runtime import make_runtime_class
    1.43 +from viff.comparison import ComparisonToft07Mixin
    1.44 +from viff.config import load_config
    1.45 +from viff.util import find_prime, dprint
    1.46 +
    1.47 +
    1.48 +def bits_to_val(bits):
    1.49 +    return sum([2**i * b for (i, b) in enumerate(reversed(bits))])
    1.50 +
    1.51 +
    1.52 +def divide(x, y, l):
    1.53 +    """Returns a share of of ``x/y`` (rounded down).
    1.54 +
    1.55 +       Precondition:  ``2**l * y < x.field.modulus``.
    1.56 +
    1.57 +       If ``y == 0`` return ``(2**(l+1) - 1)``.
    1.58 +
    1.59 +       The division is done by making a comparison for every
    1.60 +       i with ``(2**i)*y`` and *x*.
    1.61 +       Protocol by Sigurd Meldgaard.
    1.62 +
    1.63 +       Communication cost: *l* rounds of comparison.
    1.64 +
    1.65 +       Also works for simple integers:
    1.66 +       >>>divide(3, 3, 2)
    1.67 +       1
    1.68 +       >>>divide(50, 10, 10)
    1.69 +       5
    1.70 +       """
    1.71 +    bits = []
    1.72 +    for i in range(l, -1, -1):
    1.73 +        t = 2**i * y
    1.74 +        cmp = t <= x
    1.75 +        bits.append(cmp)
    1.76 +        x = x - t * cmp
    1.77 +    return bits_to_val(bits)
    1.78 +
    1.79 +
    1.80 +def main():
    1.81 +     # Parse command line arguments.
    1.82 +    parser = OptionParser(usage=__doc__)
    1.83 +
    1.84 +    parser.add_option("--modulus",
    1.85 +                     help="lower limit for modulus (can be an expression)")
    1.86 +
    1.87 +    parser.set_defaults(modulus=2**65, number=None)
    1.88 +
    1.89 +    Runtime.add_options(parser)
    1.90 +
    1.91 +    options, args = parser.parse_args()
    1.92 +    if len(args)==2:
    1.93 +        options.number = int(args[1])
    1.94 +    else:
    1.95 +        options.number = None
    1.96 +
    1.97 +    if len(args) == 0:
    1.98 +        parser.error("you must specify a config file")
    1.99 +
   1.100 +    Zp = GF(find_prime(options.modulus, blum=True))
   1.101 +
   1.102 +    # Load configuration file.
   1.103 +    id, players = load_config(args[0])
   1.104 +
   1.105 +    runtime_class = make_runtime_class(mixins=[ComparisonToft07Mixin])
   1.106 +    pre_runtime = create_runtime(id, players, 1, options, runtime_class)
   1.107 +
   1.108 +    def run(runtime):
   1.109 +        print "Connected."
   1.110 +
   1.111 +        print "My number: %d." % options.number
   1.112 +        # Players 1 and 2 are doing a sharing over the field Zp.
   1.113 +        # Our input is options.number (none for other players).
   1.114 +        if runtime.id == 3:
   1.115 +            options.number = None
   1.116 +        (x, y) = runtime.shamir_share([1, 2], Zp, options.number)
   1.117 +
   1.118 +        # Do the secret computation.
   1.119 +        result = divide(x, y, 10) # 10 bits for the result.
   1.120 +
   1.121 +        # Now open the result so we can see it.
   1.122 +        dprint("The two numbers divided are: %s", runtime.open(result))
   1.123 +
   1.124 +        result.addCallback(lambda _: runtime.shutdown())
   1.125 +
   1.126 +    pre_runtime.addCallback(run)
   1.127 +
   1.128 +    # Start the Twisted event loop.
   1.129 +    reactor.run()
   1.130 +
   1.131 +if __name__ == "__main__":
   1.132 +    main()