viff

changeset 1241:6693b04e60a4

Documentation for the Orlandi runtime.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Thu, 08 Oct 2009 11:55:36 +0200
parents 986c5b82c655
children fdf5959db257
files doc/implementation.txt doc/orlandi.txt viff/orlandi.py
diffstat 3 files changed, 59 insertions(+), 34 deletions(-) [+]
line diff
     1.1 --- a/doc/implementation.txt	Thu Oct 08 11:53:47 2009 +0200
     1.2 +++ b/doc/implementation.txt	Thu Oct 08 11:55:36 2009 +0200
     1.3 @@ -20,3 +20,5 @@
     1.4     config
     1.5     aes
     1.6     constants
     1.7 +   orlandi
     1.8 +
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/doc/orlandi.txt	Thu Oct 08 11:55:36 2009 +0200
     2.3 @@ -0,0 +1,15 @@
     2.4 +
     2.5 +An Actively Secure Protocol with Self Trust
     2.6 +===========================================
     2.7 +
     2.8 +.. automodule:: viff.orlandi
     2.9 +
    2.10 +   .. autoclass:: OrlandiException
    2.11 +      :members:
    2.12 +
    2.13 +   .. autoclass:: OrlandiShare
    2.14 +      :members:
    2.15 +
    2.16 +   .. autoclass:: OrlandiRuntime
    2.17 +      :members:
    2.18 +
     3.1 --- a/viff/orlandi.py	Thu Oct 08 11:53:47 2009 +0200
     3.2 +++ b/viff/orlandi.py	Thu Oct 08 11:55:36 2009 +0200
     3.3 @@ -345,9 +345,10 @@
     3.4  
     3.5          Communication cost: none.
     3.6  
     3.7 -        Each party ``P_i`` computes:
     3.8 -        ``[z]_i = [x]_i + [y]_i
     3.9 -                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
    3.10 +        Each party ``P_i`` computes::
    3.11 +
    3.12 +          [z]_i = [x]_i + [y]_i
    3.13 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)
    3.14  
    3.15          """
    3.16          def is_share(s, field):
    3.17 @@ -378,9 +379,10 @@
    3.18  
    3.19          Communication cost: none.
    3.20  
    3.21 -        Each party ``P_i`` computes:
    3.22 -        ``[z]_i = [x]_i - [y]_i
    3.23 -                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)``.
    3.24 +        Each party ``P_i`` computes::
    3.25 +
    3.26 +          [z]_i = [x]_i - [y]_i
    3.27 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)
    3.28  
    3.29          """
    3.30          def is_share(s, field):
    3.31 @@ -424,11 +426,11 @@
    3.32          Assume the parties are given a random share ``[r]`` by a trusted dealer. 
    3.33          Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
    3.34  
    3.35 -        1) ``r = OpenTo(P_i, [r]``
    3.36 +        1. ``r = OpenTo(P_i, [r]``
    3.37  
    3.38 -        2) ``P_i broadcasts Delta = r - x``
    3.39 +        2. ``P_i broadcasts Delta = r - x``
    3.40  
    3.41 -        3) ``[x] = [r] - Delta``
    3.42 +        3. ``[x] = [r] - Delta``
    3.43  
    3.44          """
    3.45          # TODO: Communitcation costs?
    3.46 @@ -440,7 +442,7 @@
    3.47          def hack(_, peer_id):
    3.48              # Assume the parties are given a random share [r] by a trusted dealer.
    3.49              share_r = self.random_share(field)
    3.50 -            # 1) r = OpenTo(P_i, [r])
    3.51 +            # 1. r = OpenTo(P_i, [r])
    3.52              open_r = self.open(share_r, [peer_id])
    3.53              def subtract_delta(delta, share_r):
    3.54                  delta = field(long(delta))
    3.55 @@ -676,20 +678,21 @@
    3.56          Assuming a set of multiplicative triples:
    3.57          ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``.
    3.58  
    3.59 -        1) ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
    3.60 +        1. ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
    3.61  
    3.62 -        2) ``for j = 1, ..., 2d+1 do
    3.63 +        2. Compute::
    3.64 +
    3.65 +             for j = 1, ..., 2d+1 do
    3.66               [F_j] = [x] + SUM_i=1^d [f_i]*j^i 
    3.67               and
    3.68 -             [G_j] = [y] + SUM_i=1^d [g_i]*j^i`` 
    3.69 +             [G_j] = [y] + SUM_i=1^d [g_i]*j^i
    3.70  
    3.71 -        3) for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
    3.72 +        3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])``
    3.73  
    3.74 -        4) compute [H_0] = SUM_j=1^2d+1 delta_j[H_j] 
    3.75 +        4. compute ``[H_0] = SUM_j=1^2d+1 delta_j[H_j]`` where 
    3.76 +           ``delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j)``
    3.77  
    3.78 -        5) output [z] = [H_0]
    3.79 -
    3.80 -        delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j).
    3.81 +        5. output ``[z] = [H_0]``
    3.82          """
    3.83          assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    3.84              "At least one of share_x and share_y must be a Share."
    3.85 @@ -703,7 +706,7 @@
    3.86          if cmul_result is not None:
    3.87              return cmul_result
    3.88  
    3.89 -        # 1) for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
    3.90 +        # 1. for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
    3.91          d = (len(M) - 1) // 2
    3.92          deltas = self.compute_delta(d)
    3.93          f = []
    3.94 @@ -787,30 +790,35 @@
    3.95      def triple_gen(self, field):
    3.96          """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
    3.97  
    3.98 -        1) Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
    3.99 -        compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
   3.100 -        broadcast them.
   3.101 +        1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
   3.102 +           compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
   3.103 +           broadcast them.
   3.104  
   3.105 -        2) Every party ``P_j`` does:
   3.106 -           (a) choose random ``b_j, s_j in Z_p X (Z_p)^2``.
   3.107 +        2. Every party ``P_j`` does:
   3.108  
   3.109 -           (b) compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
   3.110 +           a. choose random ``b_j, s_j in Z_p X (Z_p)^2``.
   3.111  
   3.112 -           (c) ``P_j`` do towards every other party:
   3.113 +           b. compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
   3.114 +
   3.115 +           c. ``P_j`` do towards every other party:
   3.116 +
   3.117                  i. choose random ``d_ij in Z_p^3``
   3.118 -               ii. compute and send 
   3.119 -                   ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
   3.120  
   3.121 -        3) Every party ``P_i`` does:
   3.122 -           (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
   3.123 +                ii. compute and send 
   3.124 +                    ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
   3.125  
   3.126 -           (b) pick random ``t_i in (Z_p)^2``, compute and 
   3.127 -               broadcast ``C_i = Com_ck(c_i, t_i)``
   3.128  
   3.129 -        4) Everyone computes:
   3.130 +        3. Every party ``P_i`` does:
   3.131 +
   3.132 +           a. compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
   3.133 +
   3.134 +           b. pick random ``t_i in (Z_p)^2``, compute and 
   3.135 +              broadcast ``C_i = Com_ck(c_i, t_i)``
   3.136 +
   3.137 +        4. Everyone computes:
   3.138             ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
   3.139          
   3.140 -        5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
   3.141 +        5. Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
   3.142             ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
   3.143  
   3.144          """