Re: [viff-devel] New project lead

2010-05-18 Thread Janus Dam Nielsen

I am happy to hear that Marcel has accepted the job as project leader.

Martin thank you for your work on VIFF, you have been doing great!


On 18/05/2010, at 00.55, Martin Geisler wrote:

 Hello everybody,
 
 When I was visiting Denmark last week, I asked Marcel if he would step
 up and be the project leader for VIFF. I'm very happy he accepted :-)
 
 I have given Marcel admin access to viff.dk and the mailinglists as well
 as the SSH accounts we use in VIFF. In other words, he should now be
 able to manage everything.
 
 I will of course stick around if you guys need anything...
 
 -- 
 Martin Geisler
 
 Fast and powerful revision control: http://mercurial.selenic.com/
 ___
 viff-devel mailing list (http://viff.dk/)
 viff-devel@viff.dk
 http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD. 

T +45 40 83 09 10
E janus.niel...@alexandra.dk
W alexandra.dk

See our blog about security at blog.sikkerhed.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] A potential bug in the Shamir Module

2010-04-21 Thread Janus Dam Nielsen
Thanks for the answers.

I had a suspicion that I was missing something. Maybe we should make the check 
that Ivan suggested. I am not sure, where it would be appropriate to do it?


On 21/04/2010, at 14.54, Ivan Damgård wrote:

 Hi folks,
 
 Just wanted to say that the bug is not really a bug, in the following sense:
 For the Shamir based protocol to be secure, the field size MUST be bigger than
 than the number of players. If this is not the case, either a player would be 
 assigned
 the point 0, or two players would be assigned the same point. In either case,
 the protocol is insecure. So that line of code is fine, provided the runtime
 checks that the field or fields you use are  large enough and refuses to
 run if not. If this check is not done, that's where the bug is instead :-)
 
 regards, Ivan
 
  
 On 21/04/2010, at 14.42, Janus Dam Nielsen wrote:
 
 Hi VIFF'ers
 
 I think I have found a bug in the Shamir code
 
 In the following function:
 def share(secret, threshold, num_players):
 assert threshold = 0 and threshold  num_players, Threshold out of 
 range
 
 coef = [secret]
 for j in range(threshold):
 # TODO: introduce a random() method in FieldElements so that
 # this wont have to be a long when we are sharing a
 # GMPIntegerFieldElement.
 coef.append(rand.randint(0, long(secret.modulus)-1))
 
 shares = []
 for i in range(1, num_players+1):
 # Instead of calculating s_i as
 #
 #   s_i = s + a_1 x_i + a_2 x_i^2 + ... + a_t x_i^t
 #
 # we avoid the exponentiations by calculating s_i by
 #
 #   s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
 #
 # This is a little faster, even for small n and t.
 cur_point = secret.field(i)
 cur_share = coef[threshold]
 # Go backwards from threshold-1 down to 0
 for j in range(threshold-1, -1, -1):
 cur_share = coef[j] + cur_share * cur_point
 
 shares.append((cur_point, cur_share))
 
 return shares
 
 
 The bug is this line:
 cur_point = secret.field(i)
 
 If the number of player exceed the size of the field then the function 
 returns the wrong id (cur_point)?
 
 Anybody see anything wrong in this patch:
 +++ b/viff/viff/passive.py
 @@ -542,10 +542,10 @@
  shares = shamir.share(field(number), threshold,
self.num_players)
  for other_id, share in shares:
 -if other_id.value == self.id:
 +if other_id == self.id:
  results.append(Share(self, share.field, share))
  else:
 -self.protocols[other_id.value].sendShare(pc, share)
 +self.protocols[other_id].sendShare(pc, share)
  else:
  results.append(self._expect_share(peer_id, field))
  
 diff --git a/viff/viff/shamir.py b/viff/viff/shamir.py
 --- a/viff/viff/shamir.py
 +++ b/viff/viff/shamir.py
 @@ -72,7 +72,7 @@
  #   s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
  #
  # This is a little faster, even for small n and t.
 -cur_point = secret.field(i)
 +cur_point = i
  cur_share = coef[threshold]
  # Go backwards from threshold-1 down to 0
  for j in range(threshold-1, -1, -1):
 
 
 
 
 Janus Dam Nielsen
 
 Research and Innovationspecialist, PhD.
 CENTRE FOR IT-SECURITY
 
 THE ALEXANDRA INSTITUTE LTD. 
 
 T +45 40 83 09 10
 E janus.niel...@alexandra.dk
 W alexandra.dk
 
 See our blog about security at blog.sikkerhed.alexandra.dk
 
 
 ___
 viff-devel mailing list (http://viff.dk/)
 viff-devel@viff.dk
 http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
 



Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD. 

T +45 40 83 09 10
E janus.niel...@alexandra.dk
W alexandra.dk

See our blog about security at blog.sikkerhed.alexandra.dk


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


[viff-devel] changeset 1365:04a696700b3f - config: Accept old config files.

2009-10-29 Thread Janus Dam Nielsen

Hi Marcel and Viff,

I would have expected you to upgrade your config files to the new  
setup instead of modifying VIFF to accept legacy config files, that  
cannot be generated any more?




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] Noisy preprocessing

2009-10-29 Thread Janus Dam Nielsen

Hi Marcel,

Occasionally I need to see which program counters are needed, so I can  
save them and use the NeededDataBenchmark strategy. This suggests that  
we should make it an option.


On 28/10/2009, at 20.01, Marcel Keller wrote:


Hi Janus,

do you still need the timing output in the update callback in
Runtime.preprocess()? It makes benchmarking the usual runtimes very
noisy because the update callback is called many times there.

Best regards,
Marcel

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




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

2009-10-29 Thread Janus Dam Nielsen



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

Great!


/rev/736ad1d97024
changeset: 1361:736ad1d97024
user:  Janus Dam Nielsen janus.niel...@alexandra.dk
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] NaCL code in VIFF (was: [viff-commits] viff: Generate_config_files:Added support NaCl implementation of...)

2009-10-29 Thread Janus Dam Nielsen




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.


Why is the code not put into VIFF? We already have too many
dependencies, to I would much prefer not to add new ones.

Dependencies are especially a problem on Windows, unless they come  
with

ready-made installers with the compiled C extensions.


I am not sure. Reading http://nacl.cace-project.eu/features.html I see  
that there are no copyright restrictions on the NaCl code.





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] Optimizing preprocessing

2009-10-22 Thread Janus Dam Nielsen


On 21/10/2009, at 20.28, Marcel Keller wrote:

Martin Geisler wrote:

Janus Dam Nielsen janus.niel...@alexandra.dk writes:

Hi Marcel,

I am not opposed to your suggestion. However I would like to point  
out

that in VIFF you compute on shares and not field elements!

Well, we've actually made the outer runtime interfaces in such a way
that add, mul, xor, etc... accept both integers, FieldElements and
Shares. The methods then wrap their input as needed -- or they *dont*
wrap it if that leads to a short cut (e.g., constant multiplication)


I agree (see also my answer).
I would still like to stress that Shares are the basic values in VIFF.  
The interface is then designed in such a way, so that we can do  
various optimizations, but computing on field elements (a particular  
representation of a share) is an optimization, which I am very happy  
that the interface allows us to do. But it is still an optimization.



Computing directly on the field elements is hacking the abstractions
of VIFF. Computation on field elements or rather the  
representation of

a Share can be useful as an optimization, however this optimization
should be confined within applications or runtimes, and should not
progress over interface boundaries as I fear you are suggesting.

I think we are in agreement: public methods on the runtimes will keep
returning Shares. Methods used internally in runtimes can return  
other

things as needed. To me it sounds like a better API to require
preprocessing functions to return a list of Deferreds:
 [D(?), D(?), ...],
instead of a Deferred list of tuples containing Deferreds :-)
I think it will simplify the interface nicely, at least for  
consumers.
Using simpler types also leads to less memory usage which has a  
positive

effect on performance, as Marcel notes. So let's go for it.


So this makes 2 votes in favour of it and 1 against it. Maybe we  
should have a meeting to discuss it. What do you think?
I can agree on this as well, as long as we don't make field elements  
canonical.




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] Commit messages

2009-10-19 Thread Janus Dam Nielsen

I like it.

On 19/10/2009, at 13.55, Martin Geisler wrote:


Hi guys,

I made a bunch of cleanup commits two days ago, and for those I used a
new style for the commit messages:

 topic: summary (max 68 characters)

 bigger description

You can see it here:

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

I think it makes it easier to quickly see if a commit is related to  
the

AES code, the Orlandi runtime, etc.

Please let me know if you like it or not and if you think we should
switch to this style from now on.

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




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] Broken build!

2009-10-09 Thread Janus Dam Nielsen

Hi everybody,


The build is broken:


That is unfortunate, thanks for notifying. I will fix it as soon as  
possible.



Janus, you added this code to benchmark.py:

 def update_args(runtime, options):
 args = {}
 if options.args != :
 for arg in options.args.split(','):
 id, value = arg.split('=')
 args[id] = long(value)
 runtime.setArgs(args)
 return runtime

Yes I did.


What is that supposed to do?
It is supposed to be a way for providing arguments for runtimes, which  
are unique for a given runtime.



We don't have a setArgs method anywhere,
If you use the --args commandline argument then it is your  
responsibility that the runtime you use has a proper setArgs method.



and we don't use the Java-like CamelCase coding style anyway.

Right, I will change that, as soon as possible.

You're not trying to parse the command line, right? (we have  
optparse for that)
I believe that the commandline arguments should be general to all  
runtimes.




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] Optimizing preprocessing

2009-10-09 Thread Janus Dam Nielsen

Hi Marcel,

I am not opposed to your suggestion. However I would like to point out  
that in VIFF you compute on shares and not field elements!. Computing  
directly on the field elements is hacking the abstractions of VIFF.
Computation on field elements or rather the representation of a Share  
can be useful as an optimization, however this optimization should be  
confined within applications or runtimes, and should not progress over  
interface boundaries as I fear you are suggesting.



On 08/10/2009, at 20.11, Marcel Keller wrote:


Dear friends of VIFF,

I have a proprosal to optimize preprocessing in VIFF, which I would  
like to put up for discussion.


Notation:
- D(x): a Deferred object whose callback function will be called  
with x

- S(x): same for a Share object
- F: a FieldElement object
- [x, ...]: a Python list
- (x, ...): a Python tuple

Current situation:
The two generate_triples() functions in the active runtimes return
n, D([(S(F), S(F), S(F)), ...]),
where n denotes the length of the list. Runtime.preprocess() puts  
one D(S(F), S(F), S(F)) per program counter in the preprocessing  
pool and uses util.deep_wait() to return a Deferred whose callback  
is called when all field elements are available.


The get_triple() functions return
D(S(F), S(F), S(F)),
either taken from the preprocessing pool, or by calling  
generate_triples() and adding an extra callback to extract the first  
triple.


My proposal:
The generate_triples() functions return
[D([F, F, F]), ...],
and Runtime.preprocess() puts one [F, F, F] per program counter in  
the preprocessing pool. There is no need for deep_wait, we can just  
use gatherResults on the Deferreds return by the generator  
functions. The generator functions can use gatherResults to get  
D([F, F, F]) from [S(F), S(F), S(F)].


The get_triple() functions return
[F, F, F], True  if there is a triple in the pool, and
[S(F), S(F), S(F)], Falseotherwise.
For the multiplication in BasicActiveRuntime it doesn't make a  
difference whether FieldElements or Shares are returned. Future  
applications which require Shares can wrap the FieldElements in  
Shares if the Boolean is True.


Benchmarks:
- 1 multiplications in parallel with active security using PRSS
 - 4% faster preprocessing
 - 5% faster online operation
 - 50 MB less memory used
- 10 AES blocks in parallel using masked exponentiation with active  
security using PRSS

 - 10% faster preprocessing
 - 10% faster online operation
 - 140 MB less memory used

Further considerations:
- I don't see any problem for replacing FieldElement with anything  
that does not contain Deferreds in any form.
- Probably, it would also be possible to leave the generator  
functions as they are and use something similar to deep_wait().  
However, I consider it as an overhead.
- One could also always wrap the FieldElements in Shares, but this  
would again be an overhead.


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




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] Homomorphic encryption

2009-08-10 Thread Janus Dam Nielsen

Hi Marc

I am back from vacation and looking forward to the next release. Have  
you tried to replace the current uses of Paillier in VIFF with your  
code?




On 03/08/2009, at 11.11, Marc Makkes wrote:


Hi Janus,

The inclusion of multiple gmp.h and time.h is indeed a sloppy. This  
will
fixed in the next release. I'm currently working on there key  
generation

and some additional speedup. I hope to release it at the end of the
week. In addition I have some for key extraction and recomputing
methods. This make key storage a little easier. If you have any other
comments/suggestions please let me know.

Kind regards,

-Marc



Wed, Jul 29, 2009 at 01:42:09PM +0200, Janus Dam Nielsen wrote:

  Hi Marc

  I have successfully compiled and run test.py and time.sh.

  The results where:

  [fagid...@fiona:~/./PyPaillier]$ ./time.sh
  Encrypting:
  10 loops, best of 3: 132 msec per loop
  Decrypting
  10 loops, best of 3: 39.2 msec per loop
  Nice indeed.

  I have some minor comments:

  In py_paillier.c you import sys/time.h twice.

  Also you include gmp.h in a lot of places, both in .c and .h  
files is

  that necessary.

  On 10/07/2009, at 10.18, Marc Makkes wrote:

  Hi Janus,
  Attached you find the tarball.
  Kind regards,
  -Marc
  PyPaillier.tar.gz

  
  Janus Dam Nielsen
  RD SCIENTIST, PhD.
  CENTRE FOR IT-SECURITY
  THE ALEXANDRA INSTITUTE LTD.
  T +45 42 22 93 56
  E [1]janus.niel...@alexandra.dk
  W alexandra.dk
  

References

  1. mailto:janus.niel...@alexandra.dk






Janus Dam Nielsen

RD SCIENTIST, 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] Homomorphic encryption

2009-07-10 Thread Janus Dam Nielsen

Hi Marc,

Thank you for your email.

I will have a look at the code, when I get back from vacation two  
weeks from now.



On 10/07/2009, at 10.18, Marc Makkes wrote:


Hi Janus,

I think that I'd have reached the stage where you can test my code,  
but

still lacks some basic checks and is still prone to timing attacks and
is basically the same viffs current implementation, with some  
additional
speedups. So consequently, it code should only be used for testing  
purposes

only.

I'm achieving the following speeds on my atom N270 ( 1.6Ghz ) testing
with key sizes of 2048 bit.

Viff code:
--
Encrypting:
10 loops, best of 3: 4.42 sec per loop
Decrypting:
10 loops, best of 3: 925 msec per loop

My code:

Encrypting:
10 loops, best of 3: 496 msec per loop
Decrypting:
10 loops, best of 3: 143 msec per loop

For encrypting its almost a 9 fold speedup and for decrypting 6.5  
times

with respect to the current implementation.

In the tar ball you find the small makefile as well as a test.py file.
It shows the basic use of all functions. If you have any comments,  
issues

or questions please let me know.

Happy testing,

-Marc




Janus Dam Nielsen

RD SCIENTIST, 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] [PATCH 02 of 12] Implemented secret sharing command

2009-06-22 Thread Janus Dam Nielsen



+s1, xi = ls[0]
+s2, rhoi1 = ls[1]
+s3, rhoi2 = ls[2]
+s4, Cx = ls[3]
+if not (s1 and s2 and s3 and s4):
+raise OrlandiException(Cannot share number,  
trying to create share, + \
+but a component did  
arrive properly.)


Same problem as above with the backslashes. Also, I think we talked
about this, but it looks like gather_shares would be better than
ShareList since you must have all four shares anyway.


I don't agree with this entirely. gather_shares ignores errors.



Janus Dam Nielsen

RD SCIENTIST, 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] [PATCH 00 of 12] Partial implementation of the Orlandi runtime.

2009-06-22 Thread Janus Dam Nielsen

Thanks for your comments. Great to get feedback on the code.


If I've understood things correctly, then this gives us an actively
secure protocol for full threshold scenarios, right?


Yes! When the protocol is completed it is indeed true.

Maybe you should publish the patches as a tree on hg.viff.dk like  
Marcel

has done -- and then let me know when you're happy with it and want me
to pull it into the main tree.

How do I get such a nice tree?

This patchbomb contains partial implementation of the Orlandi  
runtime.


Wow, cool! I've just looked through the first couple of patches and  
even

though I had some style-complaints, I think this is great!

Let me know if you have comments for the other patches.



Janus Dam Nielsen

RD SCIENTIST, 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] [Marc Makkes] Homomorphic encryption

2009-06-19 Thread Janus Dam Nielsen

Hi Marc,

  We generally use Paillier as a part of secure multiparty  
computation
  protocols, where each party has his own secret key and knows the  
public
  keys of the other players. The ciphertexts are generally  
multiplied a

  substantial number of times.


Can you give me the background of this application?
You should checkout the Paillier runtime in viff/paillier.py in VIFF.  
I think it is a classical example of what we want to do.


Also I am working on an implementation of another runtime, where  
Paillier is used. It is not yet complete but I will spend some time  
today to get it into VIFF. It should also provide you with some  
inspiration. I will let you know when it is available in the VIFF  
repository.



Also, i don't see any problems adapting for
python. Creating a python binding should easy to make. Do you have  
time

frame for when you are going to use the paillier implementation? Or is
it already running?
Our current Paillier runtime will certainly already now benefit from a  
fast implementation of Paillier. My main interest is using the  
implementation for the other runtime mentioned above. And I currently  
estimate that I am 3 to 4 weeks from completing it.





Janus Dam Nielsen

RD SCIENTIST, 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


[viff-devel] [PATCH 01 of 12] importeret rettelse orlandi_implementation.patch

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245394848 -7200
# Node ID 15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
# Parent  8ec45943c12ab91430d03a8895aabc6f64fe7a37
importeret rettelse orlandi_implementation.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
new file mode 100644
--- /dev/null
+++ b/viff/orlandi.py
@@ -0,0 +1,69 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see http://www.gnu.org/licenses/.
+
+from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
+from viff.util import rand, dprint
+
+class OrlandiException(Exception):
+pass
+
+class OrlandiShare(Share):
+A share in the Orlandi runtime.
+
+A share in the Orlandi runtime is a 3-tuple (x_{i}, rho_{i}, Cr_{i}) of:
+- A share of a number, x_{i}
+- A tuple of two random numbers, rho_{i} = (rho_{i}_{1}, rho_{i}_{2})
+- A commitment to the number and the random numbers, Cr_{i}
+
+The :class:`Runtime` operates on shares, represented by this class.
+Shares are asynchronous in the sense that they promise to attain a
+value at some point in the future.
+
+Shares overload the arithmetic operations so that ``x = a + b``
+will create a new share *x*, which will eventually contain the
+sum of *a* and *b*. Each share is associated with a
+:class:`Runtime` and the arithmetic operations simply call back to
+that runtime.
+
+
+def __init__(self, runtime, field, value=None, rho=None, commitment=None):
+Share.__init__(self, runtime, field, (value, rho, commitment))
+
+
+class OrlandiRuntime(Runtime):
+The Orlandi runtime.
+
+The runtime is used for sharing values (:meth:`secret_share` or
+:meth:`shift`) into :class:`OrlandiShare` object and opening such
+shares (:meth:`open`) again. Calculations on shares is normally
+done through overloaded arithmetic operations, but it is also
+possible to call :meth:`add`, :meth:`mul`, etc. directly if one
+prefers.
+
+Each player in the protocol uses a :class:`Runtime` object. To
+create an instance and connect it correctly with the other
+players, please use the :func:`create_runtime` function instead of
+instantiating a Runtime directly. The :func:`create_runtime`
+function will take care of setting up network connections and
+return a :class:`Deferred` which triggers with the
+:class:`Runtime` object when it is ready.
+
+
+def __init__(self, player, threshold=None, options=None):
+Initialize runtime.
+Runtime.__init__(self, player, threshold, options)
+self.threshold = self.num_players - 1
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
new file mode 100644
--- /dev/null
+++ b/viff/test/test_orlandi_runtime.py
@@ -0,0 +1,33 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see http://www.gnu.org/licenses/.
+
+from twisted.internet.defer import gatherResults
+
+from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
+from viff.runtime import Share
+from viff.orlandi import OrlandiRuntime
+
+from viff.field import FieldElement
+from viff.passive import PassiveRuntime
+
+class OrlandiBasicCommandsTest(RuntimeTestCase):
+Test for basic commands.
+
+# Number of players.
+num_players = 3
+
+runtime_class = OrlandiRuntime
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 04 of 12] Implementation of random share command

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245394852 -7200
# Node ID 1eb98ef76446e9ef06d8d94e31748fe5cfd2ba82
# Parent  29c28d1a8e5f5647fe97d7b01f5924f3ef006301
Implementation of random share command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -270,6 +270,52 @@
 if self.id in receivers:
 return result
 
+@increment_pc
+def random_share(self, field):
+Generate a random share in the field, field.
+
+To generate a share of a random element r in Z_{p}, party P_{i} 
+chooses at random r_{i}, rho_{r,i} in Z_{p} x (Z_{p})^2 and
+broadcast C_{r}^{i} = Com_{ck}(r_{i}, rho_{r, i}).
+Every party computes C_{r} = PRODUCT_{i=1}^{n} C_{r}^{i} = Com_{ck}(r, 
rho_{r}),
+where r_{i} = SUM_{i=1}^{n} r_{i} and rho_{r} = SUM_{i=1}^{n} 
rho_{r,i}.
+
+Party P_{i} sets [r]_{i} = (r_{i}, rho_{r,i}, C_{r}).
+
+
+# P_{i} chooses at random r_{i}, rho_{r,i} in Z_{p} x (Z_{p})^2
+ri = field(rand.randint(0, field.modulus - 1)) 
+rhoi1 = field(rand.randint(0, field.modulus - 1))
+rhoi2 = field(rand.randint(0, field.modulus - 1))
+# compute C_{r}^{i} = Com_{ck}(r_{i}, rho_{r, i}).
+Cri = self._Com(ri, (rhoi1, rhoi2))
+# Broadcast C_{r}^{i}.
+shares = []
+for peer_id in self.players:
+if peer_id == self.id:
+# Broadcast C_{r}^{i}
+d = Share(self, field, Cri)
+else:
+# Recieve C_{r}^{i}
+pc = tuple(self.program_counter)
+self.protocols[peer_id].sendShare(pc, Cri)
+d = self._expect_share(peer_id, field)
+shares.append(d)
+
+def compute_commitment(ls):
+Cr = field(1)
+for s, v in ls:
+Cr *= v
+return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
+
+sls = ShareList(shares)
+sls.addCallbacks(compute_commitment, self.error_handler)
+
+# do actual communication
+self.activate_reactor()
+
+return sls
+
 def error_handler(self, ex):
 print Error: , ex
 return ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -65,3 +65,16 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_random_share(self, runtime):
+Test creation of a random shared number.
+
+def check(v):
+self.assertEquals(True, True)
+
+x = runtime.random_share(self.Zp)
+d = runtime.open(x)
+d.addCallback(check)
+return d
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 07 of 12] Implementation of input and shift commands

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245394940 -7200
# Node ID 07a8329e75322d482dae15186422dd75e9ddb653
# Parent  4c4228af583fc965fb0722c5b051ffa213152f62
Implementation of input and shift commands.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -43,6 +43,12 @@
 def __init__(self, runtime, field, value=None, rho=None, commitment=None):
 Share.__init__(self, runtime, field, (value, rho, commitment))
 
+def input(self, inputters, field, number=None, threshold=None):
+Input *number* to the computation.
+
+The input is shared using the :meth:`shift` method.
+
+return self.shift(inputters, field, number)
 
 class OrlandiRuntime(Runtime):
 The Orlandi runtime.
@@ -378,6 +384,64 @@
 result.addCallbacks(compute_subs, self.error_handler)
 return result
 
+@increment_pc
+def shift(self, inputters, field, number):
+Shift of a share.
+
+Useful for input.
+
+Communication cost: ???.
+
+Assume the parties are given a random share [r] by a trusted dealer. 
+Then we denote the following protocol but [x] = Shift(P_{i}, x, [r]).
+
+1) r = OpenTo(P_{i}, [r]
+
+2) P_{i} broadcasts Delta = r - x
+
+3) [x] = [r] - Delta
+
+
+# TODO: Communitcation costs?
+results = []
+for peer_id in inputters:
+# Assume the parties are given a random share [r] by a trusted 
dealer.
+share_r = self.random_share(field)
+# 1) r = OpenTo(P_{i}, [r]
+open_r = self.open(share_r, [peer_id])
+if peer_id == self.id:
+# I am an inputter, send delta
+pc = tuple(self.program_counter)
+def f(r, share_r, pc):
+my_delta = None
+# 2) P_{i} broadcasts Delta = r - x
+for other_id in self.players:
+delta = r - number
+if not (other_id == self.id):
+self.protocols[other_id].sendShare(pc, delta)
+else:
+# 3) [x] = [r] - Delta
+my_delta = self.sub(share_r, delta)
+return my_delta
+open_r.addCallback(f, share_r, pc)
+open_r.addErrback(self.error_handler)
+results.append(open_r)
+else:
+# I am not an inputter, wait for a delta
+d = self._expect_share(peer_id, field)
+def f(delta, share_r):
+# 3) [x] = [r] - Delta
+return self.sub(share_r, delta)
+d.addCallback(f, share_r)
+results.append(d)
+
+# do actual communication
+self.activate_reactor()
+
+if len(results) == 1:
+ return results[0]
+return results   
+
 def _additive_constant(self, zero, field_element):
 Greate an additive constant.
 
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -15,7 +15,7 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see http://www.gnu.org/licenses/.
 
-from twisted.internet.defer import gatherResults
+from twisted.internet.defer import gatherResults, DeferredList
 
 from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
 from viff.runtime import Share
@@ -218,3 +218,37 @@
 return d
 
 
+class OrlandiAdvancedCommandsTest(RuntimeTestCase):
+Test for advanced commands.
+
+# Number of players.
+num_players = 3
+ 
+runtime_class = OrlandiRuntime
+ 
+@protocol
+def test_shift(self, runtime):
+Test addition of the shift command.
+
+def check(v):
+self.assertEquals(v, 42)
+ 
+x = runtime.shift([2], self.Zp, 42)
+d = runtime.open(x)
+d.addCallback(check)
+return d
+
+@protocol
+def test_shift_two_inputters(self, runtime):
+Test addition of the shift command.
+
+def check(v):
+self.assertEquals(v, 42)
+ 
+x, y = runtime.shift([1,3], self.Zp, 42)
+d1 = runtime.open(x)
+d1.addCallback(check)
+d2 = runtime.open(y)
+d2.addCallback(check)
+return DeferredList([d1, d2])
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 05 of 12] Implementation of addition command

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245394853 -7200
# Node ID 85ae7883768d8367baf57cf3b6647707cb1d9b1d
# Parent  1eb98ef76446e9ef06d8d94e31748fe5cfd2ba82
Implementation of addition command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -316,6 +316,66 @@
 
 return sls
 
+def add(self, share_a, share_b):
+Addition of shares.
+
+Communication cost: none.
+
+Each party P_{i} computes:
+[z]_{i} = [x]_{i} + [y]_{i}
+= (x_{i} + y_{i} mod p, rho_{x,i} + rho_{y,i} mod p, C_{x} * 
C_{y}).
+
+
+def is_share(s, field):
+if not isinstance(s, Share):
+(v, rhov, Cv) = self._additive_constant(field(0), s)
+return OrlandiShare(self, field, v, rhov, Cv)
+return s
+
+# Either share_a or share_b must have an attribute called field. 
+field = getattr(share_a, field, getattr(share_b, field, None))
+
+share_a = is_share(share_a, field)
+share_b = is_share(share_b, field)
+
+# Add rho_{x,i} and rho_{y,i} and compute the commitment.
+def compute_sums((x, y)):
+(zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
+return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
+
+result = gather_shares([share_a, share_b])
+result.addCallbacks(compute_sums, self.error_handler)
+return result
+
+def _additive_constant(self, zero, field_element):
+Greate an additive constant.
+
+Any additive constant can be interpreted as:
+[c]_{1} = (c, 0, Com_{ck}(c,0)) and
+[c]_{i} = (0, 0, Com_{ck}(c,0)) for i != 1.
+
+v = zero
+if self.id == 1:
+v = field_element
+return (v, (zero, zero), self._Com(field_element, (zero, zero)))
+
+def _plus(self, x, y):
+Addition of share-tuples x and y.
+
+Each party P_{i} computes:
+[x]_{i} = (x_{i}, rho_{x,i}, C_{x})
+[y]_{i} = (y_{i}, rho_{y,i}, C_{y})
+[z]_{i} = [x]_{i} + [y]_{i}
+= (x_{i} + y_{i} mod p, rho_{x,i} + rho_{y,i} mod p, C_{x} * 
C_{y}).
+
+(xi, (rhoxi1, rhoxi2), Cx) = x
+(yi, (rhoyi1, rhoyi2), Cy) = y
+zi = xi + yi
+rhozi1 = rhoxi1 + rhoyi1
+rhozi2 = rhoxi2 + rhoyi2
+Cz = Cx * Cy
+return (zi, (rhozi1, rhozi2), Cz)
+
 def error_handler(self, ex):
 print Error: , ex
 return ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -77,4 +77,75 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_sum(self, runtime):
+Test addition of two numbers.
 
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = runtime.add(x2, y2)
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sum_plus(self, runtime):
+Test addition of two numbers.
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = x2 + y2
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sum_constant(self, runtime):
+Test addition of two numbers.
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+z2 = x2 + y1
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 06 of 12] Implementation of subtraction command

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245394917 -7200
# Node ID 4c4228af583fc965fb0722c5b051ffa213152f62
# Parent  85ae7883768d8367baf57cf3b6647707cb1d9b1d
Implementation of subtraction command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -347,6 +347,37 @@
 result.addCallbacks(compute_sums, self.error_handler)
 return result
 
+def sub(self, share_a, share_b):
+Subtraction of shares.
+
+Communication cost: none.
+
+Each party P_{i} computes:
+[z]_{i} = [x]_{i} - [y]_{i}
+= (x_{i} - y_{i} mod p, rho_{x,i} - rho_{y,i} mod p, C_{x} * 
C_{y}).
+
+
+def is_share(s, field):
+if not isinstance(s, Share):
+(v, rhov, Cv) = self._additive_constant(field(0), s)
+return OrlandiShare(self, field, v, rhov, Cv)
+return s
+
+# Either share_a or share_b must have an attribute called field. 
+field = getattr(share_a, field, getattr(share_b, field, None))
+
+share_a = is_share(share_a, field)
+share_b = is_share(share_b, field)
+
+# Subtract xi and yi, rhoxi and rhoyi, and compute the commitment
+def compute_subs((x, y)):
+zi, (rhozi1, rhozi2), Cz = self._minus(x, y)
+return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
+
+result = gather_shares([share_a, share_b])
+result.addCallbacks(compute_subs, self.error_handler)
+return result
+
 def _additive_constant(self, zero, field_element):
 Greate an additive constant.
 
@@ -376,6 +407,23 @@
 Cz = Cx * Cy
 return (zi, (rhozi1, rhozi2), Cz)
 
+def _minus(self, x, y):
+Subtraction of share-tuples x and y.
+
+Each party P_{i} computes:
+[x]_{i} = (x_{i}, rho_{x,i}, C_{x})
+[y]_{i} = (y_{i}, rho_{y,i}, C_{y})
+[z]_{i} = [x]_{i} - [y]_{i}
+= (x_{i} - y_{i} mod p, rho_{x,i} - rho_{y,i} mod p, C_{x} * 
C_{y}).
+
+xi, (rhoxi1, rhoxi2), Cx = x
+yi, (rhoyi1, rhoyi2), Cy = y
+zi = xi - yi
+rhozi1 = rhoxi1 - rhoyi1
+rhozi2 = rhoxi2 - rhoyi2
+Cz = Cx * Cy
+return (zi, (rhozi1, rhozi2), Cz)
+
 def error_handler(self, ex):
 print Error: , ex
 return ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -147,5 +147,74 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_sub(self, runtime):
+Test subtration of two numbers.
 
+x1 = 42
+y1 = 7
 
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = runtime.add(x2, y2)
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sub_minus(self, runtime):
+Test subtration of two numbers.
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 - y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = x2 - y2
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sub_constant(self, runtime):
+Test subtration of two numbers.
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 - y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+z2 = x2 - y1
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 12 of 12] importeret rettelse triple_test.patch

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245395107 -7200
# Node ID 57f6d76d82e375b77293bcc6d54eeb6242686079
# Parent  4c46e8eeb719682da1a91b7ad96e7e902363e204
importeret rettelse triple_test.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -932,7 +932,39 @@
 self.schedule_callback(result, step2ab, ai, (r1, r2))
 result.addErrback(self.error_handler)
 return result
-
+
+def triple_test(self, field):
+triple1 = self.triple_gen(field)
+triple2 = self.triple_gen(field)
+r = self.open(self.random_share(field))
+
+def check((v, oa, ob, oc, ox, oy, oz), a, b, c):
+if v is 0:
+return None
+return (a, b, c)
+
+def compute_value(((a, b, c), (x, y, z), r)):
+oa = self.open(a)
+ob = self.open(b)
+oc = self.open(c)
+ox = self.open(x)
+oy = self.open(y)
+oz = self.open(z)
+l = self._cmul(r, x, field)
+m = self._cmul(r, y, field)
+n = self._cmul(r*r, z, field)
+d = c - self._basic_multiplication(a, b, l, m, n)
+r = gather_shares([d, oa, ob, oc, ox, oy, oz])
+r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c))
+return r
+
+result = gatherResults([triple1, triple2, r])
+result.addCallbacks(compute_value, self.error_handler)
+
+# do actual communication
+self.activate_reactor()
+
+return result
 
 def error_handler(self, ex):
 print Error: , ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -494,4 +494,21 @@
 d = gatherResults([t1, t2])
 d.addCallbacks(open, runtime.error_handler)
 return d
-
+
+@protocol
+def test_tripleTest(self, runtime):
+Test the triple_test command.
+
+def check((a, b, c)):
+self.assertEquals(c, a * b)
+
+def open((a, b, c)):
+d1 = runtime.open(a)
+d2 = runtime.open(b)
+d3 = runtime.open(c)
+d = gatherResults([d1, d2, d3])
+d.addCallback(check)
+return d
+d = runtime.triple_test(self.Zp)
+d.addCallbacks(open, runtime.error_handler)
+return d
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


[viff-devel] [PATCH 09 of 12] Implementation of the leak tolerant multiplication command

2009-06-19 Thread Janus Dam Nielsen
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# Date 1245395070 -7200
# Node ID cd787f04de1f3be2e7c969e963ed7bcd94f81305
# Parent  a07740da4582869d11ead0f56ae055965aa2b4b0
Implementation of the leak tolerant multiplication command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -75,6 +75,23 @@
 Initialize runtime.
 Runtime.__init__(self, player, threshold, options)
 self.threshold = self.num_players - 1
+self.d = 3
+self.delta = self.compute_delta(self.d)
+
+def compute_delta(self, d):
+def product(j):
+pt = 1
+pn = 1
+for k in xrange(1, 2 * d + 2):
+if k != j:
+pt *= k
+pn *= k - j
+return pt // pn
+
+delta = []
+for j in xrange(1, 2 * self.d + 2):
+delta.append(product(j))
+return delta
 
 def _Com(self, x, rho):
 return x + rho[0] + rho[1]
@@ -595,6 +612,107 @@
 
 return result
 
+def sum_poly(self, j, ls):
+x = 0
+rho1 = 0
+rho2 = 0
+Cx = 0
+exp = j
+for (fj, (rhoj1, rhoj2), Cfj) in ls:
+x += fj * exp
+rho1 += rhoj1 * exp
+rho2 += rhoj2 * exp
+Cx += Cfj * exp
+exp *= j
+return x, (rho1, rho2), Cx
+
+@increment_pc
+def leak_tolerant_mul(self, share_x, share_y):
+Leak tolerant multiplication of shares.
+
+Communication cost: ???.
+
+Assuming a set of multiplicative triples:
+M = {([a_{i}], [b_{i}], [c_{i}])} for 1 = i = 2d + 1.
+
+1) for i = 1, ..., d do [f_{i}] = rand(), [g_{i}] = rand()
+
+2) for j = 1, ..., 2d+1 do
+   [F_{j}] = [x] + SUM_{i=1}^{d} [f_{i}]*j^{i} 
+   and
+   [G_{j}] = [y] + SUM_{i=1}^{d} [g_{i}]*j^{i} 
+
+3) for j = 1, ..., 2d+1 do [H_{j}] = Mul([F_{j}], [G_{j}], [a_{j}], 
[b_{j}], [c_{j}])
+
+4) compute [H_{0}] = SUM_{j=1}^{2d+1} delta_{j}[H_{j}] 
+
+5) output [z] = [H_{0}]
+
+delta_{j} = PRODUCT_{k=1, k!=j}^{2d+1} k/(k-j).
+
+assert isinstance(share_x, Share) or isinstance(share_y, Share), \
+At least one of share_x and share_y must be a Share.
+
+field = getattr(share_x, field, getattr(share_y, field, None))
+n = field(0)
+
+cmul_result = self._cmul(share_x, share_y, field)
+if cmul_result is  not None:
+return cmul_result
+
+# 1) for i = 1, ..., d do [f_{i}] = rand(), [g_{i}] = rand()
+f = []
+g = []
+for x in xrange(self.d):
+f.append(self.random_share(field))
+g.append(self.random_share(field))
+
+def compute_polynomials(((x, y), f, g)):
+# print x:, x
+# print y:, y
+# print f:, f
+# print g:, g
+# 2) for j = 1, ..., 2d+1 do
+# [F_{j}] = [x] + SUM_{i=1}^{d} [f_{i}]*j^{i} 
+# and
+# [G_{j}] = [y] + SUM_{i=1}^{d} [g_{i}]*j^{i} 
+h0i, rhoh0, Ch0 = self._additive_constant(field(0), n)
+H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0)
+xi, (rhoxi1, rhoxi2), Cx = x
+yi, (rhoyi1, rhoyi2), Cy = y
+
+for j in xrange(1, 2*self.d + 2):
+# SUM_{i=1}^{d} [f_{i}]*j^{i} 
+vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f)
+# SUM_{i=1}^{d} [g_{i}]*j^{i} 
+wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g)
+# [F_{j}] = [x] + SUM_{i=1}^{d} [f_{i}]*j^{i} 
+# [G_{j}] = [y] + SUM_{i=1}^{d} [g_{i}]*j^{i} 
+Fji = xi + vi
+Gji = yi + wi
+Fj = OrlandiShare(self, field, Fji, (rhovi1, rhovi2), Cv)
+Gj = OrlandiShare(self, field, Gji, (rhowi1, rhowi2), Cw)
+
+a, b, c = self._get_triple(field)
+
+# [H_{j}] = Mul([F_{j}], [G_{j}], [a_{j}], [b_{j}], [c_{j}])
+Hj = self._basic_multiplication(Fj, Gj, a, b, c)
+dj = self._cmul(self.delta[j - 1], Hj, field)
+H0 = H0 + dj
+# 5) output [z] = [H_{0}]
+return H0
+
+result1 = gather_shares([share_x, share_y])
+result2 = gather_shares(f)
+result3 = gather_shares(g)
+result = gather_shares([result1, result2, result3])
+result.addCallbacks(compute_polynomials, self.error_handler)
+
+# do actual communication
+self.activate_reactor()
+
+return result
+
 def error_handler(self, ex):
 print Error: , ex
 return ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -375,3 +375,70 @@
 z2 = runtime._cmul(y2, x2, self.Zp

Re: [viff-devel] [Marc Makkes] Homomorphic encryption

2009-06-18 Thread Janus Dam Nielsen

Hi Marc,


My name is Marc X. Makkes and i'm the student who is implementing the
homomorphic encryption scheme for for NaCL project.
Great to hear from you, I will be your main contact, because I am  
probably the VIFF user who will be needing a fast homomorphic  
implementation the soonest.


I guess that the actual scheme you are implementing is the Paillier  
encryption scheme?


Tanja urged me to contact you for some detail regarding the  
implementation and if i

understand correctly your the one that is going to use this scheme for
certain applications. Can you tell me a little bit the applications?
We generally use Paillier as a part of secure multiparty computation  
protocols, where each party has his own secret key and knows the  
public keys of the other players. The ciphertexts are generally  
multiplied a substantial number of times.



In addition i've received the whish list. But it seems to me that  
there

is missing a key setup/generation function. Can you maybe comment on
that?
We generally would like an implementation which is similar to the one  
already in VIFF in terms of API and functionality. I am not sure I  
understand what you mean by missing a key setup/generation function,  
currently in Python there is a function which generates keys. If there  
are alternatives, then what are they and what would you suggest?



Currently i've have made a ''basic'' c implementation, which is
equivalent to your and my own python implementation. In the next few
day's i hope to implement the subgroup variant as well as doing the  
CRT

speedup for decryption.

Great, I hope it will outperform any other implementation ever made :)

Having Python bindings for the c implementation is also of large value  
to us.




Janus Dam Nielsen

RD SCIENTIST, 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] Confusing behaviour?

2009-03-23 Thread Janus Dam Nielsen

I have experienced the same problem/issue.

--
Janus Dam Nielsen

RD Scientist
Alexandra Instituttet
janus.niel...@alexandra.dk





On 23/03/2009, at 15.42, Thomas P Jakobsen wrote:


Hi all,

When I execute the attached VIFF protocol on three servers I would
expect all three to ask me to press enter. When all three servers have
done that, I would expect the computation of c to start and that the
servers will eventually finish.

I've run the protocol several times on Linux and Windows. What  
happens is this:


Sometimes it works out as expected, but at other times only two of the
servers will ask the user to press enter. In some cases, the third
server will ask its user to press enter as soon as one of the two
other servers presses enter. At other times, the third server will
first wake up and ask its user to press enter when both of the two
first servers have pressed enter.

I find this behaviour confusing (..twisted?) and wonder whether it is
a bug or a feature? If it's a bug, could it be related to the issue
discussed in the thread Mystery of the quadratic running time
solved?. I must admit that I haven't followed that thread in
detail...

By the way, the same thing seem sto happen if the protocol, insted of
asking the user to press enter, does some local computations like
quering a database, sleeping, computing primes or the like. Sometimes,
one of the servers will sit still until one or both of the other
servers have finished their local jobs. This was how I initially
stumbled across the problem.

Best regards,
Thomas
example.py___
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] [issue80] Broadcast

2009-03-10 Thread Janus Dam Nielsen

New submission from Janus Dam Nielsen janus.niel...@alexandra.dk:

I would like to see a broadcast method in the Runtime class. The 
purpose of the broadcast method should be to distribute a public value 
among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from 
standard in, and it is a different value for each party. We want to 
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset 
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker trac...@viff.dk
http://tracker.viff.dk/issue80

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


Re: [viff-devel] [issue80] Broadcast

2009-03-10 Thread Janus Dam Nielsen
In the simple case I want to shout out a number to everybody, even  
somebody who is eavesdropping.


--
Janus


Den 10/03/2009 kl. 12.23 skrev Ivan Bjerre Damgård:

It can definitely be useful to have a broadcast method, for  
instance to complete the implementation of the asynchronous  
maliciously secure protocol, we will need broadcast.


But one needs to be careful about what kind of security we want.  
There is a whole jungle of protocols, depending on whether it is  
unconditional or computational security, synchronous or  
asynchronous network, and what number of players you assume can be  
corrupt. I think a protocol of Bracha has in fact already been  
implemented in VIFF


regards, Ivan

Quoting Janus Dam Nielsen trac...@viff.dk:



New submission from Janus Dam Nielsen janus.niel...@alexandra.dk:

I would like to see a broadcast method in the Runtime class. The
purpose of the broadcast method should be to distribute a public  
value

among all parties (or some subset of parties).

A case: All parties in a computation needs to read a value from
standard in, and it is a different value for each party. We want to
tell the value to everybody else.

An example use could be like the input method:
a,b,c = runtime.broadcast([1,2,3], value)

Similarly, broadcast can be used in a conditional if only some subset
of parties wants to distribute a value.

--
assignedto: mg
messages: 310
nosy: jdn, mas, mg
status: chatting
title: Broadcast
type: wish


VIFF Issue Tracker trac...@viff.dk
http://tracker.viff.dk/issue80

___
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


[viff-devel] [issue79] Specify keysize for generate-config-file.py

2009-03-09 Thread Janus Dam Nielsen

New submission from Janus Dam Nielsen janus.niel...@alexandra.dk:

Add a parameter to specify the keysize in the script generate-config-
file.py

--
assignedto: jdn
keyword: simple
messages: 308
nosy: jdn, mg
status: in-progress
title: Specify keysize for generate-config-file.py
type: wish


VIFF Issue Tracker trac...@viff.dk
http://tracker.viff.dk/issue79

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


[viff-devel] Speed of ElGamal encryption

2008-09-19 Thread Janus Dam Nielsen

Hi,

I have made some tests of ElGamal encryption in Python (with some  
nontrivial amount of help from Martin thanks)


First test was in bare Python, here an encryption took

 time for 1 enc time for 4*10^6 enc
Python  : 0,002980 sec :  approx. 3 hours and 20 min
GMPY   : 0,000535 sec :  35 min and 40 sec

All the timing is made on my elderly office machine.

Another possiblity I have not tested yet is to use the Dan Bernstein  
implementation of encryption based on elliptic curves. I guess that  
we can get some more speed from there.


However I think that 35 min is worth waiting for and that we can get  
further speed up using a better implementation, and using state-of  
the art machines.


--
Janus


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


Re: [viff-devel] SMCL security notion

2008-07-25 Thread Janus Dam Nielsen



In the paper on page two, lower left, we write that each server
party execute identical copies of the server program inn lock-step.
Based on this assumption it is reasonable to consider the server as
having a single well-defined state. However in Viff this is no
longer true due to parallelism. But it would be very nice if we
could consider the server as having a single well-defined state.


I don't like this since it introduces a wide gap between the model and
the real world and I believe such a gap makes it easier to come up
with inefficient solutions.

Then we have to come up with a better description...

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


Re: [viff-devel] SMCL compiler status

2008-07-22 Thread Janus Dam Nielsen



Hi again,

While reading the progress repot I also looked at the code of the
compiler to get a feeling for what it can and cannot do.

Please correct me if I'm wrong, but it seems to go through a number of
standard phases not related to cryptography. Then there are these
three phases:

Yes there is a bunch of standard phases.


* Checking of annotations for open() calls -- I think this is part of
  the analysis in DefiniteAssignment.java.
The checking is done in AnnotationAnalysis.java, which is part of the  
DefiniteAssignment phase.
The code in AnnotationAnalysis.java is currently commented out, it  
needs to be upgraded to changes in the analysis framework used.



* Hoistability check which looks for I/O or assignments to public
  variables in the branches of if-statements.

Yes


* Conditional expansion where if-statements are turned into
  conditional assignments. Loops are also detected in the branches.


Yes



I found no support for

* Making things run in parallel (the word parallel does not occur at
  all in the source code).
There is no concept of parallelism in SMCL programs. The fact that  
the computation is distributed is abstracted away.



* Bounds checking when the protocol needs inputs to be smaller than
  the field size (needed in comparisons and new Paillier two-player
  runtime).
I haven't been aware of this being an issue. We need to handle this  
somehow.



* Counting multiplications and other stuff for preprocessing.
NYI. The multiplication optimization I implemented last week haven't  
been committet yet. It needs more integration with the rest of the  
compiler.


--
Janus

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


Re: [viff-devel] SMCL security notion

2008-07-22 Thread Janus Dam Nielsen

Hi Martin,


I am confused about the notion of security via adversary traces
presented in those papers. It is described via two properties:

* Identity Property: a public state P can only lead to one other
  public state P', regardless of the secret state.

* Commutative Property: computing on secrets leads to the same state
  as opening everything and computing on open values.

I think you write that this is a new idea -- have you then looked into
how this relates to the more standard notion of Ideal World/Real World
simulation arguments in the UC framework?
Yes this is a new formulation of the security guaranties in the  
programming language community. I have not compared this to UC, it  
would be nice to do so.



It is not clear to me how you can describe the server as one entity
with one state when it is really a set of computers -- are you
thinking of the product state for S1, S2, and S3? Is that state even
well-defined in an asynchronous network setting, or do you assume that
the coordinator synchronizes the network?
In the paper on page two, lower left, we write that each server party  
execute identical copies of the server program inn lock-step. Based  
on this assumption it is reasonable to consider the server as having  
a single well-defined state. However in Viff this is no longer true  
due to parallelism. But it would be very nice if we could consider  
the server as having a single well-defined state.



You say that the adversary can observe the trace which shows how the
configuration change on the server, but with secret values masked out.
Shouldn't the adversary be able to see the secret values of the server
parties he has corrupted?

A server is not a client, so a server only has shares of secret values.
We assume that the adversary at most corrupt a number of servers upto  
the threshold. If he corrupts more, then all our security guaranties  
are off.
So assuming that the adversary does not have access to the secret  
values is not a problem.




Oh, and using the term semantic security in Section 4.5 is
unfortunate since it already has a standard definition in
cryptography:

  http://en.wikipedia.org/wiki/Semantic_security


Thanks

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


Re: [viff-devel] Vedr.: Small VIFF language parser

2008-07-17 Thread Janus Dam Nielsen
If there are any other ideas for optimizations you would like to see  
in a compiler for Viff then now is the time to come forward.


--
Janus


Den 15/07/2008 kl. 16.49 skrev Martin Geisler:


Janus Dam Nielsen [EMAIL PROTECTED] writes:


Hi again,

Heres the fruit of half a days work :)

Analyzing the expression:
sint n = (a * y + (1 - a) * x);

Yields the following results:

Final result:
((a * y )+ ((1 - a )* x )) cost: 30
(((a * y )+ x )- (x * a )) cost: 30
(((a * y )+ x )- (a * x )) cost: 30
(((a * y )- (a * x ))+ x ) cost: 30
(((y * a )+ x )- (a * x )) cost: 30
(((y * a )+ x )- (x * a )) cost: 30
((a * y )+ (x - (x * a ))) cost: 30
(((y * a )- (a * x ))+ x ) cost: 30
(((y * a )- (x * a ))+ x ) cost: 30
(((a * y )- (x * a ))+ x ) cost: 30
((a * (y - x ))+ x ) cost: 20

And lo and behold the last line reveals that the expression
a * (y - x )+ x
has the lowest cost.


That is very cool! :-)


From the output above it seems that you have taught your analyzer

about the distributive law, that + and * are commutative.

What about a - a == 0, and that 0 * a == 0? I don't know if those
rules will help -- they might just blow up the search space... :-)

--
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] Vedr.: Small VIFF language parser

2008-07-17 Thread Janus Dam Nielsen



I have another thing to consider: the height of the resulting
arithmetic circuit.

Good idea.



If there are several possibilities for expressing the formula and each
has the same number of multiplications, then one should go for the one
with the least height: so (a*b) * (c*d) instead of ((a*b) * c) * d.


This is more like an ordering problem. We want (a*b) and (c*d) to  
happen before the multiplication of the result so they can occur in  
parallel and we don't wast clock cycles.




You might even want to prefer a formula with more multiplications if
it lowers the height of the tree -- but I cannot come up with a good
example of such a situation :-)

Given the huge execution time for an execution, I would expect this  
to be the case only in cases where you have extremely large left or  
right hanging expressions where the choice is only between one  
multiplication more or less.
If the choice comes to removing two multiplication then I think it is  
preferable to not removing them.


--
Janus


Den 17/07/2008 kl. 14.08 skrev Martin Geisler:


Janus Dam Nielsen [EMAIL PROTECTED] writes:


If there are any other ideas for optimizations you would like to see
in a compiler for VIFF then now is the time to come forward.


I have another thing to consider: the height of the resulting
arithmetic circuit.

If there are several possibilities for expressing the formula and each
has the same number of multiplications, then one should go for the one
with the least height: so (a*b) * (c*d) instead of ((a*b) * c) * d.

You might even want to prefer a formula with more multiplications if
it lowers the height of the tree -- but I cannot come up with a good
example of such a situation :-)

--
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] Small VIFF language parser

2008-07-15 Thread Janus Dam Nielsen


--
Janus


Den 15/07/2008 kl. 12.16 skrev Martin Geisler:


Janus Dam Nielsen [EMAIL PROTECTED] writes:


Den 11/07/2008 kl. 22.02 skrev Martin Geisler:


Right, good point! We should do that. Maybe a smart compiler could
do the necessary deductions automatically? [...]


I am not aware of any of-the-shelf technique for this, but it would
be a fun problem to solve.
Define a cost function:
Gamma(+) = 5
Gamma(-) = 5
Gamma(*) = 10

I have no clue if these costs reflect the relative cost among the
operators, please correct me.


I have never really measured the speed of additions/subtractions, but
my guess is that they are a 100 or maybe a 1000 times faster than
multiplications.

And comparisons are about 500 times slower than multiplications.


Given the size of an expressions that naturally appear in programs I
think it is reasonable efficient to compute all permutations of the
expression under the distributive law and then pick any one of those
with the lowest cost under the Gamma cost function.

This is worstcase exponential, but given the size of expressions
programmers are inclined to write in a program, then I don't think
it will be a problem.


For single expression I guess not, but it should also work for chains
of expressions (when possible):

  x = a * b
  y = a * c
  z = x + y

If x and y are not used, then z can be computed as a * (b + c). Was
that already part of what you planned?
Yes I have been thinking about this as well, but I currently this as  
an extension we can pursue when we know how to deal with a single  
expression.
Even in such cases as above I guess that the size of expressions will  
be reasonable small. Lets see when we get some tests.




[...]

If you are working in a language where you can redefine the
semantics of operators like * in Python you have to take that into
account as well, but it does not need to change the analysis
performed by the interpreter.


Right, but I don't think we will want to give people that power?
No, you mentioned manipulating the Python AST and so I just wanted to  
let you know that this can also be done in Python.



Depending on how much the SMCL compiler can do, it would be stupid
to throw it away. But on the other hand we might be able to
reimplement things quickly in Python from which we can work
directly with the Python AST. I guess we need more comments from
the Janus and Michael.


You should see my progress report to see what the SMCL language and
compiler can do for you.


I've printed the report and I hope I will have read it soon!

Nice, at least one more gets read my report :)


Have you ever put up the source (and repository) somewhere? The
nightly build linked from

  http://www.daimi.au.dk/~fagidiot/simap/

seems broken (as does many of the links on the blog...).

They haven't been maintained for a year now...

I have an svn repository at daimi
  /users/fagidiot/.SVNSMCL

I believe you can read from there.



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


[viff-devel] Vedr.: Small VIFF language parser

2008-07-15 Thread Janus Dam Nielsen


Hi again,

Heres the fruit of half a days work :)

Analyzing the expression:
sint n = (a * y + (1 - a) * x);

Yields the following results:

Final result:
((a * y )+ ((1 - a )* x )) cost: 30
(((a * y )+ x )- (x * a )) cost: 30
(((a * y )+ x )- (a * x )) cost: 30
(((a * y )- (a * x ))+ x ) cost: 30
(((y * a )+ x )- (a * x )) cost: 30
(((y * a )+ x )- (x * a )) cost: 30
((a * y )+ (x - (x * a ))) cost: 30
(((y * a )- (a * x ))+ x ) cost: 30
(((y * a )- (x * a ))+ x ) cost: 30
(((a * y )- (x * a ))+ x ) cost: 30
((a * (y - x ))+ x ) cost: 20

And lo and behold the last line reveals that the expression
a * (y - x )+ x
has the lowest cost. Again I just used the 10,5,5 costs for multiplication,
addition, and subtraction (they seem to enough for the moment).

These 11 expressions are not all the possible expressions one could generate, so
I don't claim that my implementation is complete but I hope it is sound.

Later...

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


Re: [viff-devel] Small VIFF language parser

2008-07-14 Thread Janus Dam Nielsen

1) Rather than

   x = (a * (y + (1 - a) * x)

you want

   x = (a * (y - x) + x)

so you shave off a superfluous mult for each assignment.


Right, good point! We should do that. Maybe a smart compiler could do
the necessary deductions automatically? So it would go from

  x = a * y + (1 - a) * x

to

  x = a * y + x - a * x

to

  x = a * (y - x) + x

via knowledge about the distrubutive law and knowledge about the cost
of addition/subtraction versus multiplication. I guess this is where
the compiler guys get into the picture -- I'm Cc'in Janus, Michael  
and

Sigurd in case they have any input on this.
I am not aware of any of-the-shelf technique for this, but it would  
be a fun problem to solve.

Define a cost function:
Gamma(+) = 5
Gamma(-) = 5
Gamma(*) = 10
I have no clue if these costs reflect the relative cost among the  
operators, please correct me.


Given the size of an expressions that naturally appear in programs  
I think it is reasonable efficient to compute all permutations of  
the expression under the distributive law and then pick any one of  
those with the lowest cost under the Gamma cost function.


This is worstcase exponential, but given the size of expressions  
programmers are inclined to write in a program, then I don't think  
it will be a problem.


We need to combine this with elimination of common subexpressions.



I have made a limited(yet) implementation of this in SMCL which can  
rewrite


  x = a * y + (1 - a) * x
to
  x = a * y + x - a * x

Rewriting this to
  x = a * (y - x) + x

should be pretty straight forward. I'll look at that tomorrow.


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


Re: [viff-devel] Small BuildBot fix

2008-02-25 Thread Janus Dam Nielsen

 The idea is the viff.dk will display the latest code and documentation
 whereas each release will contain a copy of the code and documentation
 as it was at the point of release. That way people should be able to
 always obtain API docs for their code, whether it being new or old. I
 would of course love if anybody thinks this is a bad idea...

This is all great. You would probably also want to either fork the  
repository or at least set some kind of marker (I don't know the  
correct term) when a release is done. In this way it is possible to  
go back and fix bugs in the release and release that without  
upgrading or waiting to the next release.

--
Janus


Den 25/02/2008 kl. 13.26 skrev Martin Geisler:

 Good evening everybody,

 I just saw that someone had pushed the 'Force Build' button on the
 BuildBot page -- and that had triggered an error in the 'link trial'
 step.

 That step simply does

   ln -s $(which trial)

 which means that we can run trial afterwards as ./trial. We do this
 since to test with different versions of python, we can then simply  
 run

   python2.4 ./trial viff

 or

   python2.5 ./trial viff

 Using a symbolic link to the real Trail binary makes this work both  
 when
 Trial is installed in /usr/bin (that is the case on my home  
 computer) or
 in ~/opt/bin (which is the case on DAIMI).

 It turns out that if you ask for a build of the tip revision, then
 BuildBot is smart enough to avoid deleting the build directory, and so
 the trial link was left there -- that made the second call to ln fail.

 I have fixed it now -- thanks to whoever forced the build by pressing
 the button!


 I'll try and make a third builder now which runs Epydoc whenever the
 source changes and maybe even uploads the API docs to viff.dk.

 The idea is the viff.dk will display the latest code and documentation
 whereas each release will contain a copy of the code and documentation
 as it was at the point of release. That way people should be able to
 always obtain API docs for their code, whether it being new or old. I
 would of course love if anybody thinks this is a bad idea...

 -- 
 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.dk: 8 new changesets

2008-02-22 Thread Janus Dam Nielsen
Well with all the messages and information you guys generate anyway,  
I don't need change messages to figure out that you are making progress.

I wouldn't look at the homepage every day anyway, so I don't use the  
messages as a reminder.

--
Janus


Den 22/02/2008 kl. 1.46 skrev Martin Geisler:

 Janus Dam Nielsen [EMAIL PROTECTED] writes:

 I would very much prefer not to get these messages.

 Do you mean the messages concerning the homepage?

 I really like the idea of publishing such a short summary when changes
 are made -- especially because the commit messages are included too,
 and I try to actually write something useful in them.

 Without these mails, would you then go check the homepage?

 I included the repository feed there to let casual observers know what
 we are doing, but as a developer I would want to know everything that
 happens in the project.

 Den 20/02/2008 kl. 15.57 skrev viff-devel@viff.dk:

 http://hg.viff.dk/viff.dk/rev/ec341fb94853
 changeset: 36:ec341fb94853
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 13:00:49 2008 +0100
 summary:   Filter out notification mails on the front page.

 http://hg.viff.dk/viff.dk/rev/dfe399e0b67e
 changeset: 37:dfe399e0b67e
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 13:02:01 2008 +0100
 summary:   Small code cleanup.

 [...]

 -- 
 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.dk: 8 new changesets

2008-02-20 Thread Janus Dam Nielsen
I would very much prefer not to get these messages.

--
Janus


Den 20/02/2008 kl. 15.57 skrev viff-devel@viff.dk:

 http://hg.viff.dk/viff.dk/rev/ec341fb94853
 changeset: 36:ec341fb94853
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 13:00:49 2008 +0100
 summary:   Filter out notification mails on the front page.

 http://hg.viff.dk/viff.dk/rev/dfe399e0b67e
 changeset: 37:dfe399e0b67e
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 13:02:01 2008 +0100
 summary:   Small code cleanup.

 http://hg.viff.dk/viff.dk/rev/a93c7113945e
 changeset: 38:a93c7113945e
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:26:38 2008 +0100
 summary:   Renamed /docs/ to /doc/.

 Redirection has been put in place via a .htaccess file, so no URLs
 should break because of this.

 http://hg.viff.dk/viff.dk/rev/c5cde5d82c72
 changeset: 39:c5cde5d82c72
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:28:08 2008 +0100
 summary:   Fixed link on front page.

 http://hg.viff.dk/viff.dk/rev/c49889f8f9ac
 changeset: 40:c49889f8f9ac
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:33:38 2008 +0100
 summary:   Send back permanent redirections to browsers.

 This will make Google and others switch to the new URLs while keeping
 the PageRank intact.

 http://hg.viff.dk/viff.dk/rev/65041ee232ea
 changeset: 41:65041ee232ea
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:34:31 2008 +0100
 summary:   Merged.

 http://hg.viff.dk/viff.dk/rev/f8c8f05bb4cc
 changeset: 42:f8c8f05bb4cc
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:44:49 2008 +0100
 summary:   Mark Python files as forbidden.

 People could executed them before by downloading them!

 http://hg.viff.dk/viff.dk/rev/43f18d1dc913
 changeset: 43:43f18d1dc913
 user:  Martin Geisler [EMAIL PROTECTED]
 date:  Wed Feb 20 22:54:33 2008 +0100
 summary:   Add 404 and 500 error pages.
 ___
 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] Splitting the Runtime into smaller pieces

2008-02-01 Thread Janus Dam Nielsen
Ohh so it is Turing complete? :)

--
Janus


Den 01/02/2008 kl. 1.52 skrev Martin Geisler:

 Janus Dam Nielsen [EMAIL PROTECTED] writes:

 Den 31/01/2008 kl. 14.21 skrev Martin Geisler:

 If you just want to select between two methods, then this also  
 works:

   class Comb(Base, Mix1, Mix2):
   foo = Mix1.foo

 Brilliant!

 Hehe, I think it's quite neat too :-)

 Being able to write stuff like that is so typically Python... it is a
 very flexible language that allows you to do almost anything you want.

 -- 
 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] Splitting the Runtime into smaller pieces

2008-01-31 Thread Janus Dam Nielsen
Den 31/01/2008 kl. 14.21 skrev Martin Geisler:

 If you just want to select between two methods, then this also works:

   class Comb(Base, Mix1, Mix2):
   foo = Mix1.foo

Brilliant!

--
Janus

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