viff

view apps/millionaires.py @ 961:153c24a4a6c5

find changesets by author, revision, files, or words in the commit message
Randomize port numbers in unit tests.
author Martin Geisler <mg@daimi.au.dk>
date Thu Oct 02 22:22:24 2008 +0200 (3 years ago)
parents 73f6984432b5
children 68b96c32e06e
line source
1 #!/usr/bin/python
2
3 # Copyright 2007, 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 # This example is a tribute to the original example of secure
21 # multi-party computation by Yao in 1982. In his example two
22 # millionaires meet in the street and they want to securely compare
23 # their fortunes. They want to do so without revealing how much they
24 # own to each other. This problem would be easy to solve if both
25 # millionaires trust a common third party, but we want to solve it
26 # without access to a third party.
27 #
28 # In this example the protocol is run between three millionaires and
29 # uses a protocol for secure integer comparison by Toft from 2005.
30 #
31 # Give a player configuration file as a command line argument or run
32 # the example with '--help' for help with the command line options.
33
34 from optparse import OptionParser
35 from twisted.internet import reactor
36
37 from viff.field import GF
38 from viff.runtime import Runtime, create_runtime, gather_shares
39 from viff.comparison import Toft05Runtime
40 from viff.config import load_config
41 from viff.util import rand, find_prime
42
43 # We start by defining the protocol, it will be started at the bottom
44 # of the file.
45
46 class Protocol:
47
48 def __init__(self, runtime):
49 # Save the Runtime for later use
50 self.runtime = runtime
51
52 # This is the value we will use in the protocol.
53 self.millions = rand.randint(1, 200)
54 print "I am Millionaire %d and I am worth %d millions." \
55 % (runtime.id, self.millions)
56
57 # For the comparison protocol to work, we need a field modulus
58 # bigger than 2**(l+1) + 2**(l+k+1), where the bit length of
59 # the input numbers is l and k is the security parameter.
60 # Further more, the prime must be a Blum prime (a prime p such
61 # that p % 4 == 3 holds). The find_prime function lets us find
62 # a suitable prime.
63 l = runtime.options.bit_length
64 k = runtime.options.security_parameter
65 Zp = GF(find_prime(2**(l + 1) + 2**(l + k + 1), blum=True))
66
67 # We must secret share our input with the other parties. They
68 # will do the same and we end up with three variables
69 m1, m2, m3 = runtime.shamir_share([1, 2, 3], Zp, self.millions)
70
71 # Now that everybody has secret shared their inputs we can
72 # compare them. We compare the worth of the first millionaire
73 # with the two others, and compare those two millionaires with
74 # each other.
75 m1_ge_m2 = m1 >= m2
76 m1_ge_m3 = m1 >= m3
77 m2_ge_m3 = m2 >= m3
78
79 # The results are secret shared, so we must open them before
80 # we can do anything usefull with them.
81 open_m1_ge_m2 = runtime.open(m1_ge_m2)
82 open_m1_ge_m3 = runtime.open(m1_ge_m3)
83 open_m2_ge_m3 = runtime.open(m2_ge_m3)
84
85 # We will now gather the results and call the
86 # self.results_ready method when they have all been received.
87 results = gather_shares([open_m1_ge_m2, open_m1_ge_m3, open_m2_ge_m3])
88 results.addCallback(self.results_ready)
89
90 # We can add more callbacks to the callback chain in results.
91 # These are called in sequence when self.results_ready is
92 # finished. The first callback acts like a barrier and makes
93 # all players wait on each other.
94 #
95 # The callbacks are always called with an argument equal to
96 # the return value of the preceeding callback. We do not need
97 # the argument (which is None since self.results_ready does
98 # not return anything), so we throw it away using a lambda
99 # expressions which ignores its first argument.
100 results.addCallback(lambda _: runtime.synchronize())
101 # The next callback shuts the runtime down, killing the
102 # connections between the players.
103 results.addCallback(lambda _: runtime.shutdown())
104
105 def results_ready(self, results):
106 # Since this method is called as a callback above, the results
107 # variable will contain actual field elements, not just
108 # Shares. That makes it very easy to work on them.
109
110 # Let us start by unpacking the list.
111 m1_ge_m2 = results[0]
112 m1_ge_m3 = results[1]
113 m2_ge_m3 = results[2]
114
115 # We can establish the correct order of Millionaires 2 and 3.
116 if m2_ge_m3:
117 comparison = [3, 2]
118 else:
119 comparison = [2, 3]
120
121 # We only have to insert Millionaire 1 in the correct spot.
122 if m1_ge_m2 and m1_ge_m3:
123 # Millionaire 1 is largest.
124 comparison = comparison + [1]
125 elif not m1_ge_m2 and not m1_ge_m3:
126 # Millionaire 1 is smallest.
127 comparison = [1] + comparison
128 else:
129 # Millionaire 1 is between the others.
130 comparison = [comparison[0], 1, comparison[1]]
131
132 print "From poorest to richest:"
133 for id in comparison:
134 if id == self.runtime.id:
135 print " Millionaire %d (%d millions)" % (id, self.millions)
136 else:
137 print " Millionaire %d" % id
138
139 # Parse command line arguments.
140 parser = OptionParser()
141 Runtime.add_options(parser)
142 options, args = parser.parse_args()
143
144 if len(args) == 0:
145 parser.error("you must specify a config file")
146 else:
147 id, players = load_config(args[0])
148
149 # Create a deferred Runtime and ask it to run our protocol when ready.
150 pre_runtime = create_runtime(id, players, 1, options, Toft05Runtime)
151 pre_runtime.addCallback(Protocol)
152
153 # Start the Twisted event loop.
154 reactor.run()