[viff-devel] The primitives of MPC
If you boil down VIFF, or any MPC program you can boil it down to 5 primitives. These primitives are x + y = z Addition x * y = z Multiplication -x = z Negation z = Share(x)Secret sharing z = Reveal(x) Revealing of a secret sharing My question is now: What are the second order primitives? What are the basic features that, make a programmers life easy but not essential. I would propose the following 5: z = f(x,y) Function calls for(0 to n)A for call with a fixed number of iterations. z = Rand(x)Generating random values in Zp x = y Equation x < y Comparison while( x ) A while loop on x, where x is a revealed value The first 2 primitives are easy since they are already implemented using the underlying programming language. Should creating random values be on this list? Or should it maybe be among the first order primitives, a basic building block of MPC. Equation and comparison are obvious second order primitives and has been my research topic for many years. The last on the list is the while loop, I have included it because I have seen many times that you want to compute some function, open a variable, check some information and then redo the function if the revealed value was false. This can be found when creating random values less than some threshold, creating RSA primes, and many other algorithms. Also it is not trivial to program if you want it to be efficient. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] A java implementation of VIFF
Hello, As some of you might know I have not programmed that much in VIFF because I am more familiar with C++ and Java than Python as a programming language. Therefore I have now created a Java rival to VIFF. Taking all the good design principles from VIFF and adding some things that VIFF cannot offer such as multi-threading. The program still has one drawback, in that the different players communicate over Java queues, and these queues cannot communicate through sockets. Therefore it is not a complete MPC implementation. The following things have been implemented: Sharing, Negation and Revealing of Shares. Adding and Multiplication between Shares and/or Field elements. The shares are computed using Shamir's secret sharing scheme. The algorithm, sharing scheme and communication parts have all been separated so it can be modified easily. The whole program was programmed and tested in just 34 hours (including 6 hours sleep). It contains 2115 lines of code and 32 classes, some parts where heavily influenced by previous programming attempts. Programmed in NetBeans. For anyone interested in the code I have dropped of a zip of the code at http://drop.io/tordpaper/ Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Error when coding with callbacks and reveals
Hello,
Continuing on my previous email about how to code things in VIFF. I
hereby present the complete test code.
It seems my calculations are done at the same time that the reactor is
closing down so sometimes my code does not return any printed values.
This is a mistake, either in my understanding of VIFF or in the
framework itself.
See the two runs below.
C:\Documents and Settings\item\Desktop\VIFF\viff-dev\apps>tir_test.py
--no-ssl player-3.ini
Seeding random generator with random seed 5522
Not using SSL
Listening on port 9003
Synchronizing shutdown... done.
Closing connections... Comparing [{6}] to 0
Result [{12}]
Result True
done.
Stopping reactor... done.
C:\Documents and Settings\item\Desktop\VIFF\viff-dev\apps>tir_test.py
--no-ssl player-3.ini
Seeding random generator with random seed 3023
Not using SSL
Listening on port 9003
Synchronizing shutdown... done.
Closing connections... done.
Stopping reactor... done.
#!/usr/bin/python
# Copyright 2007, 2008 VIFF Development Team.
#
# This file is part of VIFF, the Virtual Ideal Functionality Framework.
#
# VIFF is free software: you can redistribute it and/or modify it
# under the terms of the GNU Lesser General Public License (LGPL) as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
#
# VIFF is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
# Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see
[viff-devel] How to structure code with callbacks
Hello, I have a problem with how to structure codes with much callback in VIFF. I want to do some stuff with shares, reveal some values, do more calculations with shares, reveal more values, and so on. For illustration purposes, lets say I have a bitwise secret shared value r (r and r_as_bits), and I want to compute c = x + r. Then reveal c and print it and reveal c. But this is only done if bits of r are not all zero. Below is the psudocode and the real code. The real code does not work, because it will return the last result only if the reactor is not shut down prematurely. So my question is how do I get a working program that looks more like my psaudocode? psaudocode: -- def protocol(r_as_bits, mask, r, x): test = test_not_all_zero(r_as_bits, mask) if test == True c = r + x c = open(c) print c else print "False" def test_not_all_zero(r_as_bits, mask) #reveal (sum(bits) - number_of_bits)*mask temp = sum(r_as_bits[:]) - len(r_as_bits)) * mask temp = open(temp) if temp == 0 return False return True - real code:def protocol_part_1(self, r_as_bits, r, mask, x): test = self.test_not_all_zero(r_as_bits, mask) self.r = r self.x = x return test.addCallback(self.protocol_part_2) def protocol_part_2(self, test): if test: c = self.r + self.x c_open = self.runtime.open(c) result = gather_shares([c_open]) callback_result = result.addCallback(self.print_answer) return callback_result else: print "No value, False" return False def print_answer(self, value): print "Result ", value return True def test_not_all_zero(self, r_as_bits, mask): #reveal (sum(bits))*mask temp = sum(r_as_bits[:]) * mask temp_open = self.runtime.open(temp) def check_result(check): print "Comparing ", check, " to 0" if check[0].value == 0: return False return True ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Off topic question "multiparty" or "multi-party"
Good I talked it over with my advisor and him and me agreed on "multiparty", but it is good to hear that a native English speaker has complained and wanted it to be written as multiparty also. Like Claudio wrote in his mail I also vote for MPC for the short form. Martin Geisler wrote: Tord Ingolf Reistad writes: Hi Tord An off topic question about how to write "Secure Multiparty Compuations", should it be "multiparty" or "multi-party" The front page of VIFF.dk uses "multi-party", but resent papers such as "Multiparty computation goes live" uses the other version. So which should we go for, which should be the standard? Excellent question! :-) I have also been annoyed by this... Originally I always wrote "multi-party" as you see it on the VIFF homepage, but Ivan told me that a native English speaker had complained to him about the hyphen (not on the homepage, but in a paper by Ivan). So now I'm writing "multiparty" instead. I still insist on using "MP" as an abbreviation, just like you would abbreviate "database" as "DB" and not just "D". So for me it's "SMPC" and not just "SMC". ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Off topic question "multiparty" or "multi-party"
Hello, An off topic question about how to write "Secure Multiparty Compuations", should it be "multiparty" or "multi-party" The front page of VIFF.dk uses "multi-party", but resent papers such as "Multiparty computation goes live" uses the other version. So which should we go for, which should be the standard? Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Stand alone java version of comparison (proof-of-concept)
To anyone interested,
Attached is a stand alone proof-of-concept for a faster comparison of
secret shared values. When I say proof-of-concept it is that the shares
are just simulated as there is no real communication (or sharing) going
on. Other than that this file contains all the code needed.
The file contains 3 classes, 2 of which should be taken from a real library.
ZpValue - class for elements of Zp (note based on integers)
ZpShare - dummy class for shares of Zp
(the internal operation of ZpShare is for test purposes only)
TestComparisonStandAlone - all the code needed to do comparison once a
real implementation of ZpValue and ZpShare is done.
So just load this file into your favourite java interpreter (add it to a
packet of files) and you are ready to test it. All code tested and
verified to be correct.
Tord
PS: Not verified to be correct in the strictly mathematical sense, but
verified to be correct for all elements of Zp = 31, 1009 and 1031.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package MPC.Test;
import java.util.Random;
/**
*
* @author to...@stud.ntnu.no
*///ZpValue is an element in a field.
//Assuming field size is a positive value between 0 and 2^31-1
//bit 0 is the Least Significant Bit
class ZpValue {
private static java.util.Random mRandom = new Random();
private int mValue;
private int mField;
public ZpValue(int value, int field) {
//Works for negative also (value % field) can return negative values
mValue = ((value % field) + field) % field;
mField = field;
}
public int getValue() {
return mValue;
}
public int getField() {
return mField;
}
public static int getFieldLengthInBits(int fieldSize) {
int temp = fieldSize;
for (int i = 0; i < 31; i++) {
if (temp == 0) {
return i;
} else {
temp = temp / 2;
}
}
return 31;
}
@Override
public String toString() {
return Integer.toString(mValue);
}
public static String print(ZpValue[] bits) {
String temp = "";
for (int i = bits.length - 1; i >= 0; i--) {
temp = temp.concat(bits[i].toString());
}
return temp;
}
public ZpValue add(ZpValue a) {
if (this.mField != a.mField) {
return null;
} else {
return new ZpValue(mValue + a.mValue, mField);
}
}
public ZpShare add(ZpShare a) {
return new ZpShare(add((ZpValue) a));
}
public ZpValue sub(ZpValue a) {
if (this.mField != a.mField) {
return null;
} else {
return new ZpValue(mValue - a.mValue, mField);
}
}
public ZpShare sub(ZpShare a) {
return new ZpShare(sub((ZpValue) a));
}
public ZpValue mult(ZpValue b) {
if (this.mField != b.mField) {
return null;
} else {
long temp = mValue * b.mValue;
return new ZpValue((int) (temp % mField), mField);
}
}
public ZpShare mult(ZpShare a) {
return new ZpShare(mult((ZpValue) a));
}
// Returns x^{-1}
public ZpValue invert() {
int exp = mValue;
int temp = 1;
int tempF = mField - 2;
for (int i = 0; i < 31; i++) {
if (1 == tempF % 2) {
temp = (int) ((long) temp * (long) exp) % mField;
}
tempF = tempF / 2;
exp = (int) (((long) exp * (long) exp) % mField);
}
return new ZpValue(temp, mField);
}
public static ZpValue randomValue(int fieldSize) {
return new ZpValue(mRandom.nextInt(fieldSize), fieldSize);
}
public static ZpValue nonZeroRandomValue(int fieldSize) {
return new ZpValue(mRandom.nextInt(fieldSize - 1) + 1, fieldSize);
}
public static ZpValue randomBit(int fieldSize) {
return new ZpValue(mRandom.nextInt(2), fieldSize);
}
public ZpValue[] splitInt(int value) {
//Splits value into bits
int BitLength = ZpValue.getFieldLengthInBits(mField);
ZpValue[] ZpArray = new ZpValue[BitLength];
int temp = value;
for (int i = 0; i < BitLength; i++) {
ZpArray[i] = new ZpValue(temp % 2, mField);
temp = temp / 2;
}
return ZpArray;
}
public ZpValue xor(ZpValue a) {
ZpValue temp = this.add(a);
if (temp.getValue() == 2) {
temp = new ZpValue(0, temp.getField());
}
return temp;
}
public ZpValue[] split() {
return splitInt(mValue);
}
public ZpValue[] splitField() {
return splitInt(mField);
}
public static ZpValue join(ZpValue[] array) {
//Combines 31 bits (or less) into a value
if (array.length > 31) {
return null;
}
int temp = 0;
Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?
I have been thinking about the same things when I was doing my project. I do not know how VIFF works, but it would be interesting to know. My thinking about this problem is that if you are going to have a very large MPC program using the same ideas as VIFF, then you need to: 1) Have at least two threads, one thread that creates the deferred elements and one that handles incoming messages (from other players). A third thread which is invisible to the program is the tread handling incoming messages and putting them in a buffer. 2)Have algorithms that create more elements if there is room in the stack. (This can be done by the thread creating the deferred elements, which has a counter of how many elements that are created, the tread pauses if it reaches a threshold when creating new deferred elements. The tread continues when the number of deferred elements is below the threshold again). 3)Have algorithms that destroy already used elements that are not needed any more. (This can be done by the tread handling incoming shares. Each share need a list of deferred elements that are connected to it and when a deferred element is computed it is deleted from the list, when the list is empty the element is deleted). 4)Have algorithms that delay incoming shares if these shares are not created yet. 5)Have algorithms checking that someone is not just clogging up the incoming shares stack with dummy messages. 2extra)When you delete messages because no new deferred elements need them then you can get situations in big programs that an element is deleted, but it is suddenly needed far from where it was first created. Tord t.t...@cwi.nl wrote: Hi all, A really unpleasant thought has occurred to me: Is VIFF really properly asynchronous? (Yes, this question is intended to provoke you into thinking about the issue below. Of course VIFF is asynchronous in the sense that there are no rounds.) If I understand/remember correctly, VIFF is 100% single threaded. This means that if we have a small program: x, y = runtime.shamir_share([1, 2], Zp, input) z = x*y for i in xrange(100): z=z*z 1) We first share two values (returning immediately). 2) We start doing a lot of multiplications. However, as we don't have the actual shares yet, we just get deferreds. 3) Once the for-loop terminates, we return control to the surroundings. At this point we notice that the shares of x and y are there and start the actual multiplication protocols. Is my interpretation above correct? Because if it is, then this really explains the memory issues I've been seeing. And more importantly, it tells us how to actually use VIFF for large-scale computation: put in explicit "stops". The problem is that new python objects are created in each iteration of the loop, but the program does not try to get rid of any of the old ones by actually processing them. With 100 iterations, this is not a big deal, but if this is replaced by 1 or 100 (which is not unreasonable), it really becomes a problem. 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
[viff-devel] How to convert field elements to integers?
Hello, I have a simple question: After completing a VIFF program I have opened the shares and gotten the results, but the results are field elements (probably elements of class GFElement), how do I turn them back into integers? The documentation says nothing about how to turn them back into integers, which should be essencial if I am going to use these shares in other applications. There seems to be some code __repr__ in GFElements, but I cannot see how I can use it. As an additional problem, the integers should not be integers in the set form 0 to p-1, but integers from -(p-1)/2 to +(p-1)/2. How should one do that efficiently? Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
Tomas Toft wrote: Hi Tord et. al. Tord Ingolf Reistad wrote: Hello all, As you are discussing implementing the algorithm from ICITS07, I have improved on that to get a very effective algorithm. For p = 2^l - 1 and using psaudorandom secret sharing. The comparison can be done in 5 rounds and 5l multiplications. The algorithm has never been published, but attached is a java implementation of the algorithm. (There might be an error in the faun in algorithm as that is not tested). I think there is, specifically I believe that the output of CompareBitwiseRandomKnownReturnValueX can be wrong. Or rather: As far as I can see the output will *always* be even. All the (prefix) xor's computed in the faun-in (ITYM fan-in :-) will be 1 until the first differing position, i, is hit and from then on even. Computing Share Returnval = new Share(0L); for (int i=0; i Yes, it might be wrong, I have not have time to look at it in detail. I got as far as checking that the random values created where ok, and then the rest was done somewhat fast and never tested. I will look closer at the code again when I have finished programming another thing I am working on. (No, not my thesis, but a full implementation of MPC in java, so I can get some real results for my thesis). then sums zeros (rnotc == 0) or even values (xor[i] will be even when they start to differ, and 2*1 is even). If I'm right, the just use xor[i-1] instead (or xor[i+1] -- I can't get these arrays right in my head once they are reversed a few times). Or did I miss the spot where you do this? Unfortunately I do not have a phyton implementation of it, as I am bad at programming in phyton, on the other hand I am working on a java implementation of MPC, which should be ready in a month. If anyone else want to try to implement it in phyton I will be more than happy to help. Deal! At least regarding the help :-) I think that comparisonRestricted is entirely correct, but I do not understand what goes on in CompareBitwiseRandomKnown. This might be due to bugs, but can also just be me not understanding your code. Three very specific questions: 1) You write temp = rand[highestbit-1].mpcmult(BigInteger.valueOf(-1)); // -r_h From the comments it seems you want Random[highestbit-1] rather than rand[highestbit-1] Is this right? If not, what is the intuition? The intuition is to avoid overflow. We have created a value x < 2^((l/2)+1), and we want to find the last bit. Now when adding with a random value we might get an overflow in the field, but as we have the highest bit of r as a separate value, we can test for that. So we create two values c0Low or c0High which is the lowest bit of c given either that c=x+r(-2^(l-1)). Now in one of these cases there will be no overflow and in that case x0 = c0 xor r0. 2) You write int highestbit = Field.getBaseField().bitLength(); BigInteger SetHighbit = BigInteger.ZERO; SetHighbit.flipBit(highestbit); Field highBitSet = new Field(SetHighbit); Do you mean SetHighbit.flipBit(highestbit - 1); ? It seems that you want to find the value you would have gotten if Random did not have it's top bit set in the case when it actually does. See above comment for intuition, I cannot check the code today. 3) Have you forgotten to xor the return value with Random[0]? Probably. /Tomas To understand the code please start with the function public Share comparisonRestricted(Share a, Share b) and please observe that many small functions on the top are just returning values instead of shares, this is for test purposes. Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
Yes, as you said the best published algorithm is from ICITS07, but that has still to be implemented in some program. A correction to my previous statements: The 5*l multiplication-solution is for restricted inputs [a < b], where [a], [b] < p/2, so for arbitrary elements in the field you have to triple that to 15*l multiplications. The restriction of p = 2^l - 1 and psaudorandom secret sharing, reduces the work of finding random bitwise shared values in the field to 1 l multiplications, if this restriction is lifted we are looking at 4 l for each (of the two) random bitwise shared values. So that means 11 l for the restricted case and 33 l for the general case. The number of rounds will also increase to 6 if you do not use psaudorandom values. The number of rounds can grow to 8 for the comparison with no restrictions, if you do not allow for preprocessing of the final multiplications. If I remember correctly the code deviates from the constant round solution in that for primes where the two highest order bits are '10' it tests separately for the first two bits. This increases the possible number of rounds, but it decreases the failure rate. Tord Tomas Toft wrote: Hi all Tord Ingolf Reistad wrote: As you are discussing implementing the algorithm from ICITS07, I have improved on that to get a very effective algorithm. For p = 2^l - 1 and using psaudorandom secret sharing. The comparison can be done in 5 rounds and 5l multiplications. The algorithm has never been published, but attached is a java implementation of the algorithm. (There might be an error in the faun in algorithm as that is not tested). As I said, the best, *published* algorithm I know is from ICITS07. :-) Btw, does the 5*l multiplications-solution allow arbitrary input from the field or only (l-1)-bit? If it's full-field then I *really* need to see it. Unfortunately I do not have a phyton implementation of it, as I am bad at programming in phyton, on the other hand I am working on a java implementation of MPC, which should be ready in a month. If anyone else want to try to implement it in phyton I will be more than happy to help. To understand the code please start with the function public Share comparisonRestricted(Share a, Share b) and please observe that many small functions on the top are just returning values instead of shares, this is for test purposes. I'll take a look at it and perhaps try a python port if time permits. 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] Choice of comparison protocol
Hello all,
As you are discussing implementing the algorithm from ICITS07, I have
improved on that to get a very effective algorithm. For p = 2^l - 1 and
using psaudorandom secret sharing. The comparison can be done in 5
rounds and 5l multiplications. The algorithm has never been published,
but attached is a java implementation of the algorithm. (There might be
an error in the faun in algorithm as that is not tested).
Unfortunately I do not have a phyton implementation of it, as I am bad
at programming in phyton, on the other hand I am working on a java
implementation of MPC, which should be ready in a month. If anyone else
want to try to implement it in phyton I will be more than happy to help.
To understand the code please start with the function
public Share comparisonRestricted(Share a, Share b)
and please observe that many small functions on the top are just
returning values instead of shares, this is for test purposes.
Tord
Martin Geisler wrote:
[EMAIL PROTECTED] writes:
I talked with Rune Thorbek yesterday, and he asked why we have not
implemented your comparison protocol from your PhD thesis:
http://www.daimi.au.dk/~tomas/publications/dissertation.pdf
Is there any good reason why we haven't done that? Is the constants
much worse than the ones implemented?
Short answer: Yes.
Longer Answer: You need to do lots of tricks to go to
constant-rounds. The logarithmic solutions do not give (much) worse
round complexity, but require notably fewer multiplications.
Okay.
The best one published that I know of is Tord's and mine from
ICITS07. This is reasonable to implement (complexity-wise), but
trust me, you don't want to :-)
Hmm... Rune says that I should consider this a challange... :-)
I wont really have time before I return from Switzerland in September
(I leave in a week), but can I find the article online? I found the
conference webpage, but it does not link to your article, and neither
does your own publication list.
/*
* Testclass.java
*
* Created on 11. juni 2007, 01:30
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package multiparty;
/**
*
* @author item
*/
import java.math.BigInteger;
import java.util.Stack;
import multiparty.Field;
//import org.lsmp.djep.groupJep.groups.Zn;
public class Testclass {
//private class Share extends multiparty.Field {
//public Share(long l) {super(l);}
//public Share(BigInteger v) {super(v);}
//}
/** Creates a new instance of Testclass */
public Testclass() {
}
static BigInteger BIG2 = BigInteger.valueOf(2);
static java.util.Random random = new java.util.Random();
public Share generateRandom() {
return new Share(Field.random());
}
public Share generateBit() {
// Not propper way to do it.
if (random == null)
random = new java.util.Random();
boolean r = random.nextBoolean();
if (true == r)
return new Share(BigInteger.ONE);
else
return new Share(BigInteger.ZERO);
}
public Field[] splitP() {
// Splits the fieldsize p into bits
// to reconstruct the value compute bits[i]*2^i
return splitNum(Field.getBaseField());
}
public Field[] splitNum(BigInteger a) {
Field [] bits = new Field[Field.getBaseField().bitLength()];
for (int i=0; i-1; i--)
}
public int initialBitsSetInP() {
BigInteger a = Field.getBaseField();
int numBits = 0;
for (int i=a.bitLength()-1; i>-1; i--) {
if (a.testBit(i)) {
numBits = numBits + 1;
} else
break;
}
return numBits;
}
public BigInteger convertFromBitsToValueB(Share[] a) {
BigInteger temp = BigInteger.ZERO;
BigInteger exp;
for (int i=0; i-1; i--) {
// System.out.print(Rand[i]);
//}
//System.out.println("");
//for (int i=Psplit.length-1; i>-1; i--) {
//BigInteger tt2 = BIG2.pow(i);
//tt2 = tt2.multiply(Rand[i].getvalue());
//tt = tt.add(tt2);
//System.out.println("TT2 is " +tt2+" TT is "+tt);
//}
//System.out.println("TT is " + tt);
// Testing if Rand > P, there is no need to test for any bit where
// p_i = 1. p_i xor r_i is either r_i if p_i=0 or 1-r_i if p_i=1.
// There is a separate test for the last bit.
// Testing if (1-r_i+p_i) + \sum (r_j xor p_j)
// For last bit testing (p_0-r_0) + \sum (r_j xor p_j)
for (int i=Psplit.length-1; i>-1; i--) {
// Only check if p_i=0 or if last bit
if (Psplit[i].compareToZERO() || (0 == i)) {
Share temp = new Share(Bi
Re: [viff-devel] RFC: multiple program counters
Hello, First off I do not really understand what you mean when you say that you send more than once in a single method, so could you give some more details. But here is my input to the counter situation and some more broad thoughts about the program: I try to imagine that one day VIFF will not be a separate program, but only a library/subroutine in some larger program. This larger program might want to do multiple MPC computations at the same time and might have different algorithms that it can handle, these algorithms are dynamically allocated. The counter system will have to handle all these cases. So let me draw a larger picture: You start with a set of MPC algorithms/protocols, e.g. algorithms a', b' and c'. Now for each algorithm you have to define a set of roles. E.g. for algorithm a', you have roles 1, 2, 3 and 4. Each role has a predefined set of information it uses as input to the MPC protocol and a predefined set of information it gets out of the MPC protocol. You also have a set of players A, B, C, D, E, etc. Lets make this more concrete, if algorithm a' is a location finder. Then roles 1,2,3 give as input to the MPC protocol their current position. Role 1 also gives the distance 1-2 and 1-3 as input to the MPC protocol. Role 2 also gives the distance 2-3 as input to the MPC protocol. Role 4 on the other hand gives the distance 1-4, 2-4 and 3-4. Role 4 is the only one to receive any output from the MPC protocol. It receives as output its current position. So role 1 has 3 inputs, role 2 has 2 inputs, role 3 has 1 input, role 4 has 3 inputs and 1 output. Now lets also assume that algorithm b' is some other algorithm with 3 players, where each role 1,2 and 3 has one input and gets one output. Finally lets say that player A can if anybody asks him participate in algorithm a' as role 1, 2 or 3 (not 4), and algorithm b' as role 1 or 3. Then A should be able to handle simultaneously the following: Algorithm a' in role 1, with B as role 2, C as role 3, E as role 4. Algorithm b' in role 3, with C as role 1, B as role 2. Algorithm b' in role 1, with E as role 1, F as role 2. and so on... Now the nice thing about this set-up is that each instance of the triplet algorithm, role and current set of players can be hashed into an unique value. The algorithms and roles can be pre-approved and checked for information leaks by a human. The algorithms and roles can the by dynamically linked to players at runtime. Each instance of the triplet can be run as a separate thread, and the program counter in each tread can operate independent of the other threads. As long as the unique identifier is transmitted to the other players they should also be on the same page as to which algorithm and which instance of the algorithm the messages should be transmitted to. Just my idea as to a multi-threaded, dynamical VIFF system. Tord Martin Geisler wrote: > Hello everybody, > > Mikkel has pointed out that the current system with a single program > counter is not enough if we need to send more than once in a single > method. > > We think the best solution is to introduce multiple program counters, > so that each player maintains a counter for each other player in the > network. > > The idea is that since the players might do different amount of > sending and receiving, one global program counter is not enough. > > > More concretely, we imagine that it will be enough if increment_pc > increments all program counters by one, and sendData and _expect_data > only increment the program counter associated with the sending or > receiving player. > > > We send this out here since we would love to hear other ideas! > ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Asymmetric protocols
Martin Geisler wrote: > [EMAIL PROTECTED] writes: > > >> Are there really other problems than sharing (and opening a shared >> value towards only one party)? > > I don't think so. All other operations (addition, multiplication, > comparison, etc...) are done on variables which represent values in > the ideal functionality implemented by VIFF. So they are not tied to > any particular player and so I think we can limit these asymmetric > operations to sharing and opening. > I agree only sharing and opening will be asymmetric, and there are many cases in which an opening will be asymmetric. To make it really confusing there might be cases in which the opening might be dependent upon some secret shared variable. E.g. lets say you are in a hospital and that the nurses (doctors and administrators also) would have Pda's with location information. Now the nurses do not want their location to be tracked, so there is no central location server. Now one nurse puts out a request for help, and the algorithm has to find the closest nurse that is not busy to give the request to. The calculations to find the closest nurse is done using MPC, but then the call for request should be revealed only to the one fitting the description. The others should just get a dummy request (logged or discarded by the computer). In practice the nurse who's assistant was needed would hear a ring tone, and the pda would display that help was needed in room XXX. For all the other nurses (doctors and administrators), their pda would only log that an event where location information was needed was processed by the MPC module. They would not get any information about what kind of request it was, or anything else. In this example who the receiver of the message is, is not known until we have determined who is the closest. As a side note: I am working on a new comparison protocol, I have some problems with it so it might not work, but if it does then I need to compute both in some field Z_p and Z_q for different primes p and q. Can VIFF handle that or is it hard wired to only work in one field? ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] An improved comparison
I will need some help with the implementation. I will write some detailed psaudocode and you can help me transform it into Pyton. Two questions before I start: What is the function (and where is it located) for generating a random bitwise secret shared value? What is the function (and where is it located) for generating random values in the field? Tord Martin Geisler wrote: > Tord Ingolf Reistad <[EMAIL PROTECTED]> writes: > > Hi Tord! > >> I have an idea that has not been written down and implemented so I >> might as well write it to viff-devel. As you are trying to do a >> timing trial. [...] > > I have skimmed through the protocol, and it looks no worse > implementation-wise than what we already have... so I would of course > like to implement it at some point! Unless you beat me to it :-) > ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] An improved comparison
Hello, I have an idea that has not been written down and implemented so I might as well write it to viff-devel. As you are trying to do a timing trial. It is constant round protocol for MPC comparison over Z_p, where p is an l-bit prime. Using the assumptions that p is a Mersenne prime, and psaudo-random secret sharing the protocol uses 4,5 l multiplications. The comparison is [a] < [b], where [a] means that the value a is shared. The protocol builds on my earlier protocols, but the new thing is that I look at 2 and 2 bits at a time. What the protocol does is to start with the familiar trick of turning a comparison between two unknown values into a comparison between a known value and a bitwise shared random value. Based on the known value and the bitwise shared random value we look at 2 and 2 bits and compute a second value z, this value z has the last bit set to 0 or 1 based on whether the known value or the bitwise shared random value is bigger. We then use a highly effective method to extract the last bit of z as we can control which interval it is in. Assumtions: [a], [b] < p/4 (Means we are comparing [b]-[a] < p/2 instead) Psaudo-random secret sharing - makes the cost of generating random numbers negligible Mersenne primes - the cost of generating a random bitwise shared secret is only l + 2 multiplications when psaudo-random secret sharing is used Protocol: For comparison of [a] < [b] or [b] - [a] < p/2 1. Create two bitwise shared secret values [r]_B and [s]_B 2. Reveal c, where [c] = ([b] - [a]) + [r]_B The comparison now becomes a comparison between [r]_B and c, the individual bits of [r]_B and c are denoted [r_i] and c_i. 3. Compute [x] = \sum_i (1-[r_i]+c_i + \prod 2^(c_i xor [r_i])) but do it on 2 and 2-bit blocks at a time. 1-[r_i]+c_i becomes a table which is 1 if c_i <= r_i over the 2 bits, otherwise it is 0 e.g. if c_1 = 0, c_1 = 0, then the table should return 1 only if [r_0] and [r_1] is 0, in other words use 1 - ([r_0] + [r_1] - 2[r_0][r_1]). \prod 2^(c_i xor [r_i]) also becomes a table for (c_i xor [r_i]) where we look at 2 bits at a time. The table is 0 iff c_i = r_i for both bits. If c_i is not equal to r_i for both bits then the value should be 1. The nice thing about using 2 bits at a time is that we only need to compute [r_i]*[r_(i-1)] thereby using l/2 multiplications extra, but what we save is that the faun-in multiplication needed to compute the product now only becomes 2,5 l multiplications instead of 5 l. 4. For the final set and reveal x', where [x'] = [x] + 2^(l-1) - [s] and use my method for finding the lowest bit with only a constant number of multiplications. The trick is to use the highest bits of [s]. Since 2^(l-1) <= [x] < 2^(l-1) + 2^(l/2 + log(l)). Then [s] < [x] if the highest bit is not set, otherwise if the highest bit is set then [s] - 2^(l-1) < [x]. Therefore the lowest bit of [x] is equal to x'_0 xor [s_0] if the highest bit is not set. Otherwise it is equal to [s_0] xor (x' - 2^(l-1))_0, where (x' - 2^(l-1))_0 means the lowest bit of x' - 2^(l-1) when we are working over the field Z_p. Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] International test runs
Hello Martin I can get you access to a computer lab with about 10 computers that were used for a computer lab in wireless security. A re-install (as the students have changed the passwords) from image will give you a clean machine with a 2-3 months old Ubutu installation with access root if that is needed. I will soon post another email to the list with sketches for an improved comparison. It is basically the same as previous work only looking at 2 bits at a time to speed things up. Martin Geisler wrote: > Tord Ingolf Reistad <[EMAIL PROTECTED]> writes: > > Hi Tord > >> I have one personal computer that I can run VIFF on here in Norway. >> >> I might try to get you access to a computer lab if you want, so you >> can run everything from Denmark and not worry about contacting me. All >> the students are studding for their exams so the labs are empty some >> time in January. > > That would be a great solution, so that I don't have to coordinate with > you to do my tests. An account with SSH access, 50 MiB of disk, and a > standard install of Python and GCC is all I need. > > But if you have the time, we could also schedule a benchmarking session. > It think it could be done in an hour -- less if you have already > installed Twisted and GMPY. But let me know if you're to busy right now. > >> I am only looking at the code and not understanding too much so I have >> still not tried to get VIFF working in practice. > > Okay, let me know if I can help! > >> When I talked to someone (more linux geek than me) about running MPC >> with computers far away, he suggested simulating the whole thing by >> introducing controlled delays in the network layer. But I like your >> idea better. > > For benchmarking I think it is best to run the programs on the real > Internet. But for testing I would love to have such a sub-system. It > would also make it possible to repeat and automate the tests in a > reliable way. > > I have a similar item on the TODO list already: > > * Create unit tests which randomizes network delay > The current unit test with LoopbackRuntime are strictly sequential and > does not capture the random delays possible with real network traffic. > > This is not so much to test the performance, but instead the robustness > of the network setup. Right now you have to start the players in order > 3-2-1 and if you kill one of them the port is probably left in a > TIME_WAIT state for 60 seconds. > > > > > > ___ > 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] International test runs
I have one personal computer that I can run VIFF on here in Norway. I might try to get you access to a computer lab if you want, so you can run everything from Denmark and not worry about contacting me. All the students are studding for their exams so the labs are empty some time in January. I am only looking at the code and not understanding too much so I have still not tried to get VIFF working in practice. When I talked to someone (more linux geek than me) about running MPC with computers far away, he suggested simulating the whole thing by introducing controlled delays in the network layer. But I like your idea better. Martin Geisler wrote: > Martin Geisler <[EMAIL PROTECTED]> writes: > >> I would like to try VIFF over greater network distances, and this is >> where you guys come into the picture. Please tell me which machines >> you have access to in exotic places. So far I know of these >> persons/places: >> >> Tomas: Holland >> Tord: Norway > > That reminds me -- Tomas, Tord, have you managed to get VIFF working? > > I just got it running on DreamHost and will post some benchmark results > in a moment. > > > > > > ___ > 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
