viff

view viff/shamir.py @ 898:ff249565fa3a

find changesets by author, revision, files, or words in the commit message
Added Sigurd to the VIFF team!
author Martin Geisler <mg@daimi.au.dk>
date Mon Aug 25 01:19:50 2008 +0200 (3 years ago)
parents dc4319f5dd24
children 4dd2fedb0a8b
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 __docformat__ = "restructuredtext"
24
25
26 import operator
27 from viff.util import rand
28
29
30 def share(secret, threshold, num_players):
31 """Shamir share secret.
32
33 The *threshold* indicates the maximum number of shares that reveal
34 nothing about *secret*. The return value is a list of ``(player
35 id, share)`` pairs.
36
37 It holds that sharing and recombination cancels each other:
38
39 >>> from field import GF
40 >>> Zp = GF(47)
41 >>> secret = Zp(42)
42 >>> recombine(share(secret, 7, 15)[:8]) == secret
43 True
44
45 The threshold can range from zero (for a dummy-sharing):
46
47 >>> share(Zp(10), 0, 5)
48 [({1}, {10}), ({2}, {10}), ({3}, {10}), ({4}, {10}), ({5}, {10})]
49
50 up to but not including *num_players*:
51
52 >>> share(Zp(10), 5, 5)
53 Traceback (most recent call last):
54 ...
55 AssertionError: Threshold out of range
56 """
57 assert threshold >= 0 and threshold < num_players, "Threshold out of range"
58
59 coef = [secret]
60 for j in range(threshold):
61 # TODO: introduce a random() method in FieldElements so that
62 # this wont have to be a long when we are sharing a
63 # GMPIntegerFieldElement.
64 coef.append(rand.randint(0, long(secret.modulus)-1))
65
66 shares = []
67 for i in range(1, num_players+1):
68 # Instead of calculating s_i as
69 #
70 # s_i = s + a_1 x_i + a_2 x_i^2 + ... + a_t x_i^t
71 #
72 # we avoid the exponentiations by calculating s_i by
73 #
74 # s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
75 #
76 # This is a little faster, even for small n and t.
77 cur_point = secret.field(i)
78 cur_share = coef[threshold]
79 # Go backwards from threshold-1 down to 0
80 for j in range(threshold-1, -1, -1):
81 cur_share = coef[j] + cur_point * cur_share
82
83 shares.append((cur_point, cur_share))
84
85 return shares
86
87 #: Cached recombination vectors.
88 #:
89 #: The recombination vector used by `recombine` depends only on the
90 #: recombination point and the player IDs of the shares, and so it can
91 #: be cached for efficiency.
92 _recombination_vectors = {}
93
94
95 def recombine(shares, x_recomb=0):
96 """Recombines list of ``(xi, yi)`` pairs.
97
98 Shares is a list of *threshold* + 1 ``(player id, share)`` pairs.
99 Recombination is done in the optional point *x_recomb*.
100 """
101 xs = [x_i for (x_i, _) in shares]
102 ys = [y_i for (_, y_i) in shares]
103 try:
104 key = tuple(xs) + (x_recomb, )
105 vector = _recombination_vectors[key]
106 except KeyError:
107 vector = []
108 for i, x_i in enumerate(xs):
109 factors = [(x_k - x_recomb) / (x_k - x_i)
110 for k, x_k in enumerate(xs) if k != i]
111 vector.append(reduce(operator.mul, factors))
112 _recombination_vectors[key] = vector
113 return sum(map(operator.mul, ys, vector))
114
115
116 def verify_sharing(shares, degree):
117 """Verifies that a sharing is correct.
118
119 It is verified that the given shares correspond to points on a
120 polynomial of at most the given degree.
121
122 >>> from field import GF
123 >>> Zp = GF(47)
124 >>> shares = [(Zp(i), Zp(i**2)) for i in range(1, 6)]
125 >>> print shares
126 [({1}, {1}), ({2}, {4}), ({3}, {9}), ({4}, {16}), ({5}, {25})]
127 >>> verify_sharing(shares, 2)
128 True
129 >>> verify_sharing(shares, 1)
130 False
131 """
132 used_shares = shares[0:degree+1]
133 for i in range(degree+1, len(shares)+1):
134 if recombine(used_shares, i) != shares[i-1][1]:
135 return False
136
137 return True
138
139
140 if __name__ == "__main__":
141 import doctest #pragma NO COVER
142 doctest.testmod() #pragma NO COVER