viff

changeset 1262:f626a6dfef43

Merged with Janus.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 08 Oct 2009 14:28:12 +0200
parents ed2d02202af0 bba0fb85c976
children 2fd999c906ca 1deee6ab6af3
files viff/active.py
diffstat 10 files changed, 102 insertions(+), 54 deletions(-) [+]
line diff
     1.1 --- a/doc/active.txt	Thu Oct 08 14:27:37 2009 +0200
     1.2 +++ b/doc/active.txt	Thu Oct 08 14:28:12 2009 +0200
     1.3 @@ -1,6 +1,6 @@
     1.4  
     1.5 -Actively Secure Protocols
     1.6 -=========================
     1.7 +A Thresholdbased Actively Secure Runtime
     1.8 +========================================
     1.9  
    1.10  .. automodule:: viff.active
    1.11  
     2.1 --- a/doc/authors.txt	Thu Oct 08 14:27:37 2009 +0200
     2.2 +++ b/doc/authors.txt	Thu Oct 08 14:28:12 2009 +0200
     2.3 @@ -15,6 +15,7 @@
     2.4  * Marcel Keller <mkeller@cs.au.dk>
     2.5  * Tord Reistad
     2.6  * Ivan Damgård
     2.7 +* Janus Dam Nielsen <janus.nielsen@alexandra.dk>
     2.8  
     2.9  If you have been forgotten, then please checkout `the repository`_,
    2.10  add yourself to the list and `send us a patch`_!
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/doc/constants.txt	Thu Oct 08 14:28:12 2009 +0200
     3.3 @@ -0,0 +1,24 @@
     3.4 +Constants Module
     3.5 +================
     3.6 +
     3.7 +.. automodule:: viff.constants
     3.8 +
     3.9 +   .. attribute:: SHARE
    3.10 +                  ECHO
    3.11 +                  READY
    3.12 +                  SEND
    3.13 +                  PAILLIER
    3.14 +                  TEXT
    3.15 +
    3.16 +      Constants used by :class:`ShareExchanger` and others when sending 
    3.17 +      shares and other messages. They serve to distinguish messages sent 
    3.18 +      with the same program counter from one another.
    3.19 +
    3.20 +   .. attribute::INCONSISTENTHASH
    3.21 +                  OK
    3.22 +                  HASH
    3.23 +                  SIGNAL
    3.24 +
    3.25 +      Constants used by :class:`HashBroadcastMixin` when sending shares
    3.26 +      and other messages. They serve to distinguish messages sent with
    3.27 +      the same program counter from one another.
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/doc/hashbroadcast.txt	Thu Oct 08 14:28:12 2009 +0200
     4.3 @@ -0,0 +1,12 @@
     4.4 +
     4.5 +An Hash Based Broadcast Protocol
     4.6 +================================
     4.7 +
     4.8 +.. automodule:: viff.hash_broadcast
     4.9 +
    4.10 +   .. autoclass:: InconsistentHashException
    4.11 +      :members:
    4.12 +
    4.13 +   .. autoclass:: HashBroadcastMixin
    4.14 +      :members:
    4.15 +
     5.1 --- a/doc/implementation.txt	Thu Oct 08 14:27:37 2009 +0200
     5.2 +++ b/doc/implementation.txt	Thu Oct 08 14:28:12 2009 +0200
     5.3 @@ -13,9 +13,13 @@
     5.4     matrix
     5.5     runtime
     5.6     passive
     5.7 -   active
     5.8 +   active_runtimes
     5.9     paillier
    5.10     comparison
    5.11     prss
    5.12     config
    5.13     aes
    5.14 +   constants
    5.15 +   orlandi
    5.16 +   hashbroadcast
    5.17 +
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/doc/orlandi.txt	Thu Oct 08 14:28:12 2009 +0200
     6.3 @@ -0,0 +1,15 @@
     6.4 +
     6.5 +The Orlandi Runtime - An Actively Secure Protocol with Full Threshold
     6.6 +=======================================================================
     6.7 +
     6.8 +.. automodule:: viff.orlandi
     6.9 +
    6.10 +   .. autoclass:: OrlandiException
    6.11 +      :members:
    6.12 +
    6.13 +   .. autoclass:: OrlandiShare
    6.14 +      :members:
    6.15 +
    6.16 +   .. autoclass:: OrlandiRuntime
    6.17 +      :members:
    6.18 +
     7.1 --- a/doc/runtime.txt	Thu Oct 08 14:27:37 2009 +0200
     7.2 +++ b/doc/runtime.txt	Thu Oct 08 14:28:12 2009 +0200
     7.3 @@ -21,16 +21,6 @@
     7.4           or the data itself if data is received from the other player
     7.5           before we are ready to use it.
     7.6  
     7.7 -   .. attribute:: SHARE
     7.8 -                  ECHO
     7.9 -                  READY
    7.10 -                  SEND
    7.11 -                  PAILLIER
    7.12 -
    7.13 -      Constants used by :class:`ShareExchanger` when sending shares
    7.14 -      and other messages. They serve to distinguish messages sent with
    7.15 -      the same program counter from one another.
    7.16 -
    7.17     .. autofunction:: preprocess
    7.18  
    7.19        See also :ref:`preprocessing` for more background information.
     8.1 --- a/doc/todo.txt	Thu Oct 08 14:27:37 2009 +0200
     8.2 +++ b/doc/todo.txt	Thu Oct 08 14:28:12 2009 +0200
     8.3 @@ -34,13 +34,6 @@
     8.4    make the other honest players crash too, thereby effectively halting
     8.5    the protocol.
     8.6  
     8.7 -Self Trust
     8.8 -----------
     8.9 -
    8.10 -Implement an (actively) secure protocol with threshold ``t = n-1``
    8.11 -based on the "triples approach" of Claudio Orlandi and Jesper Buus
    8.12 -Nielsen. There will soon be a paper describing the protocol.
    8.13 -
    8.14  Covert Adversaries
    8.15  ------------------
    8.16  
     9.1 --- a/viff/active.py	Thu Oct 08 14:27:37 2009 +0200
     9.2 +++ b/viff/active.py	Thu Oct 08 14:28:12 2009 +0200
     9.3 @@ -15,7 +15,7 @@
     9.4  # You should have received a copy of the GNU Lesser General Public
     9.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     9.6  
     9.7 -"""Actively secure protocols."""
     9.8 +"""A thresholdbased actively secure runtime."""
     9.9  
    9.10  __docformat__ = "restructuredtext"
    9.11  
    10.1 --- a/viff/orlandi.py	Thu Oct 08 14:27:37 2009 +0200
    10.2 +++ b/viff/orlandi.py	Thu Oct 08 14:28:12 2009 +0200
    10.3 @@ -345,9 +345,10 @@
    10.4  
    10.5          Communication cost: none.
    10.6  
    10.7 -        Each party ``P_i`` computes:
    10.8 -        ``[z]_i = [x]_i + [y]_i
    10.9 -                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
   10.10 +        Each party ``P_i`` computes::
   10.11 +
   10.12 +          [z]_i = [x]_i + [y]_i
   10.13 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)
   10.14  
   10.15          """
   10.16          def is_share(s, field):
   10.17 @@ -378,9 +379,10 @@
   10.18  
   10.19          Communication cost: none.
   10.20  
   10.21 -        Each party ``P_i`` computes:
   10.22 -        ``[z]_i = [x]_i - [y]_i
   10.23 -                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)``.
   10.24 +        Each party ``P_i`` computes::
   10.25 +
   10.26 +          [z]_i = [x]_i - [y]_i
   10.27 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)
   10.28  
   10.29          """
   10.30          def is_share(s, field):
   10.31 @@ -424,11 +426,11 @@
   10.32          Assume the parties are given a random share ``[r]`` by a trusted dealer. 
   10.33          Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
   10.34  
   10.35 -        1) ``r = OpenTo(P_i, [r]``
   10.36 +        1. ``r = OpenTo(P_i, [r]``
   10.37  
   10.38 -        2) ``P_i broadcasts Delta = r - x``
   10.39 +        2. ``P_i broadcasts Delta = r - x``
   10.40  
   10.41 -        3) ``[x] = [r] - Delta``
   10.42 +        3. ``[x] = [r] - Delta``
   10.43  
   10.44          """
   10.45          # TODO: Communitcation costs?
   10.46 @@ -440,7 +442,7 @@
   10.47          def hack(_, peer_id):
   10.48              # Assume the parties are given a random share [r] by a trusted dealer.
   10.49              share_r = self.random_share(field)
   10.50 -            # 1) r = OpenTo(P_i, [r])
   10.51 +            # 1. r = OpenTo(P_i, [r])
   10.52              open_r = self.open(share_r, [peer_id])
   10.53              def subtract_delta(delta, share_r):
   10.54                  delta = field(long(delta))
   10.55 @@ -676,20 +678,21 @@
   10.56          Assuming a set of multiplicative triples:
   10.57          ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``.
   10.58  
   10.59 -        1) ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
   10.60 +        1. ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
   10.61  
   10.62 -        2) ``for j = 1, ..., 2d+1 do
   10.63 +        2. Compute::
   10.64 +
   10.65 +             for j = 1, ..., 2d+1 do
   10.66               [F_j] = [x] + SUM_i=1^d [f_i]*j^i 
   10.67               and
   10.68 -             [G_j] = [y] + SUM_i=1^d [g_i]*j^i`` 
   10.69 +             [G_j] = [y] + SUM_i=1^d [g_i]*j^i
   10.70  
   10.71 -        3) for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
   10.72 +        3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])``
   10.73  
   10.74 -        4) compute [H_0] = SUM_j=1^2d+1 delta_j[H_j] 
   10.75 +        4. compute ``[H_0] = SUM_j=1^2d+1 delta_j[H_j]`` where 
   10.76 +           ``delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j)``
   10.77  
   10.78 -        5) output [z] = [H_0]
   10.79 -
   10.80 -        delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j).
   10.81 +        5. output ``[z] = [H_0]``
   10.82          """
   10.83          assert isinstance(share_x, Share) or isinstance(share_y, Share), \
   10.84              "At least one of share_x and share_y must be a Share."
   10.85 @@ -703,7 +706,7 @@
   10.86          if cmul_result is not None:
   10.87              return cmul_result
   10.88  
   10.89 -        # 1) for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
   10.90 +        # 1. for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
   10.91          d = (len(M) - 1) // 2
   10.92          deltas = self.compute_delta(d)
   10.93          f = []
   10.94 @@ -787,30 +790,35 @@
   10.95      def triple_gen(self, field):
   10.96          """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
   10.97  
   10.98 -        1) Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
   10.99 -        compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
  10.100 -        broadcast them.
  10.101 +        1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
  10.102 +           compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
  10.103 +           broadcast them.
  10.104  
  10.105 -        2) Every party ``P_j`` does:
  10.106 -           (a) choose random ``b_j, s_j in Z_p X (Z_p)^2``.
  10.107 +        2. Every party ``P_j`` does:
  10.108  
  10.109 -           (b) compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
  10.110 +           a. choose random ``b_j, s_j in Z_p X (Z_p)^2``.
  10.111  
  10.112 -           (c) ``P_j`` do towards every other party:
  10.113 +           b. compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
  10.114 +
  10.115 +           c. ``P_j`` do towards every other party:
  10.116 +
  10.117                  i. choose random ``d_ij in Z_p^3``
  10.118 -               ii. compute and send 
  10.119 -                   ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
  10.120  
  10.121 -        3) Every party ``P_i`` does:
  10.122 -           (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
  10.123 +                ii. compute and send 
  10.124 +                    ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
  10.125  
  10.126 -           (b) pick random ``t_i in (Z_p)^2``, compute and 
  10.127 -               broadcast ``C_i = Com_ck(c_i, t_i)``
  10.128  
  10.129 -        4) Everyone computes:
  10.130 +        3. Every party ``P_i`` does:
  10.131 +
  10.132 +           a. compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
  10.133 +
  10.134 +           b. pick random ``t_i in (Z_p)^2``, compute and 
  10.135 +              broadcast ``C_i = Com_ck(c_i, t_i)``
  10.136 +
  10.137 +        4. Everyone computes:
  10.138             ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
  10.139          
  10.140 -        5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
  10.141 +        5. Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
  10.142             ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
  10.143  
  10.144          """