viff

changeset 703:dc4319f5dd24

Convert viff.shamir to ReST format.
author Martin Geisler <mg@daimi.au.dk>
date Tue, 22 Apr 2008 12:16:17 +0200
parents 5df62a47e9c5
children 0ec32944ab86
files doc/implementation.txt doc/shamir.txt viff/shamir.py
diffstat 3 files changed, 21 insertions(+), 27 deletions(-) [+]
line diff
     1.1 --- a/doc/implementation.txt	Tue Apr 22 12:03:31 2008 +0200
     1.2 +++ b/doc/implementation.txt	Tue Apr 22 12:16:17 2008 +0200
     1.3 @@ -7,3 +7,4 @@
     1.4  .. toctree::
     1.5  
     1.6     field
     1.7 +   shamir
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/doc/shamir.txt	Tue Apr 22 12:16:17 2008 +0200
     2.3 @@ -0,0 +1,6 @@
     2.4 +
     2.5 +Shamir Module
     2.6 +=============
     2.7 +
     2.8 +.. automodule:: viff.shamir
     2.9 +   :members:
     3.1 --- a/viff/shamir.py	Tue Apr 22 12:03:31 2008 +0200
     3.2 +++ b/viff/shamir.py	Tue Apr 22 12:16:17 2008 +0200
     3.3 @@ -17,10 +17,13 @@
     3.4  
     3.5  """Shamir secret sharing and recombination.
     3.6  
     3.7 -Based on the paper "How to share a secret" by Adi Shamir in
     3.8 -I{Communications of the ACM} B{22} (11): 612-613.
     3.9 +Based on the paper *How to share a secret* by Adi Shamir in
    3.10 +*Communications of the ACM* **22** (11): 612-613.
    3.11  """
    3.12  
    3.13 +__docformat__ = "restructuredtext"
    3.14 +
    3.15 +
    3.16  import operator
    3.17  from viff.util import rand
    3.18  
    3.19 @@ -28,6 +31,10 @@
    3.20  def share(secret, threshold, num_players):
    3.21      """Shamir share secret.
    3.22  
    3.23 +    The *threshold* indicates the maximum number of shares that reveal
    3.24 +    nothing about *secret*. The return value is a list of ``(player
    3.25 +    id, share)`` pairs.
    3.26 +
    3.27      It holds that sharing and recombination cancels each other:
    3.28  
    3.29      >>> from field import GF
    3.30 @@ -41,25 +48,12 @@
    3.31      >>> share(Zp(10), 0, 5)
    3.32      [({1}, {10}), ({2}, {10}), ({3}, {10}), ({4}, {10}), ({5}, {10})]
    3.33  
    3.34 -    up to but not including C{num_players}:
    3.35 +    up to but not including *num_players*:
    3.36  
    3.37      >>> share(Zp(10), 5, 5)
    3.38      Traceback (most recent call last):
    3.39        ...
    3.40      AssertionError: Threshold out of range
    3.41 -
    3.42 -    @param secret: the secret to be shared.
    3.43 -    @type secret: a field element
    3.44 -
    3.45 -    @param threshold: maximum number of shares that reveal nothing
    3.46 -    about the secret.
    3.47 -    @type threshold: integer
    3.48 -
    3.49 -    @param num_players: number of players.
    3.50 -    @type num_players: integer
    3.51 -
    3.52 -    @return: shares, one for each player.
    3.53 -    @returntype: C{list} of (player id, share) pairs
    3.54      """
    3.55      assert threshold >= 0 and threshold < num_players, "Threshold out of range"
    3.56  
    3.57 @@ -93,19 +87,17 @@
    3.58  
    3.59  #: Cached recombination vectors.
    3.60  #:
    3.61 -#: The recombination vector used by L{recombine} depends only on the
    3.62 +#: The recombination vector used by `recombine` depends only on the
    3.63  #: recombination point and the player IDs of the shares, and so it can
    3.64  #: be cached for efficiency.
    3.65  _recombination_vectors = {}
    3.66  
    3.67  
    3.68  def recombine(shares, x_recomb=0):
    3.69 -    """Recombines list of (xi, yi) pairs.
    3.70 +    """Recombines list of ``(xi, yi)`` pairs.
    3.71  
    3.72 -    Recombination is done in the optional point M{x}.
    3.73 -
    3.74 -    @param shares: M{threshold+1} shares.
    3.75 -    @type shares: C{list} of (player id, share) pairs
    3.76 +    Shares is a list of *threshold* + 1 ``(player id, share)`` pairs.
    3.77 +    Recombination is done in the optional point *x_recomb*.
    3.78      """
    3.79      xs = [x_i for (x_i, _) in shares]
    3.80      ys = [y_i for (_, y_i) in shares]
    3.81 @@ -137,11 +129,6 @@
    3.82      True
    3.83      >>> verify_sharing(shares, 1)
    3.84      False
    3.85 -    >>>
    3.86 -
    3.87 -    @param shares: The shares to be checked.
    3.88 -    @param degree: The maximum degree of the interpolating polynomial.
    3.89 -    @return: C{True} if the sharing is correct, otherwise C{False}.
    3.90      """
    3.91      used_shares = shares[0:degree+1]
    3.92      for i in range(degree+1, len(shares)+1):