viff

view apps/divide.py @ 1575:cfb8e1485006

find changesets by author, revision, files, or words in the commit message
Updated email address.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed Dec 15 13:00:00 2010 +0100 (17 months ago)
parents 6cd5ceb87542
children
line source
1 #!/usr/bin/env python
2
3 # Copyright 2008 VIFF Development Team.
4 #
5 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
6 #
7 # VIFF is free software: you can redistribute it and/or modify it
8 # under the terms of the GNU Lesser General Public License (LGPL) as
9 # published by the Free Software Foundation, either version 3 of the
10 # License, or (at your option) any later version.
11 #
12 # VIFF is distributed in the hope that it will be useful, but WITHOUT
13 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
15 # Public License for more details.
16 #
17 # You should have received a copy of the GNU Lesser General Public
18 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
19 #
20
21 """This program does a secret division between two secret shared
22 values. It is of course mostly meaningless for this example (you can
23 compute the inputs from your own value and the output).
24
25 The program can be run as follows for each player (min 3) where 24 is
26 the number we would like to divide (by):
27
28 $ python division.py player-X.ini 24
29
30 Only the numbers of player 1 and player 2 are actually used, but
31 more players are necessary for the security.
32 """
33
34 from optparse import OptionParser
35 import viff.reactor
36 viff.reactor.install()
37 from twisted.internet import reactor
38
39 from viff.field import GF
40 from viff.runtime import Runtime, create_runtime, make_runtime_class
41 from viff.comparison import ComparisonToft07Mixin
42 from viff.config import load_config
43 from viff.util import find_prime, dprint
44
45
46 def bits_to_val(bits):
47 return sum([2**i * b for (i, b) in enumerate(reversed(bits))])
48
49
50 def divide(x, y, l):
51 """Returns a share of of ``x/y`` (rounded down).
52
53 Precondition: ``2**l * y < x.field.modulus``.
54
55 If ``y == 0`` return ``(2**(l+1) - 1)``.
56
57 The division is done by making a comparison for every
58 i with ``(2**i)*y`` and *x*.
59 Protocol by Sigurd Meldgaard.
60
61 Communication cost: *l* rounds of comparison.
62
63 Also works for simple integers:
64 >>>divide(3, 3, 2)
65 1
66 >>>divide(50, 10, 10)
67 5
68 """
69 bits = []
70 for i in range(l, -1, -1):
71 t = 2**i * y
72 cmp = t <= x
73 bits.append(cmp)
74 x = x - t * cmp
75 return bits_to_val(bits)
76
77
78 def main():
79 # Parse command line arguments.
80 parser = OptionParser(usage=__doc__)
81
82 parser.add_option("--modulus",
83 help="lower limit for modulus (can be an expression)")
84
85 parser.set_defaults(modulus=2**65)
86
87 Runtime.add_options(parser)
88
89 options, args = parser.parse_args()
90 if len(args)==2:
91 number = int(args[1])
92 else:
93 number = None
94
95 if len(args) == 0:
96 parser.error("you must specify a config file")
97
98 Zp = GF(find_prime(options.modulus, blum=True))
99
100 # Load configuration file.
101 id, players = load_config(args[0])
102
103 runtime_class = make_runtime_class(mixins=[ComparisonToft07Mixin])
104 pre_runtime = create_runtime(id, players, 1, options, runtime_class)
105
106 def run(runtime):
107 print "Connected."
108
109 # Players 1 and 2 are doing a sharing over the field Zp.
110 # Our input is number (None for other players).
111 if runtime.id == 3:
112 print "I have no number"
113 else:
114 print "My number: %d." % number
115 (x, y) = runtime.shamir_share([1, 2], Zp, number)
116
117 # Do the secret computation.
118 result = divide(x, y, 10) # 10 bits for the result.
119
120 # Now open the result so we can see it.
121 dprint("The two numbers divided are: %s", runtime.open(result))
122
123 result.addCallback(lambda _: runtime.shutdown())
124
125 pre_runtime.addCallback(run)
126
127 # Start the Twisted event loop.
128 reactor.run()
129
130 if __name__ == "__main__":
131 main()