Re: [viff-devel] VIFF needs at least 3 players always?

[Thomas P Jakobsen]

> There is also an Orlandi runtime and a BeDOZa runtime (under
> development). They work for 2 parties and guarantee security against
> active adversaries (paillier.py is only for passive security).
>
> Claudio

The current implementation of the Orlandi runtime found in orlandi.py
unfortunately depends on a 3rd party party package for elliptic curve
cryptography that is not open source. So unless you have a special
agreement with the owners of that package
(http://www.cryptomathic.com) or can find something similar, you won't
be able to use it.

The BeDOZa runtime is completely open-source, but as Claudio mentions,
it is not fully implemented yet.

So for now, the only 2-party runtime is the passively secure paillier
runtime in paillier.py.

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] VIFF needs at least 3 players always?

[Claudio Orlandi]

There is also an Orlandi runtime and a BeDOZa runtime (under
development). They work for 2 parties and guarantee security against
active adversaries (paillier.py is only for passive security).

Claudio

2010/10/7 Mikkel Krøigård :
> Citat af Kyung-Wook Hwang :
>
>> Hello,
>>
>> This is Kyung Hwang from Columbia University again. I have another
>> question.
>>
>> Does Viff always need at least 3 participants? It seems to me it does.
>
> That depends on the runtime you use. If you are using the default passive
> security runtime, this is based on Shamir secret-sharing. Therefore there
> must be at least 3 parties, and the threshold will always be < n/2.
>
> There is in fact also a two-party runtime based on the Paillier
> cryptosystem. You can check it out if you want, it's in paillier.py.
>
> But basically you have to select a runtime that gives you what you want. If
> you want 2-party MPC, you can't use the Shamir sharing based runtime.
>
>>
>> I modified "beginner.py" for two players because that file was
>> simplest to modify, but when I ran the two players, I got the
>> following errors:
>>
>> kwhw...@kwhwang-sim1:~/viff-1.0/apps$ python beginner2.py player-2.ini
>> 20 --no-ssl
>> Seeding random generator with random seed 3781
>> /home/kwhwang/opt/lib/python/viff/prss.py:43: DeprecationWarning: the
>> sha module is deprecated; use the hashlib module instead
>>  import sha
>> I am player 2 and will input 20
>> Not using SSL
>> Listening on port 9002
>>  Starting reactor ###
>> 
>> Program started
>>
>> Error: [Failure instance: Traceback: : 3
>> /home/kwhwang/opt/lib/python/viff/runtime.py:317:stringReceived
>> /home/kwhwang/opt/lib/python/viff/runtime.py:456:identify_peer
>> /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:280:callback
>>
>> /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:354:_startRunCallbacks
>> ---  ---
>>
>> /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:371:_runCallbacks
>> beginner2.py:69:protocol
>> /home/kwhwang/opt/lib/python/viff/passive.py:493:input
>> /home/kwhwang/opt/lib/python/viff/passive.py:550:shamir_share
>> /home/kwhwang/opt/lib/python/viff/runtime.py:785:_expect_share
>> /home/kwhwang/opt/lib/python/viff/runtime.py:749:_expect_data
>> /home/kwhwang/opt/lib/python/viff/runtime.py:754:_expect_data_with_pc
>>
>
> As you can see, it's using shamir_share. Shamir sharing requires at least 3
> players.
>
>> I also modified equality.py for two players to see if it works for
>> only two players because that file actually compared only two players'
>> inputs but not the third player's so that file essentially needs two
>> players. But it gaves errors too with two players.
>>
>> I think Viff only works with at least three players. Am I correct?
>
> Same as above :)
>
> Regards,
> Mikkel Krøigård
> ___
> 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] VIFF needs at least 3 players always?

[Mikkel Krøigård]

Citat af Kyung-Wook Hwang :


Hello,

This is Kyung Hwang from Columbia University again. I have another question.

Does Viff always need at least 3 participants? It seems to me it does.


That depends on the runtime you use. If you are using the default  
passive security runtime, this is based on Shamir secret-sharing.  
Therefore there must be at least 3 parties, and the threshold will  
always be < n/2.


There is in fact also a two-party runtime based on the Paillier  
cryptosystem. You can check it out if you want, it's in paillier.py.


But basically you have to select a runtime that gives you what you  
want. If you want 2-party MPC, you can't use the Shamir sharing based  
runtime.




I modified "beginner.py" for two players because that file was
simplest to modify, but when I ran the two players, I got the
following errors:

kwhw...@kwhwang-sim1:~/viff-1.0/apps$ python beginner2.py player-2.ini
20 --no-ssl
Seeding random generator with random seed 3781
/home/kwhwang/opt/lib/python/viff/prss.py:43: DeprecationWarning: the
sha module is deprecated; use the hashlib module instead
  import sha
I am player 2 and will input 20
Not using SSL
Listening on port 9002
 Starting reactor ###

Program started

Error: [Failure instance: Traceback: : 3
/home/kwhwang/opt/lib/python/viff/runtime.py:317:stringReceived
/home/kwhwang/opt/lib/python/viff/runtime.py:456:identify_peer
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:280:callback
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:354:_startRunCallbacks
---  ---
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:371:_runCallbacks
beginner2.py:69:protocol
/home/kwhwang/opt/lib/python/viff/passive.py:493:input
/home/kwhwang/opt/lib/python/viff/passive.py:550:shamir_share
/home/kwhwang/opt/lib/python/viff/runtime.py:785:_expect_share
/home/kwhwang/opt/lib/python/viff/runtime.py:749:_expect_data
/home/kwhwang/opt/lib/python/viff/runtime.py:754:_expect_data_with_pc



As you can see, it's using shamir_share. Shamir sharing requires at  
least 3 players.



I also modified equality.py for two players to see if it works for
only two players because that file actually compared only two players'
inputs but not the third player's so that file essentially needs two
players. But it gaves errors too with two players.

I think Viff only works with at least three players. Am I correct?


Same as above :)

Regards,
Mikkel Krøigård
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF needs at least 3 players always?

[Kyung-Wook Hwang]

Hello,

This is Kyung Hwang from Columbia University again. I have another question.

Does Viff always need at least 3 participants? It seems to me it does.

I modified "beginner.py" for two players because that file was
simplest to modify, but when I ran the two players, I got the
following errors:

kwhw...@kwhwang-sim1:~/viff-1.0/apps$ python beginner2.py player-2.ini
20 --no-ssl
Seeding random generator with random seed 3781
/home/kwhwang/opt/lib/python/viff/prss.py:43: DeprecationWarning: the
sha module is deprecated; use the hashlib module instead
  import sha
I am player 2 and will input 20
Not using SSL
Listening on port 9002
 Starting reactor ###

Program started

Error: [Failure instance: Traceback: : 3
/home/kwhwang/opt/lib/python/viff/runtime.py:317:stringReceived
/home/kwhwang/opt/lib/python/viff/runtime.py:456:identify_peer
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:280:callback
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:354:_startRunCallbacks
---  ---
/usr/lib/python2.6/dist-packages/twisted/internet/defer.py:371:_runCallbacks
beginner2.py:69:protocol
/home/kwhwang/opt/lib/python/viff/passive.py:493:input
/home/kwhwang/opt/lib/python/viff/passive.py:550:shamir_share
/home/kwhwang/opt/lib/python/viff/runtime.py:785:_expect_share
/home/kwhwang/opt/lib/python/viff/runtime.py:749:_expect_data
/home/kwhwang/opt/lib/python/viff/runtime.py:754:_expect_data_with_pc


I also modified equality.py for two players to see if it works for
only two players because that file actually compared only two players'
inputs but not the third player's so that file essentially needs two
players. But it gaves errors too with two players.

I think Viff only works with at least three players. Am I correct?

Thank you.

Kyung
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and random numbers

[Mikkel Krøigård]

Of course it is also worth mentioning that this is a very quick and  
dirty implementation of BBS. I am sure you can save a lot of time by  
implementing this in a clever way.


No tricks were used except for gmpy.

Citat af Mikkel Krøigård :

By the way, I just implemented the Blum Blum Shub generator in  
Python just to see how fast it would be compared to urandom. Note  
here that urandom is significantly slower than the default Python  
PRNG, but we can't use the normal one anyway.


The BBS generator must square modulo n (product of two Blum primes)  
and then extract log log n lower-order bits from that. I picked a  
2048 bit n and extracted 10 bits per squaring.


I then generated 10 random bits a million times using urandom and BBS:

urandom: 30 seconds
BBS: 80 seconds

Not THAT bad really. This is the ideal situation for BBS though.

However, if you use for example random() instead (random float in  
[0;1) ), then you must either pool bits (which takes time) or throw  
away bits per call, because you need about 53 bits per number (I'm  
assuming they ARE double-precision, not a Python geek :) ). There I  
got:


urandom: 29 seconds
BBS: 435 seconds (not surprising, since 80*6 = 420)

This is of course horrible.

PS: There are probably better crypto-secure PRNGS out there, I just  
picked BBS because I know that one quite well.


Also, the CryptGenRandom generator in Windows is claimed to have  
been patched and fixed for Windows XP and Vista (presumably Windows  
7 too). However, it's probably not good practice to take their word  
for it :)


Citat af Thomas P Jakobsen :


I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

Regards,
Thomas




___
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] VIFF and random numbers

[Mikkel Krøigård]

By the way, I just implemented the Blum Blum Shub generator in Python  
just to see how fast it would be compared to urandom. Note here that  
urandom is significantly slower than the default Python PRNG, but we  
can't use the normal one anyway.


The BBS generator must square modulo n (product of two Blum primes)  
and then extract log log n lower-order bits from that. I picked a 2048  
bit n and extracted 10 bits per squaring.


I then generated 10 random bits a million times using urandom and BBS:

urandom: 30 seconds
BBS: 80 seconds

Not THAT bad really. This is the ideal situation for BBS though.

However, if you use for example random() instead (random float in  
[0;1) ), then you must either pool bits (which takes time) or throw  
away bits per call, because you need about 53 bits per number (I'm  
assuming they ARE double-precision, not a Python geek :) ). There I got:


urandom: 29 seconds
BBS: 435 seconds (not surprising, since 80*6 = 420)

This is of course horrible.

PS: There are probably better crypto-secure PRNGS out there, I just  
picked BBS because I know that one quite well.


Also, the CryptGenRandom generator in Windows is claimed to have been  
patched and fixed for Windows XP and Vista (presumably Windows 7 too).  
However, it's probably not good practice to take their word for it :)


Citat af Thomas P Jakobsen :


I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

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] VIFF and random numbers

[Thomas P Jakobsen]

I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

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] VIFF and random numbers

[Martin Geisler]

Mikkel Krøigård  writes:

Hi everybody

> Indeed it should satisfy those properties. Say if you Shamir share
> something, the adversary might get t shares in order. If it can guess
> the next bit with non-negligible advantage, this will completely break
> our claim that the adversary has no information on the secret.
>
> Luckily it should not be hard to replace. I think we knew about this
> earlier but just forgot, actually.

No, we did not forget it -- it was designed from the start with an aim
towards making tests reproducible. This is why VIFF announces the random
seed when it starts and why the seed is chosen as a small integer.

-- 
Martin Geisler

Mercurial links: http://mercurial.ch/


pgpBdiC07ULeT.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] VIFF and random numbers

[Martin Geisler]

Marcel Keller  writes:

> Thomas P Jakobsen wrote:
>
>> If not, I guess we'll have to use some external package (openssl?) or
>> implement our own algorithm.
>
> viff.util.rand is used to make all randomness replayable, which
> already helped me to find bugs triggered by certain randomness. I
> would like to have this feature also in the future, therefore I would
> vote against a random number generator using noise not only to
> generate a seed.

Right, but note that the seed is not enough to ensure deterministic
output because of jitter in the network.

> If the environment variable VIFF_SEED is set to the empty string, VIFF
> already uses /dev/urandom by using random.SystemRandom for random
> number generation. This possibility is not documented however.

It's documented in the final paragraph here:

  http://viff.dk/doc/util.html#viff.util.rand

I will of course agree that it could be made more explicit :-)

-- 
Martin Geisler

Mercurial links: http://mercurial.ch/


pgpEQ0pxZDe3R.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] VIFF and random numbers

[Marcel Keller]

Thomas P Jakobsen wrote:

The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough.


There is a paper describing various flaws:
http://www.pinkas.net/PAPERS/gpr06.pdf


If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.


viff.util.rand is used to make all randomness replayable, which already
helped me to find bugs triggered by certain randomness. I would like to
have this feature also in the future, therefore I would vote against a
random number generator using noise not only to generate a seed.

If the environment variable VIFF_SEED is set to the empty string, VIFF
already uses /dev/urandom by using random.SystemRandom for random number
generation. This possibility is not documented however.

Best regards,
Marcel



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
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 mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and random numbers

[Mikkel Krøigård]

I had not seen the later replies before answering. My apologies.

The way I've always understood urandom is exactly that. It's  
"probably" unpredictable but there's no actual proof of this, like  
there would be if you used for example Blum Blum Shub.


I'm sure there are multiple implementations of cryptographically  
secure PRNGs floating around. I think I even have one in Java. I  
suspect they are much slower than urandom though.


Citat af Thomas P Jakobsen :


The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough. If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.

Regards,
Thomas



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
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 mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and random numbers

[Mikkel Krøigård]

Indeed it should satisfy those properties. Say if you Shamir share  
something, the adversary might get t shares in order. If it can guess  
the next bit with non-negligible advantage, this will completely break  
our claim that the adversary has no information on the secret.


Luckily it should not be hard to replace. I think we knew about this  
earlier but just forgot, actually.


By the way, I am not sure we use any random numbers that should NOT  
secure in this way.


Citat af Thomas P Jakobsen :


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
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] VIFF and random numbers

[Thomas P Jakobsen]

The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough. If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.

Regards,
Thomas



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:
> It is not good to use the wrong kind of PRG, it should
> be fixed as soon as possible. But do we know that
> os.urandom will be OK on any platform, or is this
> OS -dependent at the end of the day?
>
> - Ivan
>
> On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:
>
>> VIFF itself as well as most protocols implemented in VIFF uses the
>> viff.util package for random number generation. This package in turn
>> uses the random package in the Python standard library. This means
>> that random numbers are generated using a Mersenne twister.
>>
>> As far as I can see, this is a problem, since Mersenne twister PRNGs
>> are generally not suited for cryptographic usage. E.g. it is not known
>> to pass the "next-bit test" and withstand the "state compromise
>> extensions", see
>> http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.
>>
>> One solution would be to use the os.urandom() function instead. This
>> has specifically been designed to produce cryptographically secure
>> random numbers.
>>
>> (We should probably keep the old random generator, too. It is probably
>> faster and not all random numbers used in VIFF and VIFF programs need
>> to be cryptographically secure.)
>>
>>
>> Let me know what you think about this.
>>
>> Kind regards,
>> Thomas
>> ___
>> 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] VIFF and random numbers

[Ivan Bjerre Damgård]

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that 
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:

> VIFF itself as well as most protocols implemented in VIFF uses the
> viff.util package for random number generation. This package in turn
> uses the random package in the Python standard library. This means
> that random numbers are generated using a Mersenne twister.
> 
> As far as I can see, this is a problem, since Mersenne twister PRNGs
> are generally not suited for cryptographic usage. E.g. it is not known
> to pass the "next-bit test" and withstand the "state compromise
> extensions", see
> http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.
> 
> One solution would be to use the os.urandom() function instead. This
> has specifically been designed to produce cryptographically secure
> random numbers.
> 
> (We should probably keep the old random generator, too. It is probably
> faster and not all random numbers used in VIFF and VIFF programs need
> to be cryptographically secure.)
> 
> 
> Let me know what you think about this.
> 
> Kind regards,
> Thomas
> ___
> 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] VIFF and random numbers

[Thomas P Jakobsen]

VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind 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] VIFF reactor

[Joel Pettersson]

Marcel Keller  cs.au.dk> writes:

> 
> Hi Joel,
> 
> > Is it still necessary to run `viff.reactor.install()` as described in
> >  in
> > order to utilize the VIFF reactor?
> > 
> >  - If so, would it be possible to "fix" that?
> 
> I don't see a good way to that, for the following reasons:
> - To change the default reactor properly, it would be necessary to 
> change the Twisted source code. That is not an elegant way.
> - The VIFF reactor could be installed in the runtime module. However, if 
> it would be done that way, viff.runtime would have to be imported before 
> importing the reactor, which is a possible source of errors. 
> Furthermore, that would prevent other reactors like the GtkReactor from 
> being used.
> 
> >  - If not, then the example apps would need to be updated accordingly.
> 
> As far as I can see, all example apps are updated in VIFF 1.0.
> 
> Best regards,
> Marcel
> 
> 


Hi Marcel,

I see. Thanks for your quick reply!

And yes, since it really is necessary to run `viff.reactor.install()` manually
before `from twisted.internet import reactor` you are absolutely right — all
example apps are up-to-date.

Best regards,
Joel Pettersson

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF reactor

[Martin Geisler]

Joel Pettersson  writes:

Hi everybody,

> Is it still necessary to run `viff.reactor.install()` as described in
>  in
> order to utilize the VIFF reactor?
>
>  - If so, would it be possible to "fix" that?
>  - If not, then the example apps would need to be updated accordingly.

I see Marcel answered this with lightning speed, cool! :-)

> I will, by the way, be available in #viff @ Freenode most of my time
> the next couple of days.

I'll like to add that it's very easy to get online:

  http://webchat.freenode.net/

-- 
Martin Geisler

aragost Trifork
Professional Mercurial support
http://aragost.com/mercurial/
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF reactor

[Joel Pettersson]

Hi,

Is it still necessary to run `viff.reactor.install()` as described in
 in
order to utilize the VIFF reactor?

 - If so, would it be possible to "fix" that?
 - If not, then the example apps would need to be updated accordingly.

I will, by the way, be available in #viff @ Freenode most of my time
the next couple of days.

Best regards,
Joel Pettersson
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF reactor

[Marcel Keller]

Hi Joel,


Is it still necessary to run `viff.reactor.install()` as described in
 in
order to utilize the VIFF reactor?

 - If so, would it be possible to "fix" that?


I don't see a good way to that, for the following reasons:
- To change the default reactor properly, it would be necessary to 
change the Twisted source code. That is not an elegant way.
- The VIFF reactor could be installed in the runtime module. However, if 
it would be done that way, viff.runtime would have to be imported before 
importing the reactor, which is a possible source of errors. 
Furthermore, that would prevent other reactors like the GtkReactor from 
being used.



 - If not, then the example apps would need to be updated accordingly.


As far as I can see, all example apps are updated in VIFF 1.0.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 1.0 released

[Martin Geisler]

Hi everybody!

On behalf of the VIFF Development Team, it is my pleasure to declare
that we have reached VIFF version 1.0. The current code is useful,
flexible and unlikely to change radically. Please download it here:

  Tar/GZ:  http://viff.dk/release/viff-1.0.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-1.0.tar.bz2
  Zip: http://viff.dk/release/viff-1.0.zip
  Exe: http://viff.dk/release/viff-1.0.win32.exe

Thanks to all contributors who have helped create this release!

The largest changes since 0.7.1 are summarized below:

Version 1.0, released on 2009-12-14
---

The central class named Runtime was renamed to PassiveRuntime. All
runtime classes now uses the common method names input and output for
providing data to and retrieving data from the computation. A
multiparty version of AES was added: it allows parties to encrypt a
Shamir secret shared message under a secret shared AES key to obtain a
secret shared ciphertext.

* Moved the crypto-related code from the viff.runtime.Runtime class to
  a new class called viff.passive.PassiveRuntime. This is a backwards
  incompatible change. Please update your import statements to import
  PassiveRuntime instead of Runtime.

* Introduced input method in PassiveRuntime and PaillierRuntime. This
  method should be used instead of shamir_share and share unless there
  is a particular reason to select a secret sharing strategy.

* Introduced output method in Runtime classes. This method should be
  used instead of the open method, which will go away in a future
  release.

* Renamed random seed environment variable from SEED to VIFF_SEED.

* Made viff.prss.PRF produce consistent output on both 32-bit and
  64-bit systems.

* Exponentiation of shares by square-and-multiply for public
  exponents. This means that if x is a Share, x**7 now works.

* Added multiparty AES encryption. A highly optimized version of AES
  has been added to viff.aes. It allows multiparty encryption of a
  secret shared message using a secret shared AES key.

* Introduced our own Twisted reactor. This increases throughput by
  sending data sooner, rather than later.

* Added new full-threshold actively secure runtime in viff.orlandi. It
  currently relies on a third-party proprietary library for computing
  commitments over elliptic curves, so it cannot be use with a plain
  VIFF installation.

* Issue 4: Replace the marshal module. The marshal module is not safe
  to use for malicious data, so we now use the struct module to parse
  a fixed length format instead.

* Issue 62: Proper error message when no SSL certificate present.

* Issue 75: Test without local computations. The new FakeFieldElement
  class has the interface of a FieldElement but does no computations.
  A new --fake flag for benchmark.py enables these elements.

-- 
Martin Geisler


pgpaGrlvAgi23.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] VIFF 1.0 this weekend

[Martin Geisler]

"Håvard Vegge"  writes:

> atl...@stud.ntnu.no wrote:
>> Siterer Martin Geisler :
>>
>>> Atle and Håvard: do you have your thesis' online somewhere? I would
>>> like to include links to them. I have your thesis' in PDF format
>>> already, so I would also be happy to host them on viff.dk if you
>>> prefer that?
>>
>> My thesis can be found at
>> http://daim.idi.ntnu.no/masteroppgave?id=4699, also feel free to
>> host it on the VIFF page :)
>
> And mine is here: http://daim.idi.ntnu.no/masteroppgave?id=4559
> Put it anywhere you like!

Thanks guys! I've added links to the page. I think it's best to link
back to your university so that the documents can be kept in their
canonical location.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgppsQHQt57cM.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] VIFF 1.0 this weekend

[Håvard Vegge]

And mine is here: http://daim.idi.ntnu.no/masteroppgave?id=4559
Put it anywhere you like!

håvard


atl...@stud.ntnu.no wrote:

Siterer Martin Geisler :


Hi everybody,

I would like to release what we currently have in VIFF as version 1.0
this weekend. The code has not evolved very much the last year, and
releasing version 1.0 now will fit nicely with the reports we're writing
for CACE and with my own dissertation :-)

As preparation for that, I've made a small document about the
applications where VIFF has been used:

  http://viff.dk/doc/applications.html

Atle and Håvard: do you have your thesis' online somewhere? I would like
to include links to them. I have your thesis' in PDF format already, so
I would also be happy to host them on viff.dk if you prefer that?

My thesis can be found at 
http://daim.idi.ntnu.no/masteroppgave?id=4699, also feel free to host 
it on the VIFF page :)



Everybody: if someone wants to describe the Nordic Sugar auction then
that would be super, otherwise I'll do it. Marcel has promissed to write
something about the distributed RSA. Finally, if you have been sitting
on a bugfix (small or large), then please put it in now :-)

--
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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] VIFF 1.0 this weekend

[atlema]

Siterer Martin Geisler :


Hi everybody,

I would like to release what we currently have in VIFF as version 1.0
this weekend. The code has not evolved very much the last year, and
releasing version 1.0 now will fit nicely with the reports we're writing
for CACE and with my own dissertation :-)

As preparation for that, I've made a small document about the
applications where VIFF has been used:

  http://viff.dk/doc/applications.html

Atle and Håvard: do you have your thesis' online somewhere? I would like
to include links to them. I have your thesis' in PDF format already, so
I would also be happy to host them on viff.dk if you prefer that?

My thesis can be found at  
http://daim.idi.ntnu.no/masteroppgave?id=4699, also feel free to host  
it on the VIFF page :)



Everybody: if someone wants to describe the Nordic Sugar auction then
that would be super, otherwise I'll do it. Marcel has promissed to write
something about the distributed RSA. Finally, if you have been sitting
on a bugfix (small or large), then please put it in now :-)

--
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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] VIFF 1.0 this weekend

[Martin Geisler]

Martin Geisler  writes:

> Everybody: if someone wants to describe the Nordic Sugar auction then
> that would be super, otherwise I'll do it. Marcel has promissed to
> write something about the distributed RSA.

Sorry, he has written a bit about distributed AES!

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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

[viff-devel] VIFF 1.0 this weekend

[Martin Geisler]

Hi everybody,

I would like to release what we currently have in VIFF as version 1.0
this weekend. The code has not evolved very much the last year, and
releasing version 1.0 now will fit nicely with the reports we're writing
for CACE and with my own dissertation :-)

As preparation for that, I've made a small document about the
applications where VIFF has been used:

  http://viff.dk/doc/applications.html

Atle and Håvard: do you have your thesis' online somewhere? I would like
to include links to them. I have your thesis' in PDF format already, so
I would also be happy to host them on viff.dk if you prefer that?

Everybody: if someone wants to describe the Nordic Sugar auction then
that would be super, otherwise I'll do it. Marcel has promissed to write
something about the distributed RSA. Finally, if you have been sitting
on a bugfix (small or large), then please put it in now :-)

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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] VIFF

[Martin Geisler]

Nigel Smart  writes:

Hi Nigel

> Just tried to install VIFF to have a play around.

Cool! :-)

> I followed the instructions at...
>
> http://viff.dk/doc/install.html#gnu-linux
>
>
> Issues:
>
> a) When typing...
>
>   python setup.py install --home=$HOME/opt
>
>   I get the directory
>
>   $HOME/opt/lib/python
>
>   created, but not
>
>  $HOME/opt/bin
>
>   There seems to be no error messages in the setup.py output. Has
>   setup.py run correctly?

Hmm, you're right -- it's a mistake in the install guide. We actually
don't have any binaries to install yet. So far we only have small
example application scripts in the apps/ folder.

I'll update the installation guide, thanks for the report! :-)

> b) I then go do viff/apps and type...
>
>python generate-config-files.py -n 3 -t 1 \
>localhost:9001 localhost:9002 localhost:9003
>
>Resulting in the error message
>
>   Traceback (most recent call last):
>   File "generate-config-files.py", line 57, in ?
> from viff.config import generate_configs
>   File "/home/projects/crypto/Linux/lib/python/viff/config.py", line 33, in ?
> from viff.prss import generate_subsets, PRF
>   File "/home/projects/crypto/Linux/lib/python/viff/prss.py", line 47, in ?
> from gmpy import numdigits
>   ImportError: No module named gmpy

Yes, you need to install GMPY:

  http://code.google.com/p/gmpy/

(or use a package, if you one is available in your package manager).

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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

[viff-devel] VIFF

[Nigel Smart]

Hi

Just tried to install VIFF to have a play around.

I followed the instructions at...

http://viff.dk/doc/install.html#gnu-linux


Issues:

a) When typing...

  python setup.py install --home=$HOME/opt

  I get the directory

  $HOME/opt/lib/python

  created, but not

 $HOME/opt/bin

  There seems to be no error messages in the setup.py output. Has
  setup.py run correctly?

b) I then go do viff/apps and type...

   python generate-config-files.py -n 3 -t 1 \
   localhost:9001 localhost:9002 localhost:9003

   Resulting in the error message

  Traceback (most recent call last):
  File "generate-config-files.py", line 57, in ?
from viff.config import generate_configs
  File "/home/projects/crypto/Linux/lib/python/viff/config.py", line 33, in ?
from viff.prss import generate_subsets, PRF
  File "/home/projects/crypto/Linux/lib/python/viff/prss.py", line 47, in ?
from gmpy import numdigits
  ImportError: No module named gmpy


Any ideas?

Cheers

Nigel
--
Prof. Nigel P. Smart   | Phone: +44 (0)117 954 5163
Computer Science Department,   | Fax:   +44 (0)117 954 5208
Woodland Road, | Email: ni...@cs.bris.ac.uk
University of Bristol, BS8 1UB, UK | URL:   http://www.cs.bris.ac.uk/~nigel/
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [viff-commits] viff: Generate_config_files:Added support NaCl implementation of...

[Janus Dam Nielsen]

Some good old-fashioned code review coming up... :-)

Great!


/rev/736ad1d97024
changeset: 1361:736ad1d97024
user:  Janus Dam Nielsen 
date:  Wed Oct 28 14:53:51 2009 +0100
summary:   Generate_config_files:Added support NaCl implementation  
of Paillier.


There's a space missing after the colon.

Ok.


diffstat:

apps/generate-config-files.py |  22 +++---
viff/paillierutil.py  |  20 +++-
2 files changed, 38 insertions(+), 4 deletions(-)

diffs (90 lines):

diff -r 3fe6e03541c1 -r 736ad1d97024 apps/generate-config-files.py
--- a/apps/generate-config-files.py Wed Oct 28 14:53:49 2009 +0100
+++ b/apps/generate-config-files.py Wed Oct 28 14:53:51 2009 +0100
@@ -55,7 +55,17 @@
from optparse import OptionParser

from viff.config import generate_configs
-from viff.paillierutil import ViffPaillier
+from viff.paillierutil import ViffPaillier, NaClPaillier
+
+try:
+import pypaillier
+except ImportError:
+pypaillier = None


Are we getting a module called 'pypaillier' alongside the old module
called 'paillier'? I don't like that name very much. Perhaps we should
make a module called nacl so that you could do

 try:
 from viff.nacl import paillier
 except ImportError:
 from viff import paillier

and then make the interface identical for the two modules.
Agree, this is a goal to be pursued soonish, but I would like Marc to  
make a distribution of his work that can be accessed somewhere on the  
internet.

I believe the interfaces are identical


Also, can we please have that code put into VIFF? I don't like it that
we're getting more and more "secret" code floating around :-)  
Especially

not when we make changes to VIFF to accomodate this secret code -- it
would be different if we had simple drop-in Python replacements for  
it.


(I know you've said that this code can be made public since it's  
part of

NaCL, so this is more for the record...)
The code will not be a part of VIFF, but a prerequisite like Zope  
interfaces or Twisted. I will issue warning on the mailling list when  
I submit the changeset that will require it.



+
+paillier_choices = ['viff']
+
+if pypaillier:
+paillier_choices += ['nacl']


The append method is better for that.

Ok.




+paillier = ViffPaillier(options.keysize)
+if "nacl" == options.paillier:
+paillier = NaClPaillier(options.keysize)


I think it's clearer if you write

 if options.paillier == "nacl":
 paillier = NaClPaillier(options.keysize)
 else:
 paillier = ViffPaillier(options.keysize)

I slightly disagree.
 if "nacl" == options.paillier:
 paillier = NaClPaillier(options.keysize)
 else:
 paillier = ViffPaillier(options.keysize)
Is more natural in the current case.



+try:
+import pypaillier
+except ImportError:
+pypaillier = None
+
+
class Paillier:

def __init__(self, keysize):
@@ -35,8 +41,20 @@

def generate_keys(self):
return paillier.generate_keys(self.keysize)
+
+class NaClPaillier:
+
+def __init__(self, keysize):
+self.keysize = keysize
+self.type = 'nacl'
+
+def generate_keys(self):
+return pypaillier.generate_keys(self.keysize)


def deserializer(paillier_type, str):
-return tuple(map(long, str))
+if paillier_type == "viff":
+return tuple(map(long, str))
+if paillier_type == "nacl":
+return str.dict()


I think that function would belong in the otherwise unnecessary  
classes

you define above?
Or even better: make a function in two different
modules like I suggest above.
This is a good question. I choose the current design because it leaves  
you with only one place you should change if you want to add another  
paillier implementation. I need to think some more before I comment  
further on this.




Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD.

T +45 42 22 93 56
E janus.niel...@alexandra.dk
W alexandra.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] [viff-commits] viff: Generate_config_files:Added support NaCl implementation of...

[Martin Geisler]

viff-devel@viff.dk writes:

Hi Janus,

Some good old-fashioned code review coming up... :-)

> /rev/736ad1d97024
> changeset: 1361:736ad1d97024
> user:  Janus Dam Nielsen 
> date:  Wed Oct 28 14:53:51 2009 +0100
> summary:   Generate_config_files:Added support NaCl implementation of 
> Paillier.

There's a space missing after the colon.

> diffstat:
>
>  apps/generate-config-files.py |  22 +++---
>  viff/paillierutil.py  |  20 +++-
>  2 files changed, 38 insertions(+), 4 deletions(-)
>
> diffs (90 lines):
>
> diff -r 3fe6e03541c1 -r 736ad1d97024 apps/generate-config-files.py
> --- a/apps/generate-config-files.py   Wed Oct 28 14:53:49 2009 +0100
> +++ b/apps/generate-config-files.py   Wed Oct 28 14:53:51 2009 +0100
> @@ -55,7 +55,17 @@
>  from optparse import OptionParser
>  
>  from viff.config import generate_configs
> -from viff.paillierutil import ViffPaillier
> +from viff.paillierutil import ViffPaillier, NaClPaillier
> +
> +try:
> +import pypaillier
> +except ImportError:
> +pypaillier = None

Are we getting a module called 'pypaillier' alongside the old module
called 'paillier'? I don't like that name very much. Perhaps we should
make a module called nacl so that you could do

  try:
  from viff.nacl import paillier
  except ImportError:
  from viff import paillier

and then make the interface identical for the two modules.

Also, can we please have that code put into VIFF? I don't like it that
we're getting more and more "secret" code floating around :-) Especially
not when we make changes to VIFF to accomodate this secret code -- it
would be different if we had simple drop-in Python replacements for it.

(I know you've said that this code can be made public since it's part of
NaCL, so this is more for the record...)

> +
> +paillier_choices = ['viff']
> +
> +if pypaillier:
> +paillier_choices += ['nacl']

The append method is better for that.

> +paillier = ViffPaillier(options.keysize)
> +if "nacl" == options.paillier:
> +paillier = NaClPaillier(options.keysize)

I think it's clearer if you write

  if options.paillier == "nacl":
  paillier = NaClPaillier(options.keysize)
  else:
  paillier = ViffPaillier(options.keysize)

> +try:
> +import pypaillier
> +except ImportError:
> +pypaillier = None
> +
> +
>  class Paillier:
>  
>  def __init__(self, keysize):
> @@ -35,8 +41,20 @@
>  
>  def generate_keys(self):
>  return paillier.generate_keys(self.keysize)
> +
> +class NaClPaillier:
> +
> +def __init__(self, keysize):
> +self.keysize = keysize
> +self.type = 'nacl'
> +
> +def generate_keys(self):
> +return pypaillier.generate_keys(self.keysize)
>  
>  
>  def deserializer(paillier_type, str):
> -return tuple(map(long, str))
> +if paillier_type == "viff":
> +return tuple(map(long, str))
> +if paillier_type == "nacl":
> +return str.dict()

I think that function would belong in the otherwise unnecessary classes
you define above? Or even better: make a function in two different
modules like I suggest above.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpgf17JAb0Xo.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] viff 0.7.1 question

[Martin Geisler]

Angel Redoble  writes:

Hi Angel

> I hope this question is not a bother to you.

No, not at all :-)

> I was trying to test viff-0.7.1, as I executed
> generate-config-files.py, I got the error ¨ImportError: No module
> named viff.config¨. Im not sure how to fix this problem.

The error indicates that you have not put VIFF into your PYTHONPATH. The
easiest way to solve this is to put

export PYTHONPATH=$HOME/src/viff

into your .bashrc (or similar shell startup file). Here I'm assuming
that you've downloaded VIFF and put it into ~/src/viff. This means that
you should have

  ~/src/viff:
COPYING
COPYING.LIB
NEWS
README
apps
doc
run.py
setup.py
twisted
viff

The important part is that one can find viff/config.py inside a
directory found in $PYTHONPATH.

> Im using ubuntu 9.04.

Excellent, then you should have it easy.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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] viff 0.7.1 question

[Sigurd Torkel Meldgaard]

> Hi,
>
> I hope this question is not a bother to you.

No, not at all

> I was trying to test viff-0.7.1, as I executed generate-config-files.py, I 
> got the error >¨ImportError: No module named viff.config¨. Im not sure how to 
> fix this problem.

Most likely viff is not yet on your PYTHONPATH

Please read: http://viff.dk/doc/install.html#installing-from-source
for instructions on how to get it there.

On Tue, Oct 20, 2009 at 2:27 PM, Angel Redoble  wrote:
>
> Im using ubuntu 9.04.
>
> Thanks a lot.
>
> Angel
> ___
> viff-devel mailing list (http://viff.dk/)
> viff-devel@viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>

Sigurd
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] viff 0.7.1 question

[Angel Redoble]

Hi,

I hope this question is not a bother to you. I was trying to test viff-0.7.1, 
as I executed generate-config-files.py, I got the error ¨ImportError: No module 
named viff.config¨. Im not sure how to fix this problem.

Im using ubuntu 9.04.

Thanks a lot.

Angel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff-devel Digest, Vol 17, Issue 12

[Sigurd Torkel Meldgaard]

> Hi! I'm experimenting with the RSA problem in VIFF, so i need to have
> 2 primes (p and q) plus d (the inverse) secret shared.

I Guess what you really want is the inverse operation modulo pq. What
I implemented is integer division (rounding down)

If you are allowed to reveal n=pq then the inverse of d can be
computed with a protocol like

[r] = random element
c = open(d[r])
k = c inverse mod n (if it exists, otherwise retry with new randomness)
return [r]k

Hope you can use that

Sigurd
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Martin Geisler]

Tord Ingolf Reistad  writes:

Hi Tord,

I'm sorry for having let your message wait, but I didn't know what
would be a good answer to it. I'll try to explain some of the VIFF
design and then you can tell me how that fits into your ideas.

> 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.

At a high-level VIFF works like this:

1. A single thread of execution is either sleeping in a select() call,
   waiting for network traffic, or busy doing a local computation.

2. When a select() call is interrupted due to incoming network traffic
   the data is is first unpacked. All messages in VIFF consist of
   three parts: a so-called program counter[1], an arbitrary data type
   label, and some arbitrary data:

 msg = (pc, data_type, data)

   One of exactly two things will happen:

   a) If a callback function has been associated with the program
  counter and data type, this function is called with the data.
  Concretely, this means that (pc, data_type) is used to lookup a
  Deferred in a dictionary called incoming_data, and the callback
  method is called on this Deferred.

   b) If no callback function is found, the data is stored in the
  incoming_data dictionary under the key (pc, data_type).

3. When a callback function is called it might be expecting some data
   from the network. It will query this data based on the program
   counter and data type label.  Again there are exactly two
   possibilities:

   a) If the (pc, data_type) entry in incoming_data is empty, a
  Deferred is inserted in the dictionary. This Deferred is also
  returned to the code that expected the data.

  This case ties in with 2a) above: when the data arrives at some
  later time, the Deferred returned here will be triggered.

   b) If data is found in the (pc, data_type) entry, this data is used
  to return a Deferred with its callback already called.

  We end up in this case when the data was received in 2b) above
  before it was expected.

   This is the fundamental symmetri in VIFF: you can send data and you
   can expect data, and it does not matter in which order these two
   events occur. The only requirement is agreement on the program
   counters and data type labels.

4. The program keeps alternating between sleeping and executing local
   code until the reactor.stop() is called from one of the callback
   functions.

   Executing the program like this ensures that all parts of the
   program can be advanced in a uniform and fine-grained way. So if a
   function has executed these three lines:

 b1 = x < y
 b2 = a * b
 b = b1 * b2

   it will have created two Deferreds, b1 and b2, which will be
   waiting on network traffic. When a relavant piece of data is
   received, b1 and b2 will be triggered and eventually we will
   trigger the third Deferred, b.

   This happens in "parallel" across the whole system, with no
   explicit scheduling needed.

[1]: http://viff.dk/doc/program-counters.html

> 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.

As described above, a VIFF program will buffer up incoming traffic
while it is busy executing callback functions.

Having a dedicated thread that will deal with incoming data wont help
much here if it also invoke the callbacks like in case 2a). The
problem is that the thread will tie itself up with executing the
callback functions...

So it could instead spawn a new thread to handle the callbacks for
this particular piece of data. I believe the performance of such a
stunt will be very poor, unless you use a system like Haskell or
Erlang which supports very low overhead micro-threads.

If the thread does not invoke the callbacks, then all that is achieved
is unpacking of data. The execution thread could just as well do that.

> 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).

Delaying a computation based on the available memory would indeed be a
very nice feature. I've had some discussions with Mikkel and Marcel
about how this might work in VIFF via recursive calls to the reactor's
doIteration method... but that is for another long email :-)

> 3)Have algorithms that destroy already used elements that are not
> needed any more. (This can be done by the tre

Re: [viff-devel] VIFF benchmarks

[Thomas P Jakobsen]

> I've put some changes to it here -- it's only style changes in order to
> make it more "pythonic" :-) Please pull from this repository:
>
>  http://bitbucket.org/mg/viffbench-mg/
>
> I have not really tested the changes, expect by running pyflakes on the
> source.

Thanks a lot. I'll take a look at it as soon as I get the time.

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] VIFF benchmarks

[Martin Geisler]

"Thomas Jakobsen"  writes:
Hi Thomas

> I've written a VIFF application that should make it easy to create,
> run and visualize benchmarks for VIFF protocols.

I've put some changes to it here -- it's only style changes in order to
make it more "pythonic" :-) Please pull from this repository:

  http://bitbucket.org/mg/viffbench-mg/

I have not really tested the changes, expect by running pyflakes on the
source. By the way, pyflakes informs me that:

  viffbench/examples/ComparisonToft05.py:68: undefined name 'start_time'
  viffbench/lib/enum.py:193: undefined name 'EnumValueCompareError'
  viffbench/test/test.py:52: undefined name 'Suite'

in addition to some warnings.

I hope you like the changes, and that they mostly work! :-)

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgps7KXCgLzkV.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] VIFF benchmarks

[Martin Geisler]

Thomas Jakobsen  writes:

> I've just converted the benchmark code to a stand-alone application
> and uploaded it to bitbucket.org.
>
> You can find it here:
>
> http://bitbucket.org/tpj/viffbench

Wow, this looks really great, especially the quick start guide on the
Wiki. I hope to try it out soon.

I can see that you've already announced it on PyPI, super! When you
have put up zip and tar files (you can upload them to either PyPI or
simply put them in the Bitbucket wiki), you could consider putting it
on Freasmeat too:

  http://freshmeat.net/add-project/

They require a proper release before they will accept software into
their catalog.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty 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] VIFF benchmarks

[Thomas Jakobsen]

I've just converted the benchmark code to a stand-alone application
and uploaded it to bitbucket.org.

You can find it here:

http://bitbucket.org/tpj/viffbench

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] VIFF and large scale programs -- is VIFF really asynchronous?

[Martin Geisler]

t.t...@cwi.nl writes:

> 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.

Yes! Unless you offload some heavy computation with deferToThread, then
everything is run in one thread.

> 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".

Yeah, that is exactly what we have to do. Twisted is built on the idea
that your code does small chunks of work, sends out some data and
arranges for a function to be called when the next piece of data is
ready. It is particularly important that the code does not hold on to
the CPU for too long -- this stops the reactor.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgp18kv7KvgfK.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] VIFF and large scale programs -- is VIFF really asynchronous?

[Martin Geisler]

Mikkel Krøigård  writes:

> However, the focus is on handling the memory issue.
>
> While you can save memory by splitting up the computation, I would
> much prefer it if you could write code like the stuff Tomas wrote
> without thinking about memory-saving tricks. Ideally, it should be
> completely straightforward and without tricks.

I agree. But it is tricky... consider a "good" program like this:

  x = a * b
  y = c * d

and a "bad" program like this:

  x = a * b
  y = x * c

In the first we *want* both multiplications to be scheduled, but in the
second case we would prefer to wait with the calculation of y until x is
here. One problem is that to "wait with the calculation of y" sort of
means that we want y to be a Deferred :-)

> We just discussed if the Twisted reactor could somehow get control
> before we are done scheduling. In the case below, we would like to
> start getting some of the older stuff done before piling on new
> computations, and if the reactor could just send and receive once in a
> while, then maybe that could happen.
>
> However, Twisted is apparently not the kind of scheduling system we
> would need for that. I guess my question for this list is if my
> understanding here is correct.

Definitely, Twisted doesn't do any scheduling.

> Martin told me that there may be a way to reduce the memory usage by
> minimizing the size of deferreds, and that this is already mentioned
> in the bug tracker.

Yes, I have been talking to the Twisted guys about this. Please see this
bug report and especially this comment:

  http://twistedmatrix.com/trac/ticket/3245#comment:13

I have also been adding support for tracking the memory usage. Simply
add --track-memory to any program using VIFF and it will sample the
memory every 0.1 seconds and print out a line when the values change.

By doing that I found that the multiplication benchmark uses an
additional *6 KiB* for *each* additional multiplication I ask it to do.
Here I'm talking about the peak memory usage of the process, so this
includes the Deferreds, their values, their pointers to each other, etc.

> However, add an extra zero to the number of iterations and we're back
> to square one.

True. But high-level software takes up memory. We have a very elegant
in-memory program structure, but it is wasteful with memory unless the
programmer takes special care not to start too much at the same time.

-- 
Martin Geisler


pgpwFKC4HaraU.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] VIFF and large scale programs -- is VIFF really asynchronous?

[Mikkel Krøigård]

Quoting Ivan Bjerre Damgård :


Folks,

I think your precious time is better spent on figuring out a brilliant
solution to handling memory issues with VIFF, than on discussions about what
"asynchronous" really means :-)

Well if you are calling it asynchronous, then it had better BE asynchronous :)

However, the focus is on handling the memory issue.

While you can save memory by splitting up the computation, I would  
much prefer it if you could write code like the stuff Tomas wrote  
without thinking about memory-saving tricks. Ideally, it should be  
completely straightforward and without tricks.


We just discussed if the Twisted reactor could somehow get control  
before we are done scheduling. In the case below, we would like to  
start getting some of the older stuff done before piling on new  
computations, and if the reactor could just send and receive once in a  
while, then maybe that could happen.


However, Twisted is apparently not the kind of scheduling system we  
would need for that. I guess my question for this list is if my  
understanding here is correct.


Martin told me that there may be a way to reduce the memory usage by  
minimizing the size of deferreds, and that this is already mentioned  
in the bug tracker. However, add an extra zero to the number of  
iterations and we're back to square one.



regards, Ivan

Quoting Marcel Keller :


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).


There's a pitfall here: What do you mean with "share"? At this point, the
shares are only scheduled to be sent, the real communication doesn't occur
until step 3. The FAQ of Twisted says so:
http://twistedmatrix.com/trac/wiki/FrequentlyAskedQuestions#WhydoesittakealongtimefordataIsendwithtransport.writetoarriveattheothersideoftheconnection
Since I discussed this issue last week with Martin, I also looked at the
source of Twisted 8.1.0 to confirm it.


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".


As Mikkel wrote, I had the same issues and I solved them by calling parts of
my code (one AES round at a time) as a callback of some trigger shares.
___
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 mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Ivan Bjerre Damgård]

Folks,

I think your precious time is better spent on figuring out a brilliant
solution to handling memory issues with VIFF, than on discussions about what
"asynchronous" really means :-)

regards, Ivan

Quoting Marcel Keller :


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).


There's a pitfall here: What do you mean with "share"? At this point, the
shares are only scheduled to be sent, the real communication doesn't occur
until step 3. The FAQ of Twisted says so:
http://twistedmatrix.com/trac/wiki/FrequentlyAskedQuestions#WhydoesittakealongtimefordataIsendwithtransport.writetoarriveattheothersideoftheconnection
Since I discussed this issue last week with Martin, I also looked at the
source of Twisted 8.1.0 to confirm it.


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".


As Mikkel wrote, I had the same issues and I solved them by calling parts of
my code (one AES round at a time) as a callback of some trigger shares.
___
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] VIFF and large scale programs -- is VIFF really asynchronous?

[Marcel Keller]

> 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).

There's a pitfall here: What do you mean with "share"? At this point, the 
shares are only scheduled to be sent, the real communication doesn't occur 
until step 3. The FAQ of Twisted says so: 
http://twistedmatrix.com/trac/wiki/FrequentlyAskedQuestions#WhydoesittakealongtimefordataIsendwithtransport.writetoarriveattheothersideoftheconnection
Since I discussed this issue last week with Martin, I also looked at the 
source of Twisted 8.1.0 to confirm it.

> 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".

As Mikkel wrote, I had the same issues and I solved them by calling parts of 
my code (one AES round at a time) as a callback of some trigger shares.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Tord Ingolf Reistad]

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

Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Mikkel Krøigård]

Quoting t.t...@cwi.nl:



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".
Yes, that is how it works. Martin tells me that putting in "stops" is  
indeed the way to handle it, and apparently Marcel has done this  
successfully.


However, I don't see how this makes VIFF less asynchronous. We are  
forcing it to synchronize to avoid some memory usage, but that in  
itself does not make it synchronous.



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.
Indeed. I suppose that is the cost of handling it with deferreds,  
although I can imagine that other ways of implementing it would also  
run into problems if you carefully scheduled enough multiplications  
that depend on each other.


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[T . Toft]

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

Re: [viff-devel] VIFF benchmarks

[Martin Geisler]

"Thomas Jakobsen"  writes:

Hi Thomas

I just had a look at it -- it looks very cool!

> I've written a VIFF application that should make it easy to create,
> run and visualize benchmarks for VIFF protocols.

I think it would be nice if this was an external application which uses
VIFF as a library. Maybe call it viffbench? Then make a structure like
this:

  README <- put the text of this email here :-)
  setup.py
  viffbench/ <- this folder holds the files currently in apps/benchmark

Put it in a repository and upload it to bitbucket and announce it on
PyPI (python setup.py register) -- voila, you've made a release :-)

> I've used the application to set up a few benchmarks and run it on our
> new benchmark servers. The autogenerated result can be seen on
> http://www.daimi.au.dk/~tpj/web. It shows two benchmarks for the tip
> revision. There's also a "history" graph showing execution time of the
> Toft05 comparison back in time. Each dot represents a mercurial
> commit. Luckily it gets faster and faster :-) I admit there's not much
> explanation to the graphs yet, but I hope it's enough to illustrate
> the use of the application.

I like it a lot -- we should put those graphs on viff.dk when you get a
cronjob setup on the smpcXX machines.

> If you are interested in the source and have access to the DAIMI file
> system, it is located at /users/tpj/viff-repos/viff-benchmark. I will
> later put it on viff.dk. If you have problems getting it to work, I'll
> like to hear about that, too.

Please consider putting the code somewhere public where we can better
collaborate on it. If you put it on bitbucket you would get a bug
tracker, a wiki and nice Mercurial hosting:

  http://bitbucket.org/

That would make for a quick and nice homepage for the project.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpwL2pqCAvpy.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] VIFF benchmarks

[Thomas Jakobsen]

> The autogenerated result can be seen on
> http://www.daimi.au.dk/~tpj/web.

Oops. On Gmane the period seems to become part of the link. So here's
a valid link without period:

http://www.daimi.au.dk/~tpj/web

Regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF benchmarks

[Thomas Jakobsen]

Hi VIFF'ers,

I've written a VIFF application that should make it easy to create,
run and visualize benchmarks for VIFF protocols.

As an illustrating example, all you have to do in order to benchmark
the Toft05 comparison:

1) Define the benchmark. This means implementing a subclass of
VIFFBenchmark that specifies the runtime class to be used as well as
what should be measured. Here we simply measure the time it takes to
compare two random shared integers using the Toft05 comparison
protocol.

class BenchmarkToft05(VIFFBenchmark):
def get_runtime_class(self):
return Toft05Runtime
def protocol(self, rt, attr):
Zp = GF(int(attr['modulus']))
a = rt.prss_share_random(Zp)
b = rt.prss_share_random(Zp)
c = gather_shares([a,b])
c.addCallback(self.start_timer)
d = (a <= b)
d.addCallback(self.stop_timer)
return d

2) Run the benchmark. This is done by setting up a benchmark suite
that has a connection to a database where it can store the results.
Multiple benchmarks with various parameters can then be added to the
suite before it is run.

d = Database([host="localhost", db="benchmark", user="benchamark",
passwd = "secret")
s = Suite(revision="ec70dc5ac213",
  database=d,
  user="smpc",
  work_dir = "some/dir/for/temporary/files",
  hosts=config['hosts'])

(The config['hosts'] reads a config file where host adresses and ports
are specified.)

s.add_benchmark(BenchmarkToft05({
'runs': 100,
'n': 3,
'threshold': 1,
'modulus': 2342342348883
'use_ssl': True}))

s.run()

In this case, the Toft05 comparison is run 100 times with 3 players
and security threshold 1 using ssl_connection between the players.
Multiple benchmarks can be added to the suite before running it. The
resulting timings are stored in the database. Any parameter that is
specified when adding a benchmark will be available to the running
benchmark, e.g. in the protocol()-method.

3) Visualize the results. Data can be fetched directly from the
database or through some helper methods (not quite written yet...) and
visualized using e.g. matplotlib. Each single result is stored, so
statistical analysis such as computing confidence intervals, is
possible.


That's it. If you want to benchmark something that does not involve a
protocol, e.g. just the time it takes to do a local multiplication (or
even something unrelated to VIFF), you can subclass Benchmark instead
of VIFFBenchmark. It works almost the same way execpt that the
benchmark is only run on one machine and there is no runtime
available.

I've used the application to set up a few benchmarks and run it on our
new benchmark servers. The autogenerated result can be seen on
http://www.daimi.au.dk/~tpj/web. It shows two benchmarks for the tip
revision. There's also a "history" graph showing execution time of the
Toft05 comparison back in time. Each dot represents a mercurial
commit. Luckily it gets faster and faster :-) I admit there's not much
explanation to the graphs yet, but I hope it's enough to illustrate
the use of the application.

The script that generated the graphs can easily be set up to run
regularly as a cronjob. I'm about to do that such that we always have
an up-to-date view on the performance of VIFF. You are welcome to use
the application for your self, but if you have a benchmark that you
will like to be included in the "nightly benchmark" - and preferably,
some code or concrete idea how to do the benchmark, you are welcome to
contanct me and I will try to include it.

If you are interested in the source and have access to the DAIMI file
system, it is located at /users/tpj/viff-repos/viff-benchmark. I will
later put it on viff.dk. If you have problems getting it to work, I'll
like to hear about that, too.

Disclaimer: The code is still very much "alpha".

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] Viff installation on Gentoo

[Martin Geisler]

Marcel Keller <[EMAIL PROTECTED]> writes:

> Martin Geisler schrieb:
>> Marcel Keller <[EMAIL PROTECTED]> writes:
>>
>>> As requested, here is the command to install the dependencies on Gentoo:
>>>
>>> $ emerge -av twisted gmpy
>>>
>>> Make sure to have the crypt use flag enabled, otherwise SSL might not
>>> be available.
>>
>> Thank you very much! I have included this in the online installation
>> guide:
>>
>>   http://viff.dk/doc/install.html#gnu-linux
>>
>> The Debian instructions include pyOpenSSL too, should the Gentoo
>> instructions not have that as well?
>
> If the crypt use flag is enabled, pyOpenSSL is a dependency of
> twisted.

Ah, nice! I didn't expect this :-)

> One could also install pyOpenSSL directly (emerge pyopenssl), but
> that will be broken if twisted changes its SSL library. On the other
> hand, the use flag could also change.

>From what you say the current instructions seem the best. Thanks for
the help.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Viff installation on Gentoo

[Marcel Keller]

Martin Geisler schrieb:

Marcel Keller <[EMAIL PROTECTED]> writes:


As requested, here is the command to install the dependencies on Gentoo:

$ emerge -av twisted gmpy

Make sure to have the crypt use flag enabled, otherwise SSL might not
be available.


Thank you very much! I have included this in the online installation
guide:

  http://viff.dk/doc/install.html#gnu-linux

The Debian instructions include pyOpenSSL too, should the Gentoo
instructions not have that as well?


If the crypt use flag is enabled, pyOpenSSL is a dependency of twisted. 
One could also install pyOpenSSL directly (emerge pyopenssl), but that 
will be broken if twisted changes its SSL library. On the other hand, 
the use flag could also change.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Viff installation on Gentoo

[Martin Geisler]

Marcel Keller <[EMAIL PROTECTED]> writes:

> As requested, here is the command to install the dependencies on Gentoo:
>
> $ emerge -av twisted gmpy
>
> Make sure to have the crypt use flag enabled, otherwise SSL might not
> be available.

Thank you very much! I have included this in the online installation
guide:

  http://viff.dk/doc/install.html#gnu-linux

The Debian instructions include pyOpenSSL too, should the Gentoo
instructions not have that as well?

-- 
Martin Geisler


pgpdVVJJeZ1Ma.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

[viff-devel] Viff installation on Gentoo

[Marcel Keller]

As requested, here is the command to install the dependencies on Gentoo:

$ emerge -av twisted gmpy

Make sure to have the crypt use flag enabled, otherwise SSL might not be 
available.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.7.1 released

[Martin Geisler]

Hello everybody,

It's my great pleasure to announce the immediate release of the latest
and greatest version of VIFF: 0.7.1. Let the release party begin! When
you're done partying, then please download it here:

  Tar/GZ:  http://viff.dk/release/viff-0.7.1.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.7.1.tar.bz2
  Zip: http://viff.dk/release/viff-0.7.1.zip
  Exe: http://viff.dk/release/viff-0.7.1.win32.exe

This is bugfix release -- thanks to Sebastiaan and Tomas for finding a
nasty bug in the passive multiplication protocol. The NEWS file says:

Version 0.7.1, released on 2008-10-09
-

A major bug was fixed in the passive multiplication protocol in the
case where 2t + 1 != n. Unit tests were updated for Python 2.6.

* Players would do inconsistent recombination of shares in the passive
  multiplication protocol (Runtime.mul). This resulted in wrong
  answers being computed when 2t + 1 != n.

* Fixed unit tests on Python 2.6. The Bracha broadcast let the players
  send data to themselves by mistake, and for some reason this was not
  detected in earlier Python versions.

* Profiling information (from a run with --profile) is dumped in
  player-X.pstats and player-X.prof files for later analysis.

* Issue 57: Get rid of Runtime._shamir_share. The method was folded
  into Runtime.mul.

* Issue 69: The installation was simplified by including the ConfigObj
  library in the VIFF source. A system-wide installation of ConfigObj
  (if any) will be ignored.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.7

[Martin Geisler]

I'm very happy to announce the release of VIFF version 0.7:

  Tar/GZ:  http://viff.dk/release/viff-0.7.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.7.tar.bz2
  Zip: http://viff.dk/release/viff-0.7.zip
  Exe: http://viff.dk/release/viff-0.7.win32.exe

The changes since version 0.6 are:

  PyOpenSSL is now used instead of GnuTLS and this enables secure
  connections on Windows. The code dealing with starting a player has
  been made much more robust and players can now be started in any
  order. Player can now also be reliably shutdown. New runtime based on
  homomorphic Paillier encryption supports just two players. Added a new
  protocol for equality testing with secret shared result.

About VIFF:

  Virtual Ideal Functionality Framework is a framework for creating
  efficient and secure multi-party computations (SMPC). Players, who do
  not trust each other, participate in a joint computation based on
  their private inputs. The computation is done using cryptographic
  protocols which allows them to obtain a correct answer without
  revealing their private inputs. Operations supported include addition,
  multiplication, and comparison, all with Shamir secret shared outputs.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.


pgphhpz1Z8ffK.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

[viff-devel] VIFF 0.6 released!

[Martin Geisler]

I am happy to announce the release of VIFF version 0.6:

  Tar/GZ:  http://viff.dk/release/viff-0.6.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.6.tar.bz2
  Zip: http://viff.dk/release/viff-0.6.zip
  Exe: http://viff.dk/release/viff-0.6.win32.exe

Executive summary of the changes since VIFF 0.5:

  The average time for a secure comparison was reduced by 60-70%.
  Comparisons now work with an actively secure multiplication protocol.
  A memory leak was fixed. Converted documentation to new Sphinx format,
  please see: http://viff.dk/doc/index.html

More details:

* A new prss_lsb function in viff.prss efficiently produces a share of
  a random field element together with a GF256 share of its least
  significant bit. This made comparisons 3-4 times faster.

* New default flavors has been added to viff.comparison which uses the
  actively secure multiplication protocol. Actively secure comparisons
  take about twice as long as passive secure comparisons.

* When data was sent and received empty deque objects were left behind
  in the ShareExchanger.incoming_data dictionaries. That caused a
  memory leak which is now fixed. An example application, gc-test.py,
  was added to test this and similar problems.

* The documentation is now generated using Sphinx and aims to be more
  like a manual than purely an API documentation. The extended section
  on program counters is an example of this.

* Fixed a bug that made 'GF256(1) != GF256(1)' return 'True'.

* Calling '~GF256(255)' would throw a KeyError, fixed.

* Issue 19: Make Runtime.convert_bit_share actively secure.

-- 
Martin Geisler


pgpS9DZfN7fkA.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] viff: Switch to prss_share_bit_double in comparisons.

[Martin Geisler]

Ivan Bjerre Damgaard <[EMAIL PROTECTED]> writes:

> Quoting Martin Geisler <[EMAIL PROTECTED]>:
>>..
>> but this makes
>>
>>   viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest
>>
>> go into what looks like a never-ending loop?! You you have a better
>> solution, then I'm all ears! :-)
>
> What is wrong with just doing a single normal secure multiplication,
> and then open the result?

That was what I tried to do... I don't know why it didn't work. I have
now created Issue 42 to track this:

  http://tracker.viff.dk/issue42

Who wants to have the honor of fixing bug 42?! :-)

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: Switch to prss_share_bit_double in comparisons.

[Ivan Bjerre Damgaard]

Quoting Martin Geisler <[EMAIL PROTECTED]>:
>..
> but this makes
>
>   viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest
>
> go into what looks like a never-ending loop?! You you have a better
> solution, then I'm all ears! :-)

What is wrong with just doing a single normal secure multiplication, and then
open the result?

If we want to optimize, we have to have a way to PRSS-create a random degree 2t
polynomial that is 0 in 0. This is close to what we discussed at the meeting
today. Given that, we first make a random shared a, and a random degree 2t
polynomial g, with g(0)=0. Then locally square your share in a, add to your
share in g and broadcast. This will securely compute a^2, with passive security
if t< n/2.

If you want active security, it's more complicated, and it may be easier as a
first step to just call a normal multiplication to get a^2. Then you get
whatever security that multiplication offers.

regards, Ivan

regards, Ivan
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: Switch to prss_share_bit_double in comparisons.

[Martin Geisler]

Tomas Toft <[EMAIL PROTECTED]> writes:

> Martin Geisler wrote:
>
>>   Before: 1309 ms per comparison with 100 parallel comparisons
>>   After:   324 ms per comparison with 100 parallel comparisons
>
> Nice speedup. It's also possible to do a similar thing for
> ComparisonToft07Mixin. In the two-fields variation we need the same
> bit in Zp and Zq, where q<
> Similarly to generating the same random bit in Zp and GF(256), we
> can
>
> 1) generate a random bit [b]_p in Zp
> 2) generate a pseudorandom number [r]_p (of limited size) in Zp and
> the same number mod q in Zq [r mod q]_q (similar to the present case,
> where q "implicitly" is two)
> 3) c  <- open([b]_p + [r]_p)
> 4) [b]_q = ((c mod q) - [r mod q]_q)

Will you send a patch with this? There are also scary number of TODOs
still left in the the code you wrote in ComparisonToft07Mixin class...

> Anyway. looking at this lead Mikkel and me to look at
> prss_share_random in runtime.py, and there seems to be either a bug
> (information leak) /or/ a possibility of optimisation when sharing a
> bit in Zp.
>
>
> The problem is the following:
>
> result = self.open(Share(self, field, share*share),
> threshold=2*self.threshold)
>
> Is the "*" in "share*share" a multiplication protocol or a
> multiplication of actual values?

The types are always such that the Share class wraps FieldElements,
which in turn wraps normal integers. So this is a multiplication of
two FieldElements with no multiplication protocol running behind the
scenes :-(

> If it is actual values, then we *cannot* simply call it shares and
> open it, as the polynomial is not uniformly random (this can also be
> done with PRSS and no communication).

You're right... I made that change five weeks ago:

  http://hg.viff.dk/viff/rev/d1d4c633fca8

I'm glad that you guys took a look at the code!

> If on the other hand it is an invoation of the multiplication
> protocol, then it is secure but can be optimised with the PRSS
> version mentioned above.

If you see how to make it both secure and efficient, then please send
a patch (or let me know where I can pull one)! I once put up a guide
for VIFF developement, that might come in handy:

  http://viff.dk/doc/development.html

I just tried fixing it, but it seems that I have stepped into some
strange bugs (which I do not understand) by doing so. I tried with

element = prss(self.num_players, self.id, field, prfs, prss_key)
share = Share(self, field, element)

if field is GF256 or not binary:
return share

# Open the square and compute a square-root
result = self.open(share * share)

def finish(square, element, binary):
if square == 0:
# We were unlucky, try again...
return self.prss_share_random(field, binary)
else:
# We can finish the calculation
root = square.sqrt()
# When the root is computed, we divide the share and
# convert the resulting -1/1 share into a 0/1 share.
return Share(self, field, (element/root + 1) / 2)

self.schedule_callback(result, finish, element, binary)
return result

but this makes

  viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest

go into what looks like a never-ending loop?! You you have a better
solution, then I'm all ears! :-)


-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: Switch to prss_share_bit_double in comparisons.

[Tomas Toft]

Hi

Martin Geisler wrote:

viff-devel@viff.dk writes:

Hi everybody,

I don't know how many of you follow the commits to the VIFF repository?
Would anybody be interested in a mailing list for it?

Anyway -- the latest commit is this:


http://hg.viff.dk/viff/rev/5dd8c277268c
changeset: 751:5dd8c277268c
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Tue May 13 16:28:41 2008 +0200
summary:   Switch to prss_share_bit_double in comparisons.


This change makes the ComparisonToft05Mixin.greater_than_equal method
actively secure and much faster!

Running three players on my home computer gives these results:

  Before: 1309 ms per comparison with 100 parallel comparisons
  After:   324 ms per comparison with 100 parallel comparisons

That is a factor of four! I measured similar improvements earlier today
when using three different machines at DAIMI.


Nice speedup. It's also possible to do a similar thing for 
ComparisonToft07Mixin. In the two-fields variation we need the same bit 
in Zp and Zq, where q<

Similarly to generating the same random bit in Zp and GF(256), we can

1) generate a random bit [b]_p in Zp
2) generate a pseudorandom number [r]_p (of limited size) in Zp and the 
same number mod q in Zq [r mod q]_q (similar to the present case, where 
q "implicitly" is two)

3) c  <- open([b]_p + [r]_p)
4) [b]_q = ((c mod q) - [r mod q]_q)


Anyway. looking at this lead Mikkel and me to look at
prss_share_random in runtime.py, and there seems to be either a bug 
(information leak) /or/ a possibility of optimisation when sharing a bit 
in Zp.



The problem is the following:

result = self.open(Share(self, field, share*share), 
threshold=2*self.threshold)


Is the "*" in "share*share" a multiplication protocol or a 
multiplication of actual values? If it is actual values, then we 
*cannot* simply call it shares and open it, as the polynomial is not 
uniformly random (this can also be done with PRSS and no communication).


If on the other hand it is an invoation of the multiplication protocol, 
then it is secure but can be optimised with the PRSS version mentioned 
above.



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] viff: Switch to prss_share_bit_double in comparisons.

[Martin Geisler]

viff-devel@viff.dk writes:

Hi everybody,

I don't know how many of you follow the commits to the VIFF repository?
Would anybody be interested in a mailing list for it?

Anyway -- the latest commit is this:

> http://hg.viff.dk/viff/rev/5dd8c277268c
> changeset: 751:5dd8c277268c
> user:  Martin Geisler <[EMAIL PROTECTED]>
> date:  Tue May 13 16:28:41 2008 +0200
> summary:   Switch to prss_share_bit_double in comparisons.

This change makes the ComparisonToft05Mixin.greater_than_equal method
actively secure and much faster!

Running three players on my home computer gives these results:

  Before: 1309 ms per comparison with 100 parallel comparisons
  After:   324 ms per comparison with 100 parallel comparisons

That is a factor of four! I measured similar improvements earlier today
when using three different machines at DAIMI.

-- 
Martin Geisler


pgpxfBwX16Np4.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

[viff-devel] VIFF 0.5 is released!

[Martin Geisler]

On behalf of the VIFF Development Team, I am very happy to announce the
release of VIFF 0.5. I decided that there were no reason to wait until
Wednesday to do the final release, so here it is:

  Tar/GZ:  http://viff.dk/release/viff-0.5.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.5.tar.bz2
  Zip: http://viff.dk/release/viff-0.5.zip
  Exe: http://viff.dk/release/viff-0.5.win32.exe

Changes since version 0.4:

  Added preliminary support for preprocessing and an efficient
  multiplication protocol which is secure against active adversaries.
  The Runtime class has been split into several parts and two new mixin
  classes provide different comparison protocols. Several coercion
  problems were fixed. The Runtime.callback method was renamed to
  Runtime.schedule_callback. VIFF was tested on Python 2.6 and some
  small problems were fixed. If python-gnutls is unavailable, players
  now automatically fallback to TCP connections. The installation guide
  was updated for Windows Vista. A new example program was added and the
  documentation was updated. Changed license to LGPL.

Details:

* Issue 2: Split Runtime class into smaller parts. The old Runtime
  class has been split. If your program used the greater_than_equal
  method, then you need to use the new Toft05Runtime class from
  viff.comparison. If you used greater_than_equalII, then use the
  Toft07Runtime from the same module.

* Issue 3: Preprocessing. The runtime will now log the use of certain
  methods and this log can be used to preprocess the needed data.

* Issue 7: New system for unit tests. The tests now better simulate an
  asynchronous network by randomly delaying the communication between
  the players.

* Better coercion. The comparison in Toft07Runtime can now correctly
  deal with arguments of mixed types, e.g., comparisons like "100 < x"
  where x is a Share.

* The coercion done by the xor method was also fixed.

* Issue 30: Local multiplication if one operand is a constant. The
  runtime will now avoid an expensive resharing step when multiplying
  shares with constants.

* Issue 22: Allow sending data several times in one method. Previously
  one could only send once to a given players in a given method since
  all communication used the same program counter. The data is now
  correctly buffered on the receiving side.

* Python 2.6 compatibility. VIFF is now regularly tested on Python 2.6
  via a new build slave.

* Automatic fallback to TCP if python-gnutls is unavailable. It was
  previously necessary to specify the --no-tls flag when running the
  example applications under Windows since python-gnutls is
  unavailable there. This is now detected automatically at runtime.


-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.


pgpaGbhcc78Nr.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] viff: Try importing gnutls without introducing an unused binding.

[Martin Geisler]

Mikkel Krøigård <[EMAIL PROTECTED]> writes:

>> http://hg.viff.dk/viff/rev/19b875e0d65d
>> changeset: 685:19b875e0d65d
>> user:  Martin Geisler <[EMAIL PROTECTED]>
>> date:  Fri Apr 25 11:54:29 2008 +0200
>> summary:   Try importing gnutls without introducing an unused binding.
>>
>
> Just tested this in Windows. You no longer have to write --no-tls,
> it gets disabled by default.

Excellent, thanks for testing this!

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: Try importing gnutls without introducing an unused binding.

[Mikkel Krøigård]

> http://hg.viff.dk/viff/rev/19b875e0d65d
> changeset: 685:19b875e0d65d
> user:  Martin Geisler <[EMAIL PROTECTED]>
> date:  Fri Apr 25 11:54:29 2008 +0200
> summary:   Try importing gnutls without introducing an unused binding.
>

Just tested this in Windows. You no longer have to write --no-tls, it gets
disabled by default.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: 5 new changesets

[Martin Geisler]

viff-devel@viff.dk writes:

> http://hg.viff.dk/viff/rev/74f54302aeb0
> changeset: 682:74f54302aeb0
> user:  Martin Geisler <[EMAIL PROTECTED]>
> date:  Fri Apr 25 10:03:36 2008 +0200
> summary:   Auto-detect if we can use TLS or not.

This change should allow you to run the example programs on Windows
without specifying --no-tls. Could somebody using Windows (Mikkel,
Tomas, Thomas) please make sure to test that this works as expected?

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF 0.5rc1 has been released!

[Martin Geisler]

Martin Geisler <[EMAIL PROTECTED]> writes:

> Hi,
>
> On behalf of the VIFF Development Team, I'm very happy to announce
> the release of VIFF version 0.5rc1:
>
>   Tar/GZ:  http://viff.dk/release/viff-0.5rc1.tar.gz
>   Tar/BZ2: http://viff.dk/release/viff-0.5rc1.tar.bz2
>   Zip: http://viff.dk/release/viff-0.5rc1.zip
>   Exe: http://viff.dk/release/viff-0.5rc1.win32.exe
>
> This is the first release candidate of VIFF 0.5. If we hear of no
> problems with this one, we will make the final release in a week.

Mikkel has already updated the installation instructions for Windows
Vista, please see: http://viff.dk/install.html

If you find any other problems, typos, strange stuff, then please let
us know!

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.5rc1 has been released!

[Martin Geisler]

Hi,

On behalf of the VIFF Development Team, I'm very happy to announce the
release of VIFF version 0.5rc1:

  Tar/GZ:  http://viff.dk/release/viff-0.5rc1.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.5rc1.tar.bz2
  Zip: http://viff.dk/release/viff-0.5rc1.zip
  Exe: http://viff.dk/release/viff-0.5rc1.win32.exe

This is the first release candidate of VIFF 0.5. If we hear of no
problems with this one, we will make the final release in a week.

The changes since version 0.4 are:

  Added preliminary support for preprocessing and an efficient
  multiplication protocol which is secure against active adversaries.
  The Runtime class has been split into several parts and two new
  mixin classes provide different comparison protocols. Several
  coercion problems were fixed. The Runtime.callback method was
  renamed to Runtime.schedule_callback. VIFF was tested on Python 2.6
  and some small problems were fixed. A new example program was added
  and the documentation was updated.

Details:

* Issue 2: Split Runtime class into smaller parts. The old Runtime
  class has been split. If your program used the greater_than_equal
  method, then you need to use the new Toft05Runtime class from
  viff.comparison. If you used greater_than_equalII, then use the
  Toft07Runtime from the same module.

* Issue 3: Preprocessing. The runtime will now log the use of certain
  methods and this log can be used to preprocess the needed data.

* Issue 7: New system for unit tests. The tests now better simulate an
  asynchronous network by randomly delaying the communication between
  the players.

* Better coercion. The comparison in Toft07Runtime can now correctly
  deal with arguments of mixed types, e.g., comparisons like "100 < x"
  where x is a Share.

* The coercion done by the xor method was also fixed.

* Issue 30: Local multiplication if one operand is a constant. The
  runtime will now avoid an expensive resharing step when multiplying
  shares with constants.

* Issue 22: Allow sending data several times in one method. Previously
  one could only send once to a given players in a given method since
  all communication used the same program counter. The data is now
  correctly buffered on the receiving side.

* Python 2.6 compability. VIFF is now regularly tested on Python 2.6
  via a new build slave.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.4 has been released!

[Martin Geisler]

Hello,

I'm very happy to announce the release of VIFF version 0.4:

  Tar/GZ:  http://viff.dk/release/viff-0.4.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.4.tar.bz2
  Zip: http://viff.dk/release/viff-0.4.zip
  Exe: http://viff.dk/release/viff-0.4.win32.exe

The viff-0.4.win32.exe is a Windows installer which contains no examples
or documentation, please download viff-0.4.zip to get those.

The changes since version 0.3 are:

  Implemented a reliable Bracha broadcast which is secure against active
  adversaries. Shamir sharings, pseudo-random as well as standard, can
  now be asymmetric which means that only a subset of the parties
  provide input. The open protocol is now also asymmetric, in the sense
  that only a subset of the parties receive the opened result. The
  behavior of field elements in Boolean expressions has been fixed. This
  means that "GF256(0) and GF256(1)" now returns GF256(0) instead of
  GF256(1). Added a modern implementation of the classic Yao
  millionaires example from 1982 which started this field of research.

  Details:

  * Bracha broadcast, which is a reliable broadcast mechanism against
active adversaries, has been implemented. Secure broadcast is a
building block that is often used in active security scenarios.

  * Asymmetric Shamir sharing. It is now possible to specify that just a
subset of the players should provide input to a Shamir sharing. This
change is not backwards compatible with version 0.3 or earlier.
Adapting old programs is easy, simply change:

  a, b, c = rt.shamir_share(Zp(input))

to

  a, b, c = rt.shamir_share([1, 2, 3], Zp, input)

where Zp is a field and rt is a Runtime.

  * Asymmetric pseudo-random secret sharing. As the asymmetric Shamir
sharing above, this is not backwards compatible. This can be fixed
by changing statements such as e.g.

  a, b, c = rt.prss_share(Zp(input))

to

  a, b, c = rt.prss_share([1, 2, 3], Zp, input)

where Zp is a field and rt is a Runtime.

  * Asymmetric open protocol, meaning that it is now possible to specify
that only a subset of the players should receive the opened secret.
This change is not backwards compatible in cases, where threshold is
explicitly passed as a parameter. To correct this, name the
threshold parameter, e.g. change

  result = rt.open(sharing, rt.threshold * 2)

to

  result = rt.open(sharing, threshold=rt.threshold * 2)

  * Overloaded exclusive-or operations on Share instances. Given two
shares a and b, one can now do

  c = a ^ b

to obtain the exclusive-or. This works for both GF256 shares and Zp
shares, though the two types must not be mixed.


-- 
Martin Geisler


pgptULuhRBgIk.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] viff: 9 new changesets

[Martin Geisler]

viff-devel@viff.dk writes:

Hi VIFFers :-)

> http://hg.viff.dk/viff/rev/1121ca038c8b
> changeset: 492:1121ca038c8b
> user:  Martin Geisler <[EMAIL PROTECTED]>
> date:  Fri Mar 07 23:47:25 2008 +0100
> summary:   Added simple script to control the build process.

Those of you who follow the commits will have seen that I have comitted
a script called run.py which now has the responsibitity of running all
our tests and building documentation.

At first I thought about making a Makefile, but I guess that wont run
easily on Windows. And since VIFF already requires Python and Twisted, I
made a Python script instead.

The idea is that Buildbot (http://buildbot.viff.dk) will run the script
and instead of putting logic into the Buildbot, we can put it in the
script where everybody can see it.

So far I have moved all the commands for the Linux systems I have access
to and things finally seem to work.

People on other platforms will hopefully be able to check if things work
there too, and if not, I hope they can fix it by hacking run.py. There
you can use all the platform specific tricks you can come up with :-)

For example, to run special code for when you are on Windows you will do

  import sys
  if sys.platform == "win32":
# Do Windows stuff...
  else:
# Do default stuff...

For Mac OS X the sys.platform string is "darwin" as far as I know.

I hope that this script will finally enable us to have regular builds on
all three major platforms, so please start hacking :-)

-- 
Martin Geisler


pgpF7oyEQF0l1.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] viff: 2 new changesets

[Martin Geisler]

viff-devel@viff.dk writes:

> http://hg.viff.dk/viff/rev/4f7cc081dcff
> changeset: 445:4f7cc081dcff
> user:  Martin Geisler <[EMAIL PROTECTED]>
> date:  Fri Feb 22 13:29:50 2008 +0100
> summary:   Mention the Bracha broadcast here.

And I have now also disabled these notifications! Let me know if you
want them back...

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] viff: 2 new changesets

[viff-devel]

http://hg.viff.dk/viff/rev/4f7cc081dcff
changeset: 445:4f7cc081dcff
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Fri Feb 22 13:29:50 2008 +0100
summary:   Mention the Bracha broadcast here.

http://hg.viff.dk/viff/rev/31f7051556ac
changeset: 446:31f7051556ac
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Fri Feb 22 13:40:48 2008 +0100
summary:   We now have an online bibliography.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] viff: 3 new changesets

[viff-devel]

http://hg.viff.dk/viff/rev/0219cfbc8b28
changeset: 442:0219cfbc8b28
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Fri Feb 22 11:38:39 2008 +0100
summary:   Removed "proof of concept" from description.

http://hg.viff.dk/viff/rev/ea1fa3db09db
changeset: 443:ea1fa3db09db
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Fri Feb 22 13:07:46 2008 +0100
summary:   Better heading.

http://hg.viff.dk/viff/rev/3958f7685e50
changeset: 444:3958f7685e50
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Fri Feb 22 13:24:50 2008 +0100
summary:   Merged.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] viff: 2 new changesets

[viff-devel]

http://hg.viff.dk/viff/rev/5e18dc77b09b
changeset: 440:5e18dc77b09b
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Tue Feb 19 23:08:38 2008 +0100
summary:   Add Bracha broadcast to the keyword list.

http://hg.viff.dk/viff/rev/a318522fe51d
changeset: 441:a318522fe51d
user:  Martin Geisler <[EMAIL PROTECTED]>
date:  Tue Feb 19 23:10:49 2008 +0100
summary:   Add "secret" to module docstring.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF coding style and a HACKING-style guide for developers

[Martin Geisler]

Martin Geisler <[EMAIL PROTECTED]> writes:

> * Thomas: How do I create a new unit test? Not just one, I want to
>   create many with randomized parameters! What to do?

I spend a bit of time writing about unit testing with VIFF:

  http://viff.dk/docs/unit-testing.html

Let me know what you think -- preferably in the form of patches
against http://hg.viff.dk/viff.dk :-)

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF unit tests

[Martin Geisler]

Janus Dam Nielsen <[EMAIL PROTECTED]> writes:

>> But I asked since I am not sure I completely understand how you want
>> this implemented?
>
> Neither do I. I just want to be naive and stupid and run the entire
> test suite with a set of parameters without having to remember or even
> know that a certain testcase does not support my parameter. How to do
> this, I don't know. I just like it.

Then all I can say is that I think we have an idea for a possible
solution below... :-)

> Den 15/02/2008 kl. 10.21 skrev Martin Geisler:
>
>> Janus Dam Nielsen <[EMAIL PROTECTED]> writes:
>>
> I think that having parametrized tests is good, however I just
> wanted to point out that defining the parameters in the Runtime
> class/object might not be suffienciently expressive to what we
> want.
> We might would like a kind of grouping/system of tests so that it
> is
> easy to run the tests without any particular knowledge of which
> protocols support which parameters.
>
> Those tests for which a given set of parameters is invalid, the
> test
> could return an undefined value, or the test could be elided from
> the set of tests since it doesn't make any sense for these
> parameters anyhow.

 The test suite is implemented using Trial, a Twisted tool which
 extends the standard Python unittest module with support for
 Deferreds. The Python unittest module is modelled after JUnit.

 In Trial there is support for marking a test as skipped, and that
 might be useful for what you are describing -- we could query the
 tests for their requirements and if they do not match the parameters
 of the current test, then we skip that test.

 Something like that could work, but I don't know if it is the best
 way... Have you looked at the Trial documentation to see how it
 could
 be done? There is a tutorial here:

   http://twistedmatrix.com/trac/browser/branches/trial-
 tutorial-2443/doc/core/howto/trial.xhtml?format=raw

 and the API documentation is here:

   http://twistedmatrix.com/documents/current/api/
 twisted.trial.unittest.TestCase.html

 Trial is not so well documented as the rest of Twisted, so looking
 at
 the source code has helped me a bit until I found the above
 tutorial.
>>>
>>> I haven't looked at the code. I just wanted to make sure you didn't
>>> shoot yourself in the foot unintentionally :)
>>
>> Yeah, thanks, that would be bad :-) so it is really nice to get some
>> input in these design questions!
>>
>> But I asked since I am not sure I completely understand how you want
>> this implemented?
>>
>> You want some set of parameters that are specified on the command line
>> when one starts Trial, or should they be put in the unit tests
>> directly?
>>
>> The latter is easy, and we can already now generate many unit tests
>> with
>> small differences such as the number of players. Adding this to
>> test_active_runtime.py:
>>
>> class Active5(ActiveRuntimeTest):
>> num_players = 5
>>
>> class Active6(ActiveRuntimeTest):
>> num_players = 6
>>
>> class Active7(ActiveRuntimeTest):
>> num_players = 7
>>
>> makes the Bracha broadcast test be run three more times, but with more
>> players. It even works, I just tested! :-)
>>
>> That might be a good way to do things: code a TestCase with some unit
>> tests, but be sure to make them generic in the sense that they can be
>> run with any number of players (or threshold). Then create several
>> subclasses like above. The classes can even be created at runtime:
>>
>> for n in range(3,6):
>> code = """
>> class Active%d(ActiveRuntimeTest):
>> num_players = %d
>> """ % (n, n)
>> exec code
>>
>> Trial never notices the difference and runs our tests as normal!
>>
>> This way we have lots of power over how the tests are generated: we
>> can
>> easily test, say, all n<10, 10 randomly chosen n between 10 and 50,
>> and
>> 5 random n's between 50 and 100. Something like that...
>>
>> --
>> Martin Geisler
>> ___
>> viff-devel mailing list (http://viff.dk/)
>> viff-devel@viff.dk
>> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>

-- 
Martin Geisler


pgp3Wq7tZo8nZ.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

[viff-devel] VIFF coding style and a HACKING-style guide for developers

[Martin Geisler]

Hi guys,

I have added a little page with some information on the coding style
used in VIFF:

  http://viff.dk/docs/coding-style.html

I also added some "buttons" in a header -- I chose a simple and very
old-school way of doing this: links in square brackets. I wanted to keep
things simple, but perhaps it would be better to turn the links into
proper buttons as on the frontpage? Comments are very welcome! (Comments
with patches are even more welcome, remember that you can checkout the
website from http://hg.viff.dk/viff.dk/.)


I am also making a document which will describe VIFF from the
perspective of someone who wants to change it -- I called it hacking.txt
as a start to continue the long tradition of including a HACKING file
along side the README and INSTALL files.

My idea for the document is that it should contain the more detailed
explainations which aren't suitable for docstrings. There is already
some quite long (too long, I think) docstrings in runtime.py explaining
stuff like program counters. I think it would be better to make a short
docstring which references a webpage instead.

On the other hand, it might be a bad idea to spread the documentation
over too many places -- it will probably be easier to forget to update
it then. And people might end up with code on their systems for which
the documentation is no longer online (though they can always find it in
the website repository). Again, let me know what you think of this...


I would like to get input on what kind of subjects you want me to write
about. I think there should be something that answers concrete task-
oriented questions like:

* Tord: I want to implement my super comparison protocol which uses no
  rounds, no multiplications, no players, no everything! How do I start?

* Thomas: How do I create a new unit test? Not just one, I want to
  create many with randomized parameters! What to do?

Those kind of questions :-)

And some details on the program counter magic, not just how it works but
also why it is necessary in the first place.


That was all for now -- now I must go back to my slides for my
qualification exam on Thursday...

-- 
Martin Geisler


pgp6T7D1hgL9F.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] VIFF unit tests

[Janus Dam Nielsen]

> But I asked since I am not sure I completely understand how you want
> this implemented?

Neither do I. I just want to be naive and stupid and run the entire  
test suite with a set of parameters without having to remember or  
even know that a certain testcase does not support my parameter. How  
to do this, I don't know. I just like it.

--
Janus


Den 15/02/2008 kl. 10.21 skrev Martin Geisler:

> Janus Dam Nielsen <[EMAIL PROTECTED]> writes:
>
 I think that having parametrized tests is good, however I just
 wanted to point out that defining the parameters in the Runtime
 class/object might not be suffienciently expressive to what we  
 want.
 We might would like a kind of grouping/system of tests so that  
 it is
 easy to run the tests without any particular knowledge of which
 protocols support which parameters.

 Those tests for which a given set of parameters is invalid, the  
 test
 could return an undefined value, or the test could be elided from
 the set of tests since it doesn't make any sense for these
 parameters anyhow.
>>>
>>> The test suite is implemented using Trial, a Twisted tool which
>>> extends the standard Python unittest module with support for
>>> Deferreds. The Python unittest module is modelled after JUnit.
>>>
>>> In Trial there is support for marking a test as skipped, and that
>>> might be useful for what you are describing -- we could query the
>>> tests for their requirements and if they do not match the parameters
>>> of the current test, then we skip that test.
>>>
>>> Something like that could work, but I don't know if it is the best
>>> way... Have you looked at the Trial documentation to see how it  
>>> could
>>> be done? There is a tutorial here:
>>>
>>>   http://twistedmatrix.com/trac/browser/branches/trial-
>>> tutorial-2443/doc/core/howto/trial.xhtml?format=raw
>>>
>>> and the API documentation is here:
>>>
>>>   http://twistedmatrix.com/documents/current/api/
>>> twisted.trial.unittest.TestCase.html
>>>
>>> Trial is not so well documented as the rest of Twisted, so  
>>> looking at
>>> the source code has helped me a bit until I found the above  
>>> tutorial.
>>
>> I haven't looked at the code. I just wanted to make sure you didn't
>> shoot yourself in the foot unintentionally :)
>
> Yeah, thanks, that would be bad :-) so it is really nice to get some
> input in these design questions!
>
> But I asked since I am not sure I completely understand how you want
> this implemented?
>
> You want some set of parameters that are specified on the command line
> when one starts Trial, or should they be put in the unit tests  
> directly?
>
> The latter is easy, and we can already now generate many unit tests  
> with
> small differences such as the number of players. Adding this to
> test_active_runtime.py:
>
> class Active5(ActiveRuntimeTest):
> num_players = 5
>
> class Active6(ActiveRuntimeTest):
> num_players = 6
>
> class Active7(ActiveRuntimeTest):
> num_players = 7
>
> makes the Bracha broadcast test be run three more times, but with more
> players. It even works, I just tested! :-)
>
> That might be a good way to do things: code a TestCase with some unit
> tests, but be sure to make them generic in the sense that they can be
> run with any number of players (or threshold). Then create several
> subclasses like above. The classes can even be created at runtime:
>
> for n in range(3,6):
> code = """
> class Active%d(ActiveRuntimeTest):
> num_players = %d
> """ % (n, n)
> exec code
>
> Trial never notices the difference and runs our tests as normal!
>
> This way we have lots of power over how the tests are generated: we  
> can
> easily test, say, all n<10, 10 randomly chosen n between 10 and 50,  
> and
> 5 random n's between 50 and 100. Something like that...
>
> -- 
> Martin Geisler
> ___
> 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] VIFF unit tests

[Martin Geisler]

Janus Dam Nielsen <[EMAIL PROTECTED]> writes:

>>> I think that having parametrized tests is good, however I just
>>> wanted to point out that defining the parameters in the Runtime
>>> class/object might not be suffienciently expressive to what we want.
>>> We might would like a kind of grouping/system of tests so that it is
>>> easy to run the tests without any particular knowledge of which
>>> protocols support which parameters.
>>>
>>> Those tests for which a given set of parameters is invalid, the test
>>> could return an undefined value, or the test could be elided from
>>> the set of tests since it doesn't make any sense for these
>>> parameters anyhow.
>>
>> The test suite is implemented using Trial, a Twisted tool which
>> extends the standard Python unittest module with support for
>> Deferreds. The Python unittest module is modelled after JUnit.
>>
>> In Trial there is support for marking a test as skipped, and that
>> might be useful for what you are describing -- we could query the
>> tests for their requirements and if they do not match the parameters
>> of the current test, then we skip that test.
>>
>> Something like that could work, but I don't know if it is the best
>> way... Have you looked at the Trial documentation to see how it could
>> be done? There is a tutorial here:
>>
>>   http://twistedmatrix.com/trac/browser/branches/trial-
>> tutorial-2443/doc/core/howto/trial.xhtml?format=raw
>>
>> and the API documentation is here:
>>
>>   http://twistedmatrix.com/documents/current/api/
>> twisted.trial.unittest.TestCase.html
>>
>> Trial is not so well documented as the rest of Twisted, so looking at
>> the source code has helped me a bit until I found the above tutorial.
>
> I haven't looked at the code. I just wanted to make sure you didn't
> shoot yourself in the foot unintentionally :)

Yeah, thanks, that would be bad :-) so it is really nice to get some
input in these design questions!

But I asked since I am not sure I completely understand how you want
this implemented?

You want some set of parameters that are specified on the command line
when one starts Trial, or should they be put in the unit tests directly?

The latter is easy, and we can already now generate many unit tests with
small differences such as the number of players. Adding this to
test_active_runtime.py:

class Active5(ActiveRuntimeTest):
num_players = 5

class Active6(ActiveRuntimeTest):
num_players = 6

class Active7(ActiveRuntimeTest):
num_players = 7

makes the Bracha broadcast test be run three more times, but with more
players. It even works, I just tested! :-)

That might be a good way to do things: code a TestCase with some unit
tests, but be sure to make them generic in the sense that they can be
run with any number of players (or threshold). Then create several
subclasses like above. The classes can even be created at runtime:

for n in range(3,6):
code = """
class Active%d(ActiveRuntimeTest):
num_players = %d
""" % (n, n)
exec code

Trial never notices the difference and runs our tests as normal!

This way we have lots of power over how the tests are generated: we can
easily test, say, all n<10, 10 randomly chosen n between 10 and 50, and
5 random n's between 50 and 100. Something like that...

-- 
Martin Geisler


pgpqDrd8ZCeHb.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] VIFF unit tests

[Janus Dam Nielsen]

I haven't looked at the code. I just wanted to make sure you didn't  
shoot yourself in the foot unintentionally :)

--
Janus


Den 15/02/2008 kl. 1.57 skrev Martin Geisler:

> Janus Dam Nielsen <[EMAIL PROTECTED]> writes:
>
>> I think that having parametrized tests is good, however I just
>> wanted to point out that defining the parameters in the Runtime
>> class/object might not be suffienciently expressive to what we want.
>> We might would like a kind of grouping/system of tests so that it is
>> easy to run the tests without any particular knowledge of which
>> protocols support which parameters.
>>
>> Those tests for which a given set of parameters is invalid, the test
>> could return an undefined value, or the test could be elided from
>> the set of tests since it doesn't make any sense for these
>> parameters anyhow.
>
> The test suite is implemented using Trial, a Twisted tool which
> extends the standard Python unittest module with support for
> Deferreds. The Python unittest module is modelled after JUnit.
>
> In Trial there is support for marking a test as skipped, and that
> might be useful for what you are describing -- we could query the
> tests for their requirements and if they do not match the parameters
> of the current test, then we skip that test.
>
> Something like that could work, but I don't know if it is the best
> way... Have you looked at the Trial documentation to see how it could
> be done? There is a tutorial here:
>
>   http://twistedmatrix.com/trac/browser/branches/trial- 
> tutorial-2443/doc/core/howto/trial.xhtml?format=raw
>
> and the API documentation is here:
>
>   http://twistedmatrix.com/documents/current/api/ 
> twisted.trial.unittest.TestCase.html
>
> Trial is not so well documented as the rest of Twisted, so looking at
> the source code has helped me a bit until I found the above tutorial.
>
> -- 
> Martin Geisler
> ___
> 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] VIFF unit tests

[Martin Geisler]

Janus Dam Nielsen <[EMAIL PROTECTED]> writes:

> I think that having parametrized tests is good, however I just
> wanted to point out that defining the parameters in the Runtime
> class/object might not be suffienciently expressive to what we want.
> We might would like a kind of grouping/system of tests so that it is
> easy to run the tests without any particular knowledge of which
> protocols support which parameters.
>
> Those tests for which a given set of parameters is invalid, the test
> could return an undefined value, or the test could be elided from
> the set of tests since it doesn't make any sense for these
> parameters anyhow.

The test suite is implemented using Trial, a Twisted tool which
extends the standard Python unittest module with support for
Deferreds. The Python unittest module is modelled after JUnit.

In Trial there is support for marking a test as skipped, and that
might be useful for what you are describing -- we could query the
tests for their requirements and if they do not match the parameters
of the current test, then we skip that test.

Something like that could work, but I don't know if it is the best
way... Have you looked at the Trial documentation to see how it could
be done? There is a tutorial here:

  
http://twistedmatrix.com/trac/browser/branches/trial-tutorial-2443/doc/core/howto/trial.xhtml?format=raw

and the API documentation is here:

  
http://twistedmatrix.com/documents/current/api/twisted.trial.unittest.TestCase.html

Trial is not so well documented as the rest of Twisted, so looking at
the source code has helped me a bit until I found the above tutorial.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF unit tests

[Janus Dam Nielsen]

I think that having parametrized tests is good, however I just wanted  
to point out that defining the parameters in the Runtime class/object  
might not be suffienciently expressive to what we want. We might  
would like a kind of grouping/system of tests so that it is easy to  
run the tests without any particular knowledge of which protocols  
support which parameters.
Those tests for which a given set of parameters is invalid, the test  
could return an undefined value, or the test could be elided from the  
set of tests since it doesn't make any sense for these parameters  
anyhow.

--
Janus


Den 14/02/2008 kl. 4.22 skrev Martin Geisler:

> "Thomas Jakobsen" <[EMAIL PROTECTED]> writes:
>
>> As Martin points out, it will be inconvenient or impossible to
>> parameterize some tests like this. But for others, it will be just
>> as easy, and in these cases we get a lot of extra testing for "free"
>> by doing it, since it will enable us to run them with many
>> parameters.
>
> We just have to remember to be very careful with the random seeds used
> in these tests -- we must be able to reproduce the tests exactly.
>
> But if we get that right, I think random testing would be great way to
> expand the scope of the current tests to make sure that everything
> still holds together with more players, larger threshold, etc.
>
> -- 
> Martin Geisler
> ___
> 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] VIFF unit tests

[Martin Geisler]

"Thomas Jakobsen" <[EMAIL PROTECTED]> writes:

> As Martin points out, it will be inconvenient or impossible to
> parameterize some tests like this. But for others, it will be just
> as easy, and in these cases we get a lot of extra testing for "free"
> by doing it, since it will enable us to run them with many
> parameters.

We just have to remember to be very careful with the random seeds used
in these tests -- we must be able to reproduce the tests exactly.

But if we get that right, I think random testing would be great way to
expand the scope of the current tests to make sure that everything
still holds together with more players, larger threshold, etc.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF unit tests

[Martin Geisler]

Jakob Illeborg Pagter <[EMAIL PROTECTED]> writes:

> Thomas Jakobsen skrev:
>
>> As Martin points out, it will be inconvenient or impossible to
>> parameterize some tests like this. But for others, it will be just
>> as easy, and in these cases we get a lot of extra testing for
>> "free" by doing it, since it will enable us to run them with many
>> parameters.
>
> Why don't you just parameterize tests by default and then let the
> test throw an error if the parameters are not within a defined legal
> range?

No reason, I guess...

By grouping tests in different classes we can already obtains some of
the wanted flexibility: the test_broadcast method is in the
ActiveRuntimeTest class because this class specifies that we need 4
players. We could change this number to be a threshold factor,
something like

  threshold_factor = 3

which would mean that we need

  num_playes > threshold_factor * threshold

which with threshold = 1 gives the four players we had before. But
given such a factor, it would be easy to generate test cases with
varying number of players and threshold.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF homepage

[Martin Geisler]

Hi everybody,

I have updated the VIFF homepage and switched from having just one
XHTML file to a system where pages are written in reStructuredText
format and then rendered to XHTML.

The first new page is just a simple page with links to the VIFF
documentation, including the design talk slides which were never
online before.

The pages can be checked out via

  hg clone http://hg.viff.dk/viff.dk

(it looks weird, I know... but like this the default target directory
is viff.dk which is nice, I think. We can easily change the URL,
though, if anybody thinks this is important.)

That gives you a bunch of .txt files which follow an easy format
described here:

  http://docutils.sourceforge.net/docs/user/rst/quickstart.html

This is the standard format used in Python for documentation that is
both easy to read and write in plain-text, but which can be turned
into HTML (and LaTeX, and probably other formats as well).


Hacking on the website is now very easy (and I'm sure you can find
some bad English you will want to correct):

  hg clone http://hg.viff.dk/viff.dk
  cd viff.dk
  ./update_news.py
  ./buildhtml.py

You only need to run update_news.py if you want to regenerate the
news-blob on the front page in your local version. It is done
automatically every two hours on viff.dk.

Now change something, add new files, and run buildhtml.py to generate
the .html files. When you are satisfied with the results, you simply
'hg commit' it and tell me to pull from your repository. We can also
setup a shared repository on viff.dk if people prefer that and I
become a bottleneck in the process.


I went with this system since it is *simple* in terms of
infrastructure -- I really like the idea of having a website that does
not depend on a huge backend system (database or webserver). With this
setup you can preview the website directly from the filesystem and
easily work on it from several locations.

Docutils (the project making reStructuredText) is not the most
flexible system out there, but again I hope that the simplicity will
be a good thing.

Let me know what you think!

Oh, one last thing:c to build the website you will need Feedparser,
Genshi, and Docutils:

  * http://feedparser.googlecode.com/files/feedparser-4.1.zip
  * http://ftp.edgewall.com/pub/genshi/Genshi-0.4.4.tar.bz2
  * http://docutils.sourceforge.net/docutils-snapshot.tgz

or for people on DAIMI: just put /home/mg/opt/lib/python in your
PYTHONPATH. That should do the trick.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF unit tests

[Jakob Illeborg Pagter]

Why don't you just parameterize tests by default and then let the test 
throw an error if the parameters are not within a defined legal range?

-- Jakob

Thomas Jakobsen skrev:
> Exactly.
> 
> As Martin points out, it will be inconvenient or impossible to
> parameterize some tests like this. But for others, it will be just as
> easy, and in these cases we get a lot of extra testing for "free" by
> doing it, since it will enable us to run them with many parameters.
> 
> -- Thomas
> 
> ___
> 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] VIFF unit tests

[Thomas Jakobsen]

Exactly.

As Martin points out, it will be inconvenient or impossible to
parameterize some tests like this. But for others, it will be just as
easy, and in these cases we get a lot of extra testing for "free" by
doing it, since it will enable us to run them with many parameters.

-- 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] VIFF unit tests

[Martin Geisler]

Janus Dam Nielsen <[EMAIL PROTECTED]> writes:

> Does it make sense to run all unit tests with the same configuations
> of players and thresholds. That is, for all protocols p, is p
> executed with x players and threshold t is p welldefined?

Well, no, not in general. If you write a protocol for seven people
Shamir sharing would look like this in VIFF:

  a, b, c, d, e, f, g = rt.shamir_share(range(1, 8), input)

and that breaks down (I guess quite spectacularly...) when you run it
with fewer than seven players.

I think Thomas wants us to write protocols that are generic in the
sense that they don't assume a particular number of players. So the
above line becomes:

  shares = rt.shamir_share(range(1, len(rt.players)+1), input)

If the next step is to add all inputs, then this is easily changed
from

  sum = a + b + c + d + e + f + g

to

  import operator
  sum = reduce(operator.add, shares)

which works any number of shares.

So it is only carefully written protocols that can be adapted like
that. Examples could be:

* Find the minimum input, the median input, the sum, or the average.

* Sort the inputs (using a simple bubble-sort or similar). The Yao
  millionaires example already sorts three elements via three
  comparisons.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Viff unit tests

[Janus Dam Nielsen]

I thing to consider.

Does it make sense to run all unit tests with the same configuations  
of players and thresholds. That is, for all protocols p, is p  
executed with x players and threshold t is p welldefined?

I suspect, out of the blue air, that this is not the case. I am I  
right or am I wrong?

--
Janus


Den 13/02/2008 kl. 8.43 skrev Martin Geisler:

> "Thomas Jakobsen" <[EMAIL PROTECTED]> writes:
>
>> I suggest that we - as far as it's reasonable - write unit tests
>> that don't depend on a specific number of players and threshold, but
>> instead use number of players and threshold as defined by
>> runtime.threshold and runtime.players. This will allow us to
>> automatically run these tests with many combinations of (no of
>> players, threshold), say, (3,1), (5,2), (5,1), (7,3).
>
> That is an excellent idea! You're right that the current unit tests
> are hard-coded to use a particular number of players (3 player for
> most of tests and 4 for the Bracha broadcast test). We should change
> this and make a setup where the same test is run with different
> parameters.
>
> Changing it is quite easy (but somewhat tedious):
>
> a, b, c = runtime.shamir_share([1, 2, 3], self.Zp, 42 +  
> runtime.id)
>
> becomes
>
> everybody = range(1, len(runtime.players)+1)
> shares = runtime.shamir_share(everybody, self.Zp, 42 +  
> runtime.id)
>
> and we can then loop over shares as we see fit. I think I will make a
> num_players field in Runtime so that we can stop writing
> len(runtime.players) so often...
>
> One can almost just use runtime.players.keys(), but since
> runtime.players is a dictionary we don't really know in which order
> the keys will come out, or more importantly, if the order is the same
> for all players.
>
>> My experience from developing protocols for the previous SIMAP
>> prototype was that testing all protocols with (3,1), (5,1) (5,2) and
>> (7,3) sometimes caught subtle bugs that wouldn't have been caught
>> when testing only (3,1) and, say, (5,2).
>
> Yeah, there might be some strange bugs hiding there...
>
> I think we should do this after a 0.4 release. There has been quite a
> lot of new features since 0.3: some asymmetric protocols, Bracha
> broadcast, xor overloading. When we have asymmetric open and
> prss_share, then I think we should release the code as VIFF 0.4.
>
> -- 
> Martin Geisler
> ___
> 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] Viff unit tests

[Martin Geisler]

"Thomas Jakobsen" <[EMAIL PROTECTED]> writes:

> I suggest that we - as far as it's reasonable - write unit tests
> that don't depend on a specific number of players and threshold, but
> instead use number of players and threshold as defined by
> runtime.threshold and runtime.players. This will allow us to
> automatically run these tests with many combinations of (no of
> players, threshold), say, (3,1), (5,2), (5,1), (7,3).

That is an excellent idea! You're right that the current unit tests
are hard-coded to use a particular number of players (3 player for
most of tests and 4 for the Bracha broadcast test). We should change
this and make a setup where the same test is run with different
parameters.

Changing it is quite easy (but somewhat tedious):

a, b, c = runtime.shamir_share([1, 2, 3], self.Zp, 42 + runtime.id)

becomes

everybody = range(1, len(runtime.players)+1)
shares = runtime.shamir_share(everybody, self.Zp, 42 + runtime.id)

and we can then loop over shares as we see fit. I think I will make a
num_players field in Runtime so that we can stop writing
len(runtime.players) so often...

One can almost just use runtime.players.keys(), but since
runtime.players is a dictionary we don't really know in which order
the keys will come out, or more importantly, if the order is the same
for all players.

> My experience from developing protocols for the previous SIMAP
> prototype was that testing all protocols with (3,1), (5,1) (5,2) and
> (7,3) sometimes caught subtle bugs that wouldn't have been caught
> when testing only (3,1) and, say, (5,2).

Yeah, there might be some strange bugs hiding there...

I think we should do this after a 0.4 release. There has been quite a
lot of new features since 0.3: some asymmetric protocols, Bracha
broadcast, xor overloading. When we have asymmetric open and
prss_share, then I think we should release the code as VIFF 0.4.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Viff unit tests

[Thomas Jakobsen]

Hi

I suggest that we - as far as it's reasonable - write unit tests that
don't depend on a specific number of players and threshold, but
instead use number of players and threshold as defined by
runtime.threshold and runtime.players. This will allow us to
automatically run these tests with many combinations of (no of
players, threshold), say, (3,1), (5,2), (5,1), (7,3).

My experience from developing protocols for the previous SIMAP
prototype was that testing all protocols with (3,1), (5,1) (5,2) and
(7,3) sometimes caught subtle bugs that wouldn't have been caught when
testing only (3,1) and, say, (5,2).

Any opinions about this?

Regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF Development Team

[Martin Geisler]

Hello!

I have just pushed a change that replaces the many occurrences of my
name with 'VIFF Development Team' throughout the code (except for the
design talk, which was held by me). I have done this since I obviously
hope we will become a team, and then it would be wrong for me to claim
credit in every file.

I also wanted to signify that every file is open for hacking by anybody.

The credits are now collected in a single file: AUTHORS. I have listed
myself, Tomas, and Mikkel so far since we three are the only ones you
will find in the hg log.

Tomas and Mikkel: I only listed an email address for myself -- if you
want your address included, then send a patch or tell me where I can 'hg
pull' from :-) Or maybe not if you don't your address to be published in
the clear like that.

-- 
Martin Geisler


pgpEZNROYNFJw.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] VIFF 0.3 has been released!

[Martin Geisler]

Janus Dam Nielsen <[EMAIL PROTECTED]> writes:

Hi Janus

> That is great news!
>
>> As expected, the time per multiplication stayed constant when I
>> varied the number of multiplications -- with the parallel scheduling
>> there is a huge difference between doing 100 and doing 1000
>> multiplications (a factor of four in a test I did).
>
> Do you have any idea about why there is a factor of four?

No, I'm afraid that I can only guess... This is the table I was able to
make some days ago for parallel multiplications:

  +-+--+
  | Number of muls  | Time per mul |
  +-+--+
  | 100 | 16.6 ms  |
  +-+--+
  | 500 |  6.8 ms  |
  +-+--+
  | 1000|  4.0 ms  |
  +-+--+
  | 3000|  2.9 ms  |
  +-+--+

When I tested sequential multiplications I got timings of 190 ms per
multiplication. When I do a traceroute from viff.dk to the computer in
Norway, it also measures a round trip time of ~190 ms (14 hops).

In theory, I would expect the parallel multiplications to take at least
190 ms and when the CPU fully loaded and the bandwidth exhausted, the
time should increase linearly. Something like this (in my poor ASCII art
skills):

  ^
  |_-
  |  _-
  |_-
  190 |
  |
  +--->
   ^
   full load

The average time per multiplication would then of course drop quickly
until the full load point, and from there on it should grow/fall until
it stabilizes on the true average.

This is just my expectation, I have not done enough tests to really
confirm it yet. (Testing is takes a lot of time and somewhat boring :-)

With the latest changes in the code I'm seeing more fluctuations in the
test results -- I don't know why that is. The slowest host is viff.dk
and it is normally twice as slow as the other two machines. I've just
tried running benchmark.py with 1000 multiplications:

  camel25: 1.165 ms
  viff.dk: 3.196 ms
  serengeti12: 1.364 ms

When I ran a similar test with 1000 multiplications using the old
multiply_benchmark.py a week ago, I got numbers like this:

  thyra03: 3.188 ms
  viff.dk: 3.357 ms
  serengeti12: 3.818 ms

These numbers are much more similar. I'll have to look into why the new
test gives different timings for the different players.

--
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF 0.3 has been released!

[Janus Dam Nielsen]

Hi Martin,

That is great news!

> As expected, the time per multiplication stayed constant when I varied
> the number of multiplications -- with the parallel scheduling there  
> is a
> huge difference between doing 100 and doing 1000 multiplications (a
> factor of four in a test I did).

Do you have any idea about why there is a factor of four?

--
Janus


Den 27/12/2007 kl. 15.13 skrev Martin Geisler:

> Martin Geisler <[EMAIL PROTECTED]> writes:
>
> Hi Ivan, Thomas, Dan, Jakob, Janus, and the rest of viff-devel!
>
> I have implemented and timed TLS in VIFF -- I figured you SIMAP guys
> might want to hear about that too.
>
>> This is the summary of changes:
>>
>>   Secure communication between the players were implemented using TLS
>>   (Transport Layer Security, the successor to SSL). An included
>>   Makefile can generate the needed certificates. The network layer  
>> was
>>   completely reimplemented, this breaks compatibility with programs
>>   written for VIFF version 0.2 or earlier.
>
> Now that we have TLS in VIFF we can finally start evaluating the
> performance in a realistic setting. Noone knew how big a performance
> loss encrypting and decrypting shares would be. As I wrote here
>
>   http://article.gmane.org/gmane.comp.cryptography.viff.devel/43
>
> there doesn't seem to be any measurable performance loss associated  
> with
> TLS(!) For version 0.3 I have also made a new benchmarking program  
> which
> can benchmark both parallel and sequential scheduling of  
> multiplications
> and comparisons. This program shows that VIFF really does manage to
> schedule things correctly as intended. When run across the Internet
> sequential multiplications took 190 ms per multiplication whereas
> parallel multiplications took only ~4 ms each.
>
> As expected, the time per multiplication stayed constant when I varied
> the number of multiplications -- with the parallel scheduling there  
> is a
> huge difference between doing 100 and doing 1000 multiplications (a
> factor of four in a test I did).
>
> If I run the sequential multiplications with three machines at the  
> DAIMI
> LAN, then I cannot measure any difference in execution time. That  
> makes
> sense too since the ping times are about 0.2 ms, and so the machines
> wait very little in the sequential case.
>
> -- 
> Martin Geisler

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF 0.3 has been released!

[Martin Geisler]

Martin Geisler <[EMAIL PROTECTED]> writes:

Hi Ivan, Thomas, Dan, Jakob, Janus, and the rest of viff-devel!

I have implemented and timed TLS in VIFF -- I figured you SIMAP guys
might want to hear about that too.

> This is the summary of changes:
>
>   Secure communication between the players were implemented using TLS
>   (Transport Layer Security, the successor to SSL). An included
>   Makefile can generate the needed certificates. The network layer was
>   completely reimplemented, this breaks compatibility with programs
>   written for VIFF version 0.2 or earlier.

Now that we have TLS in VIFF we can finally start evaluating the
performance in a realistic setting. Noone knew how big a performance
loss encrypting and decrypting shares would be. As I wrote here

  http://article.gmane.org/gmane.comp.cryptography.viff.devel/43

there doesn't seem to be any measurable performance loss associated with
TLS(!) For version 0.3 I have also made a new benchmarking program which
can benchmark both parallel and sequential scheduling of multiplications
and comparisons. This program shows that VIFF really does manage to
schedule things correctly as intended. When run across the Internet
sequential multiplications took 190 ms per multiplication whereas
parallel multiplications took only ~4 ms each.

As expected, the time per multiplication stayed constant when I varied
the number of multiplications -- with the parallel scheduling there is a
huge difference between doing 100 and doing 1000 multiplications (a
factor of four in a test I did).

If I run the sequential multiplications with three machines at the DAIMI
LAN, then I cannot measure any difference in execution time. That makes
sense too since the ping times are about 0.2 ms, and so the machines
wait very little in the sequential case.

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.3 has been released!

[Martin Geisler]

Hi everybody,

A little later for Christmas, but here it is anyway: I've just released
VIFF version 0.3 this evening. Download it here:

  Tar/GZ:  http://viff.dk/release/viff-0.3.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.3.tar.bz2
  Zip: http://viff.dk/release/viff-0.3.zip

This is the summary of changes:

  Secure communication between the players were implemented using TLS
  (Transport Layer Security, the successor to SSL). An included Makefile
  can generate the needed certificates. The network layer was completely
  reimplemented, this breaks compatibility with programs written for
  VIFF version 0.2 or earlier.

Enjoy! :-)

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] VIFF 0.2 released

[Martin Geisler]

Hello,

I have just released VIFF version 0.2! These are the new things in
this release:

  Implemented overloaded arithmetic operators, so 'w = x + y * z' now
  adds and multiplies the three shares as expected. Updated API
  documentation. Released using a Distutils setup.py script.

Please download it and play with it:

  Tar/GZ:  http://viff.dk/release/viff-0.2.tar.gz
  Tar/BZ2: http://viff.dk/release/viff-0.2.tar.bz2
  Zip: http://viff.dk/release/viff-0.2.zip

If you have any questions, then please send them to this list. I have
tried to update the documentation a lot for this release -- Epydoc
tells me that all methods and functions are documented now. Simply
having documentation is of course not a guarantee for *good*
documentation, so please complain when you find something you don't
understand...

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk