viff

view viff/shamir.py @ 1536:4e36cad23bc1

find changesets by author, revision, files, or words in the commit message
Added doctest for shamir.recombine().
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed Aug 11 11:04:19 2010 +0200 (21 months ago)
parents f933bd327750
children 9c938858c46b
line source
1 # Copyright 2007, 2008 VIFF Development Team.
2 #
3 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
4 #
5 # VIFF is free software: you can redistribute it and/or modify it
6 # under the terms of the GNU Lesser General Public License (LGPL) as
7 # published by the Free Software Foundation, either version 3 of the
8 # License, or (at your option) any later version.
9 #
10 # VIFF is distributed in the hope that it will be useful, but WITHOUT
11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 # Public License for more details.
14 #
15 # You should have received a copy of the GNU Lesser General Public
16 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
17
18 """Shamir secret sharing and recombination. Based on the paper *How to
19 share a secret* by Adi Shamir in *Communications of the ACM* **22**
20 (11): 612-613.
21 """
22
23 import operator
24 from viff.util import rand, fake
25
26
27 @fake(lambda s, t, n: [(s.field(i+1), s) for i in range(n)])
28 def share(secret, threshold, num_players):
29 """Shamir share secret.
30
31 The *threshold* indicates the maximum number of shares that reveal
32 nothing about *secret*. The return value is a list of ``(player
33 id, share)`` pairs.
34
35 It holds that sharing and recombination cancels each other:
36
37 >>> from field import GF
38 >>> Zp = GF(47)
39 >>> secret = Zp(42)
40 >>> recombine(share(secret, 7, 15)[:8]) == secret
41 True
42
43 The threshold can range from zero (for a dummy-sharing):
44
45 >>> share(Zp(10), 0, 5)
46 [({1}, {10}), ({2}, {10}), ({3}, {10}), ({4}, {10}), ({5}, {10})]
47
48 up to but not including *num_players*:
49
50 >>> share(Zp(10), 5, 5)
51 Traceback (most recent call last):
52 ...
53 AssertionError: Threshold out of range
54 """
55 assert threshold >= 0 and threshold < num_players, "Threshold out of range"
56
57 coef = [secret]
58 for j in range(threshold):
59 # TODO: introduce a random() method in FieldElements so that
60 # this wont have to be a long when we are sharing a
61 # GMPIntegerFieldElement.
62 coef.append(rand.randint(0, long(secret.modulus)-1))
63
64 shares = []
65 for i in range(1, num_players+1):
66 # Instead of calculating s_i as
67 #
68 # s_i = s + a_1 x_i + a_2 x_i^2 + ... + a_t x_i^t
69 #
70 # we avoid the exponentiations by calculating s_i by
71 #
72 # s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
73 #
74 # This is a little faster, even for small n and t.
75 cur_point = secret.field(i)
76 cur_share = coef[threshold]
77 # Go backwards from threshold-1 down to 0
78 for j in range(threshold-1, -1, -1):
79 cur_share = coef[j] + cur_share * cur_point
80
81 shares.append((cur_point, cur_share))
82
83 return shares
84
85 #: Cached recombination vectors.
86 #:
87 #: The recombination vector used by `recombine` depends only on the
88 #: recombination point and the player IDs of the shares, and so it can
89 #: be cached for efficiency.
90 _recombination_vectors = {}
91
92
93 @fake(lambda s, x=0: s[0][1])
94 def recombine(shares, x_recomb=0):
95 """Recombines list of ``(xi, yi)`` pairs.
96
97 Shares is a list of *threshold* + 1 ``(player id, share)`` pairs.
98 Recombination is done in the optional point *x_recomb*.
99
100 >>> from field import GF
101 >>> Zp = GF(19)
102 >>> shares = [(Zp(i), 7 * Zp(i) + 3) for i in range(1, 4)]
103 >>> print shares
104 [({1}, {10}), ({2}, {17}), ({3}, {5})]
105 >>> del(shares[1])
106 >>> recombine(shares)
107 {3}
108 """
109 xs, ys = zip(*shares)
110 key = xs + (x_recomb, )
111 try:
112 vector = _recombination_vectors[key]
113 except KeyError:
114 vector = []
115 for i, x_i in enumerate(xs):
116 factors = [(x_k - x_recomb) / (x_k - x_i)
117 for k, x_k in enumerate(xs) if k != i]
118 vector.append(reduce(operator.mul, factors))
119 _recombination_vectors[key] = vector
120 return sum(map(operator.mul, ys, vector))
121
122
123 def verify_sharing(shares, degree):
124 """Verifies that a sharing is correct.
125
126 It is verified that the given shares correspond to points on a
127 polynomial of at most the given degree.
128
129 >>> from field import GF
130 >>> Zp = GF(47)
131 >>> shares = [(Zp(i), Zp(i**2)) for i in range(1, 6)]
132 >>> print shares
133 [({1}, {1}), ({2}, {4}), ({3}, {9}), ({4}, {16}), ({5}, {25})]
134 >>> verify_sharing(shares, 2)
135 True
136 >>> verify_sharing(shares, 1)
137 False
138 """
139 used_shares = shares[0:degree+1]
140 for i in range(degree+1, len(shares)+1):
141 if recombine(used_shares, i) != shares[i-1][1]:
142 return False
143
144 return True
145
146
147 if __name__ == "__main__":
148 import doctest #pragma NO COVER
149 doctest.testmod() #pragma NO COVER