Re: [viff-devel] A bug in VIFF?
Problem seems to be fixed. I used addCallback several places where I should instead have used schedule_callback. The new changes to VIFF somehow triggered this bug. Best regards, Thomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Hi all
Today, Sebastiaan and I have been doing some serious thinking and
looking into the VIFF code, and we feel convinced that we've found the
bug.
The problem lies entirely in the multiplication protocol. In
Runtime.mul, products of shares are computed and shared. Then secure
Lagrange interpolation runs to reconstruct the original sharing.
With an odd number of players, $n$, and threshold $t = (n-1)/2$ a
contribution is needed from all parties. But if the threshold is lower
or there are more parties, then reconstruction doesn't require all
shares. VIFF uses this to optimize the protocol, using only the first
$2t+1$ shares received.
This doesn't work for the multiplication protocol: Unless shares from
the /same/ parties are used, there will be a mismatch. Say we have
players 1,2,3,4 and a threshold of 1. Each $i$ shares their product
with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then
the polynomial is
P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x)
Another could use 2,3,4, thus interpolating
P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x)
Clearly this is not the same computation! Thus, the parties end up
with inconsistent shares -- they have points on different polynomials.
To solve the problem, the players must agree on which shares are used. A
simple solution is to require all shares present. Alternatively (for the
passive case) we could say that only the first $2t+1$ parties share the
products of their shares. This basically eliminates any need for any of
the other parties.
Regards,
Tomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
[EMAIL PROTECTED] writes:
Hi all
Today, Sebastiaan and I have been doing some serious thinking and
looking into the VIFF code, and we feel convinced that we've found the
bug.
Great work, thanks to both of you for solving the mystery! I guess this
bug is sufficiently grave that we should do a 0.7.1 release to fix it.
So let me know if you've found other weird things...
The problem lies entirely in the multiplication protocol. In
Runtime.mul, products of shares are computed and shared. Then secure
Lagrange interpolation runs to reconstruct the original sharing.
With an odd number of players, $n$, and threshold $t = (n-1)/2$ a
contribution is needed from all parties. But if the threshold is lower
or there are more parties, then reconstruction doesn't require all
shares. VIFF uses this to optimize the protocol, using only the first
$2t+1$ shares received.
This doesn't work for the multiplication protocol: Unless shares from
the /same/ parties are used, there will be a mismatch. Say we have
players 1,2,3,4 and a threshold of 1. Each $i$ shares their product
with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then
the polynomial is
P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x)
Another could use 2,3,4, thus interpolating
P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x)
Clearly this is not the same computation! Thus, the parties end up
with inconsistent shares -- they have points on different polynomials.
To solve the problem, the players must agree on which shares are used.
A simple solution is to require all shares present. Alternatively (for
the passive case) we could say that only the first $2t+1$ parties
share the products of their shares. This basically eliminates any need
for any of the other parties.
That would be a good idea, also for performance. I suggest that we use a
round-robin system where we determine the perticipating subset based on
the current program counter.
So far I have a failing unit test which clearly shows the bug, I'll try
and fix it now.
--
Martin Geisler
pgpFQx5rzicnb.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Martin Geisler [EMAIL PROTECTED] writes:
That would be a good idea, also for performance. I suggest that we use
a round-robin system where we determine the perticipating subset based
on the current program counter.
Code for this would look like this:
diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -39,7 +39,7 @@
from collections import deque
from viff import shamir
-from viff.prss import prss, prss_lsb, prss_zero
+from viff.prss import prss, prss_lsb, prss_zero, generate_subsets
from viff.field import GF256, FieldElement
from viff.util import wrapper, rand
@@ -703,6 +703,18 @@
def __init__(self, player, threshold, options=None):
Initialize runtime.
BasicRuntime.__init__(self, player, threshold, options)
+self.subsets = {}
+
+def select_subset(self, threshold):
+Select subset for *threshold* based on current program counter.
+try:
+subsets = self.subsets[threshold]
+except KeyError:
+players = frozenset(range(1, self.num_players+1))
+subsets = list(generate_subsets(players, 2*threshold + 1))
+self.subsets[threshold] = subsets
+return subsets[hash(tuple(self.program_counter)) % len(subsets)]
+
@increment_pc
def open(self, share, receivers=None, threshold=None):
(perhaps with an @increment_pc decorator...)
So far I have a failing unit test which clearly shows the bug, I'll
try and fix it now.
I've pushed the new unit tests as revision 4daa42544157, but I'm afraid
I'm too tired to fix things tonight... feel free to jump in :-)
--
Martin Geisler
pgpO73AHmQUgo.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Hi,
Tomas is right, of course. For the passive case, using the first 2t+1 players
always works, and for the active case, we do not use the
local-multiply-and-reshare method anyway. The current implementation of active
security has
a preprocessing step based on either PRSS or hyper invertible matrices, and a
computation phase where all we do is that we open shared values. Neither phase
has the problem encountered here.
regards, Ivan
Quoting [EMAIL PROTECTED]:
Hi all
Today, Sebastiaan and I have been doing some serious thinking and
looking into the VIFF code, and we feel convinced that we've found the
bug.
The problem lies entirely in the multiplication protocol. In
Runtime.mul, products of shares are computed and shared. Then secure
Lagrange interpolation runs to reconstruct the original sharing.
With an odd number of players, $n$, and threshold $t = (n-1)/2$ a
contribution is needed from all parties. But if the threshold is lower
or there are more parties, then reconstruction doesn't require all
shares. VIFF uses this to optimize the protocol, using only the first
$2t+1$ shares received.
This doesn't work for the multiplication protocol: Unless shares from
the /same/ parties are used, there will be a mismatch. Say we have
players 1,2,3,4 and a threshold of 1. Each $i$ shares their product
with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then
the polynomial is
P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x)
Another could use 2,3,4, thus interpolating
P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x)
Clearly this is not the same computation! Thus, the parties end up
with inconsistent shares -- they have points on different polynomials.
To solve the problem, the players must agree on which shares are used. A
simple solution is to require all shares present. Alternatively (for the
passive case) we could say that only the first $2t+1$ parties share the
products of their shares. This basically eliminates any need for any of
the other parties.
Regards,
Tomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Tomas is right, of course. For the passive case, using the first 2t+1 players always works, and for the active case, we do not use the local-multiply-and-reshare method anyway. The thing is, I always just assumed that we always used the same set of shares, and it is kind of easy to miss if you just read quickly through it - it says what you expect. I guess that's why we all missed it until now. The unit tests should not be hardcoded to n=3, t=1 as they are now, because that's why we never found the problem in the first place. I can rewrite the unit tests to the general setting. It needs to be done. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Hoogh, S.J.A. de [EMAIL PROTECTED] writes: Hi Sebastiaan I've looked at your code, and I don't understand the final part, the one which is supposed to calculate the sorted order of the millionaires: # We can establish the correct order of Millionaires 2 and 3. comparison = [5] if m1_gt_m2 and m1_gt_m3 and m1_gt_m4 and m1_gt_m5: comparison = [1] elif not m1_gt_m2 and m2_gt_m3 and m2_gt_m4 and m2_gt_m5: comparison = [2] elif not m1_gt_m3 and not m2_gt_m3 and m3_gt_m4 and m3_gt_m5: comparison = [3] elif not m1_gt_m4 and not m2_gt_m4 and not m3_gt_m4 and m4_gt_m5: comparison = [4] The original code is here: http://hg.viff.dk/viff/file/153c24a4a6c5/apps/millionaires.py#l115 and it works by ordering the numbers 1, 2, 3 by hand in the comparison list: it first checks to see if 2 and 3 should be ordered [3, 2] or [2, 3] and it then puts the number 1 into this list in the right spot. The final output is thus something like this: I am Millionaire 1 and I am worth 193 millions. From poorest to richest: Millionaire 3 Millionaire 2 Millionaire 1 (193 millions) and I can understand why you don't get this output with your code. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Thanks for your early feedback. I am running ViFF 0.6 so I will upgrade right now and tell you whether the problem is still there. Sebastiaan -Original Message- From: Martin Geisler [mailto:[EMAIL PROTECTED] Sent: woensdag 1 oktober 2008 9:39 To: Hoogh, S.J.A. de Cc: viff-devel@viff.dk Subject: Re: FW: Bug in ViFF Hoogh, S.J.A. de [EMAIL PROTECTED] writes: Hi Sebastiaan, Thanks for giving VIFF some exercise! :-) Tomas Toft and I are using ViFF to analyze Toft's secure Linear Programming protocol. At the first sight everything seemed to work nicely, but when trying to increase the number of participants and the threshold we've found an annoying fact about ViFF: The threshold should be given explicitly when creating the runtime in any ViFF program. ViFF doesn't check whether this threshold matches with the parameters given in the configuration files. Wouldn't it be nicer if the threshold is read by create_runtime(id, players, threshold, options, Toft05Runtime) automatically? You mean that the threshold should be put in the player-X.ini files? I guess that is a good idea... As it is now, VIFF simply trusts you to get everything right -- it lets you pretend that you know what you are doing :-) The threshold used when generating config files determines the threshold for PRSS, whereas the threshold given to create_runtime determines the threshold for Shamir sharings. Now that I think of it, it seems natural to put both thresholds in the config files and unite them at the same time. Now doing this consistently and setting #players =3 and threshold =1 works and setting #players=5 and threshold=2 also works. However, there seems to be some bug somewhere when trying #players=5 and threshold=1. I've altered the millionaires.py such that it deals with 5 players instead of three and it provides correct output if threshold=2 but correct output for the participants 1, 2 and 3 only (and junk for players 4 and 5) if threshold=1... Hmm, that is bad... did you generalize millionaires.py so that there can be 4, 5, ... millionaires? How did you sort the inputs -- like it is done in sort.py? In addition, if I create the config-files with 5 players and threshold=1 and if I put threshold=2 in the millionaires program, it works again, i.e., provides correct output Hopefully, this information helps you finding the bug. If anything needs some clarification I'm happy to provide you more details... Is this with version 0.7, which was just released? Also, can you send us the modified millionaires.py program? I have recently tested multiplications with (n, t) = (25, 8) and it ran fine, but I must admit that I did not check that the results were correct, I only made sure that the benchmarks could be run. -- Martin Geisler millionaires-5.py Description: millionaires-5.py ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Nope, Also with version 0.7 exactly the same problem occurs. Sincerely, Sebastiaan -Original Message- From: Martin Geisler [mailto:[EMAIL PROTECTED] Sent: woensdag 1 oktober 2008 9:39 To: Hoogh, S.J.A. de Cc: viff-devel@viff.dk Subject: Re: FW: Bug in ViFF Hoogh, S.J.A. de [EMAIL PROTECTED] writes: Hi Sebastiaan, Thanks for giving VIFF some exercise! :-) Tomas Toft and I are using ViFF to analyze Toft's secure Linear Programming protocol. At the first sight everything seemed to work nicely, but when trying to increase the number of participants and the threshold we've found an annoying fact about ViFF: The threshold should be given explicitly when creating the runtime in any ViFF program. ViFF doesn't check whether this threshold matches with the parameters given in the configuration files. Wouldn't it be nicer if the threshold is read by create_runtime(id, players, threshold, options, Toft05Runtime) automatically? You mean that the threshold should be put in the player-X.ini files? I guess that is a good idea... As it is now, VIFF simply trusts you to get everything right -- it lets you pretend that you know what you are doing :-) The threshold used when generating config files determines the threshold for PRSS, whereas the threshold given to create_runtime determines the threshold for Shamir sharings. Now that I think of it, it seems natural to put both thresholds in the config files and unite them at the same time. Now doing this consistently and setting #players =3 and threshold =1 works and setting #players=5 and threshold=2 also works. However, there seems to be some bug somewhere when trying #players=5 and threshold=1. I've altered the millionaires.py such that it deals with 5 players instead of three and it provides correct output if threshold=2 but correct output for the participants 1, 2 and 3 only (and junk for players 4 and 5) if threshold=1... Hmm, that is bad... did you generalize millionaires.py so that there can be 4, 5, ... millionaires? How did you sort the inputs -- like it is done in sort.py? In addition, if I create the config-files with 5 players and threshold=1 and if I put threshold=2 in the millionaires program, it works again, i.e., provides correct output Hopefully, this information helps you finding the bug. If anything needs some clarification I'm happy to provide you more details... Is this with version 0.7, which was just released? Also, can you send us the modified millionaires.py program? I have recently tested multiplications with (n, t) = (25, 8) and it ran fine, but I must admit that I did not check that the results were correct, I only made sure that the benchmarks could be run. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
