viff

changeset 1295:beefdf8f16c4

orlandi: wrapped lots of crazy-long code lines and docstrings
author Martin Geisler <mg@cs.au.dk>
date Fri, 16 Oct 2009 22:34:26 +0200
parents cefcb223c892
children 42f614d9acf3
files viff/orlandi.py
diffstat 1 files changed, 83 insertions(+), 53 deletions(-) [+]
line diff
     1.1 --- a/viff/orlandi.py	Fri Oct 16 19:12:29 2009 +0200
     1.2 +++ b/viff/orlandi.py	Fri Oct 16 22:34:26 2009 +0200
     1.3 @@ -47,6 +47,7 @@
     1.4      """A share in the Orlandi runtime.
     1.5  
     1.6      A share in the Orlandi runtime is a 3-tuple ``(x_i, rho_i, Cr_i)`` of:
     1.7 +
     1.8      - A share of a number, ``x_i``
     1.9      - A tuple of two random numbers, ``rho_i = (rho_i1, rho_i2)``
    1.10      - A commitment to the number and the random numbers, ``Cr_i``
    1.11 @@ -115,14 +116,16 @@
    1.12          return self.open(share, receivers, threshold)
    1.13  
    1.14      def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
    1.15 -        """Send the share *xi*, *rhoi*, and the commitment *Cx* to party *other_id*."""
    1.16 +        """Send the share *xi*, *rhoi*, and the commitment *Cx* to
    1.17 +        party *other_id*."""
    1.18          self.protocols[other_id].sendShare(pc, xi)
    1.19          self.protocols[other_id].sendShare(pc, rhoi[0])
    1.20          self.protocols[other_id].sendShare(pc, rhoi[1])
    1.21          self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
    1.22  
    1.23      def _expect_orlandi_share(self, peer_id, field):
    1.24 -        """Waits for a number ``x``, ``rho``, and the commitment for ``x``."""
    1.25 +        """Waits for a number ``x``, ``rho``, and the commitment for
    1.26 +        ``x``."""
    1.27          xi = self._expect_share(peer_id, field)
    1.28          Cx = Deferred()
    1.29          rhoi1 = self._expect_share(peer_id, field)
    1.30 @@ -133,7 +136,8 @@
    1.31              expected_num = 4;
    1.32              if len(ls) is not expected_num:
    1.33                  raise OrlandiException("Cannot share number, trying to create a share,"
    1.34 -                                       " expected %s components got %s." % (expected_num, len(ls)))
    1.35 +                                       " expected %s components got %s."
    1.36 +                                       % (expected_num, len(ls)))
    1.37              s1, xi = ls[0]
    1.38              s2, rhoi1 = ls[1]
    1.39              s3, rhoi2 = ls[2]
    1.40 @@ -155,7 +159,8 @@
    1.41              expected_num = 3;
    1.42              if len(ls) is not expected_num:
    1.43                  raise OrlandiException("Cannot share number, trying to create a share,"
    1.44 -                                       " expected %s components got %s." % (expected_num, len(ls)))
    1.45 +                                       " expected %s components got %s."
    1.46 +                                       % (expected_num, len(ls)))
    1.47  
    1.48              s1, xi = ls[0]
    1.49              s2, rhoi1 = ls[1]
    1.50 @@ -168,13 +173,15 @@
    1.51          return sls
    1.52  
    1.53      def secret_share(self, inputters, field, number=None, threshold=None):
    1.54 -        """Share the value, number, among all the parties using additive shareing.
    1.55 +        """Share the value *number* among all the parties using
    1.56 +        additive sharing.
    1.57  
    1.58 -        To share an element ``x in Z_p``, choose random ``x_1, ..., x_n-1 in Z_p``,
    1.59 -        define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
    1.60 +        To share an element ``x in Z_p``, choose random ``x_1, ...,
    1.61 +        x_n-1 in Z_p``, define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
    1.62  
    1.63 -        Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``, define
    1.64 -        ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x, p_x)``.
    1.65 +        Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``,
    1.66 +        define ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x,
    1.67 +        p_x)``.
    1.68  
    1.69          Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``.
    1.70          """
    1.71 @@ -184,13 +191,14 @@
    1.72          self.program_counter[-1] += 1
    1.73  
    1.74          def additive_shares_with_rho(x):
    1.75 -            """Returns a tuple of a list of tuples (player id, share, rho) and rho.
    1.76 +            """Returns a tuple of a list of tuples (player id, share,
    1.77 +            rho) and rho.
    1.78  
    1.79 -            Chooses random elements ``x_1, ..., x_n-1`` in field and ``x_n`` st.
    1.80 -            ``x_n = x - Sum_i=1^n-1 x_i``.
    1.81 +            Chooses random elements ``x_1, ..., x_n-1`` in field and
    1.82 +            ``x_n`` st. ``x_n = x - Sum_i=1^n-1 x_i``.
    1.83  
    1.84 -            Chooses random pair of elements ``rho_1, ..., rho_n in Z_p^2``
    1.85 -            and define ``rho_n = Sum_i=1^n rho_i``.
    1.86 +            Chooses random pair of elements ``rho_1, ..., rho_n in
    1.87 +            Z_p^2`` and define ``rho_n = Sum_i=1^n rho_i``.
    1.88  
    1.89              Returns a pair of ``((player id, x_i, rho_i), rho)``.
    1.90              """
    1.91 @@ -245,8 +253,8 @@
    1.92  
    1.93          Every partyi broadcasts a share pair ``(x_i', rho_x,i')``.
    1.94  
    1.95 -        The parties compute the sums ``x'``, ``rho_x'`` and
    1.96 -        check ``Com_ck(x',rho_x' = C_x``.
    1.97 +        The parties compute the sums ``x'``, ``rho_x'`` and check
    1.98 +        ``Com_ck(x',rho_x' = C_x``.
    1.99  
   1.100          If yes, return ``x = x'``, else else return :const:`None`.
   1.101          """
   1.102 @@ -278,17 +286,22 @@
   1.103                                         (x, rho1, rho2, Cx1, Cx))
   1.104  
   1.105          def deserialize(ls):
   1.106 -            shares = [(field(long(x)), field(long(rho1)), field(long(rho2))) for x, rho1, rho2 in map(self.list_str, ls)]
   1.107 +            shares = [(field(long(x)), field(long(rho1)), field(long(rho2)))
   1.108 +                      for x, rho1, rho2 in map(self.list_str, ls)]
   1.109              return shares
   1.110  
   1.111          def exchange((xi, (rhoi1, rhoi2), Cx), receivers):
   1.112              # Send share to all receivers.
   1.113 -            ds = self.broadcast(self.players.keys(), receivers, str((str(xi.value), str(rhoi1.value), str(rhoi2.value))))
   1.114 +            ds = self.broadcast(self.players.keys(), receivers,
   1.115 +                                str((str(xi.value),
   1.116 +                                     str(rhoi1.value),
   1.117 +                                     str(rhoi2.value))))
   1.118  
   1.119              if self.id in receivers:
   1.120                  result = gatherResults(ds)
   1.121                  result.addCallbacks(deserialize, self.error_handler)
   1.122 -                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(Cx,))
   1.123 +                result.addCallbacks(recombine_value, self.error_handler,
   1.124 +                                    callbackArgs=(Cx,))
   1.125                  return result
   1.126  
   1.127          result = share.clone()
   1.128 @@ -304,15 +317,15 @@
   1.129      def random_share(self, field):
   1.130          """Generate a random share in the field, field.
   1.131  
   1.132 -        To generate a share of a random element ``r in Z_p``, party ``P_i``
   1.133 -        chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and
   1.134 +        To generate a share of a random element ``r in Z_p``, party
   1.135 +        ``P_i`` chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and
   1.136          broadcast ``C_r^i = Com_ck(r_i, rho_ri)``.
   1.137  
   1.138 -        Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r, rho_r)``,
   1.139 -        where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n rho_ri``.
   1.140 +        Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r,
   1.141 +        rho_r)``, where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n
   1.142 +        rho_ri``.
   1.143  
   1.144          Party ``P_i sets [r]_i = (r_i, rho_ri, C_r)``.
   1.145 -
   1.146          """
   1.147          self.program_counter[-1] += 1
   1.148  
   1.149 @@ -431,15 +444,15 @@
   1.150  
   1.151          Communication cost: ???.
   1.152  
   1.153 -        Assume the parties are given a random share ``[r]`` by a trusted dealer.
   1.154 -        Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
   1.155 +        Assume the parties are given a random share ``[r]`` by a
   1.156 +        trusted dealer. Then we denote the following protocol but
   1.157 +        ``[x] = Shift(P_i, x, [r])``.
   1.158  
   1.159          1. ``r = OpenTo(P_i, [r]``
   1.160  
   1.161          2. ``P_i broadcasts Delta = r - x``
   1.162  
   1.163          3. ``[x] = [r] - Delta``
   1.164 -
   1.165          """
   1.166          # TODO: Communitcation costs?
   1.167          assert (self.id in inputters and number != None) or (self.id not in inputters)
   1.168 @@ -448,7 +461,8 @@
   1.169  
   1.170          results = []
   1.171          def hack(_, peer_id):
   1.172 -            # Assume the parties are given a random share [r] by a trusted dealer.
   1.173 +            # Assume the parties are given a random share [r] by a
   1.174 +            # trusted dealer.
   1.175              share_r = self.random_share(field)
   1.176              # 1. r = OpenTo(P_i, [r])
   1.177              open_r = self.open(share_r, [peer_id])
   1.178 @@ -459,7 +473,8 @@
   1.179              if peer_id == self.id:
   1.180                  def g(r, x):
   1.181                      delta = r - x
   1.182 -                    delta = self.broadcast([peer_id], self.players.keys(), str(delta.value))
   1.183 +                    delta = self.broadcast([peer_id], self.players.keys(),
   1.184 +                                           str(delta.value))
   1.185                      self.schedule_callback(delta, subtract_delta, share_r)
   1.186                      delta.addErrback(self.error_handler)
   1.187                      return delta
   1.188 @@ -567,9 +582,9 @@
   1.189      def _cmul(self, share_x, share_y, field):
   1.190          """Multiplication of a share with a constant.
   1.191  
   1.192 -        Either share_x or share_y must be an OrlandiShare but not both.
   1.193 -        Returns None if both share_x and share_y are OrlandiShares.
   1.194 -
   1.195 +        Either share_x or share_y must be an OrlandiShare but not
   1.196 +        both. Returns None if both share_x and share_y are
   1.197 +        OrlandiShares.
   1.198          """
   1.199          def constant_multiply(x, c):
   1.200              assert(isinstance(c, FieldElement))
   1.201 @@ -696,7 +711,8 @@
   1.202               and
   1.203               [G_j] = [y] + SUM_i=1^d [g_i]*j^i
   1.204  
   1.205 -        3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])``
   1.206 +        3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j],
   1.207 +           [b_j], [c_j])``
   1.208  
   1.209          4. compute ``[H_0] = SUM_j=1^2d+1 delta_j[H_j]`` where
   1.210             ``delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j)``
   1.211 @@ -799,9 +815,9 @@
   1.212      def triple_gen(self, field):
   1.213          """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
   1.214  
   1.215 -        1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
   1.216 -           compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
   1.217 -           broadcast them.
   1.218 +        1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p
   1.219 +           X (Z_p)^2``, compute ``alpha_i = Enc_eki(a_i)`` and ``Ai =
   1.220 +           Com_ck(a_i, r_i)``, and broadcast them.
   1.221  
   1.222          2. Every party ``P_j`` does:
   1.223  
   1.224 @@ -894,10 +910,12 @@
   1.225              Ci = commitment.commit(ci.value, t1.value, t2.value)
   1.226  
   1.227              # Broadcast Ci.
   1.228 -            Cs = self.broadcast(self.players.keys(), self.players.keys(), repr(Ci))
   1.229 +            Cs = self.broadcast(self.players.keys(), self.players.keys(),
   1.230 +                                repr(Ci))
   1.231              result = gatherResults(Cs)
   1.232 -            result.addCallbacks(step45, self.error_handler, callbackArgs=(alphas, gammas, alpha_randomness,
   1.233 -                                                                          As, Bs, ai, bi, ci, r, s, t, dijs))
   1.234 +            result.addCallbacks(step45, self.error_handler,
   1.235 +                                callbackArgs=(alphas, gammas, alpha_randomness,
   1.236 +                                              As, Bs, ai, bi, ci, r, s, t, dijs))
   1.237              return result
   1.238  
   1.239          def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s):
   1.240 @@ -978,7 +996,9 @@
   1.241          Ai = commitment.commit(ai.value, r1.value, r2.value)
   1.242  
   1.243          # broadcast alpha_i and A_i.
   1.244 -        ds = self.broadcast(sorted(self.players.keys()), sorted(self.players.keys()), str(alphai) + ":" + repr(Ai))
   1.245 +        ds = self.broadcast(sorted(self.players.keys()),
   1.246 +                            sorted(self.players.keys()),
   1.247 +                            str(alphai) + ":" + repr(Ai))
   1.248  
   1.249          result = gatherResults(ds)
   1.250          def split_alphas_and_As(ls):
   1.251 @@ -1126,14 +1146,22 @@
   1.252                  return d
   1.253  
   1.254              def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas):
   1.255 -                """So if B receives ai, bi, dij, ri, si, and the randomness used in the
   1.256 -                computation of alpha, he then checks that:
   1.257 -                1) the alpha_i he received is equals to the encryption of ai and the
   1.258 -                commitment he received, Ai, is equal to the commitment of ai and ri
   1.259 -                2) the commitment he received, Bj, is equal to the commitment of bj and sj
   1.260 -                3) the gammaij he received is equal to the gammaij he now computes based on
   1.261 -                the values he reveives
   1.262 +                """So if B receives ai, bi, dij, ri, si, and the
   1.263 +                randomness used in the computation of alpha, he then
   1.264 +                checks that:
   1.265 +
   1.266 +                1) the alpha_i he received is equals to the encryption
   1.267 +                   of ai and the commitment he received, Ai, is equal
   1.268 +                   to the commitment of ai and ri
   1.269 +
   1.270 +                2) the commitment he received, Bj, is equal to the
   1.271 +                   commitment of bj and sj
   1.272 +
   1.273 +                3) the gammaij he received is equal to the gammaij he
   1.274 +                   now computes based on the values he reveives
   1.275 +
   1.276                  4) a, b, c is a triple, a * b = c
   1.277 +
   1.278                  5) ai, bi < p and dij < p^3
   1.279                  """
   1.280                  a = 0
   1.281 @@ -1178,7 +1206,8 @@
   1.282                  # to the commitment of ai and ri.
   1.283                  if A1 != A:
   1.284                      raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A))
   1.285 -                # 2) the commitment he received, Bj, is equal to the commitment of bj and sj.
   1.286 +                # 2) the commitment he received, Bj, is equal to the
   1.287 +                # commitment of bj and sj.
   1.288                  if B1 != B:
   1.289                      raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B))
   1.290                  if C1 != C:
   1.291 @@ -1188,8 +1217,8 @@
   1.292                      raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c))
   1.293  
   1.294  
   1.295 -                # 3) the gammaij he received is equal to the gammaij he now computes based on
   1.296 -                # the values he reveives
   1.297 +                # 3) the gammaij he received is equal to the gammaij
   1.298 +                # he now computes based on the values he reveives
   1.299                  for j in xrange(len(ais)):
   1.300                      n = self.players[self.id].pubkey[0]
   1.301                      nsq = n * n
   1.302 @@ -1225,7 +1254,8 @@
   1.303                          ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment)
   1.304                          ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness)
   1.305                          ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1])
   1.306 -                    # Receive and recombine shares if this player is a receiver.
   1.307 +                    # Receive and recombine shares if this player is a
   1.308 +                    # receiver.
   1.309                      else:
   1.310                          send_share(player_id, pc, a)
   1.311                          send_share(player_id, pc, b)
   1.312 @@ -1259,8 +1289,8 @@
   1.313              return dls_all
   1.314  
   1.315          def step6(M_without_test_set):
   1.316 -            """Partition M without test_set in quantity
   1.317 -            random subsets M_i of size (2d + 1).
   1.318 +            """Partition M without test_set in quantity random subsets
   1.319 +            M_i of size (2d + 1).
   1.320              """
   1.321              subsets = []
   1.322              size = 2 * self.d + 1