Tord Ingolf Reistad <[EMAIL PROTECTED]> writes:
Hi Tord
> I will need some help with the implementation. I will write some
> detailed psaudocode and you can help me transform it into Pyton.
Sure! I would love to include some tutorial-like material on this
mailing list to help you and others get started with VIFF.
> Two questions before I start:
> What is the function (and where is it located) for generating a
> random bitwise secret shared value?
The VIFF runtime has no single function to do this, but it is easy to
do anyway. The beginning of the greater_than method has code similar
to this:
# First we share m bits with PRSS (underscore is a typical choice
# for a variable which is ignored):
bits = [self.prss_share_random(field, True) for _ in range(m)]
# We can calculate [v] = \sum_{i=0}^{m-1} 2^i * [b_i] which will
# make [v] a secret sharing. To do this we first define a local
# function to do the work:
def bits_to_int(bits):
"""Converts a list of bits to an integer."""
# The builtin enumerate function takes a sequence [x, y, z, ...]
# and returns a sequence of pairs [(0, x), (1, y), (2, z), ...].
# This is very handy for this kind of calculations:
return sum([2**i * b_i for i, b_i in enumerate(bits)])
# At this point we have the "bits" variable above, which contains a
# list of Shares. We want a new variable, lets call it "value",
# which depends on the shares. The gather_shares function does that:
value = gather_shares(bits)
# When all the Shares in bits are ready, value will be ready as
# well. If we do nothing, then value will simply contain a list of
# Shares. But we want value to contain a single Share with the value
# of \sum_{i=0}^{m-1} 2^i * [b_i] as described above.
#
# So we add the bits_to_int function to the list of callbacks for
# value (this list is initially empty):
value.addCallback(bits_to_int)
That code should do it -- if you strip out some of the comments you'll
see that it's not so difficult :-)
You can think of the callbacks as filters in a pipe-line. If you
create a Share it will initially be empty. If you start an interactive
Python session you can do this (">>>" is your prompt):
>>> from viff.runtime import Share
Seeding random generator with random seed 3195
>>> s = Share(None)
(Here we cheated and used None instead of a proper runtime. That will
work for this example.)
You cannot do much with such a guy -- it has no value yet. The only
thing you can do is to add filters which will work on the value it
will eventually get. We can for example square the value:
>>> s.addCallback(lambda x: x * x)
<Share at 0xB7F042ACL>
We can add more filters:
>>> s.addCallback(lambda x: x - 5)
<Share at 0xB7F042ACL>
These anonymous functions will be called one after each other when s
finally gets a value. The result from one function is passed as the
input to the next function. Because we're dealing with a Share, we
know that the initial input will be a field element, and that is why I
can write "x * x" and "x - 5" since those operations are overloaded
for field elements.
You can change the type of the value flowing in the filter along the
way -- this will change the field element into a string:
>>> s.addCallback(lambda x: str(x))
<Share at 0xB7F042ACL>
Let us work some more on the string:
>>> s.addCallback(lambda s: "The string was: %s" % s)
<Share at 0xB7F042ACL>
This uses the "%" operator which is quite similar to the printf
statement in C.
We now have a Share s which is loaded with four functions! But it has
no value to work on yet, so nothing has really been achieved. Putting
a value into a Share is done by the callback method. Let's put
GF256(10) into s:
>>> from viff.field import GF256
>>> s.callback(GF256(10))
Nothing happened? Well, the functions has been evaluated, but the
result is in s. You can see it if you evaluate s again:
>>> s
<Share at 0xB7F042ACL current result: 'The string was: [65]'>
That is how you work on a Share. The gather_shares function is a
function which takes a list of Shares and gives you back a Share. This
share will receive a list of field elements as its initial value. This
is extremely handy in VIFF. For example, to multiply two Shares (when
they are ready) you would do
>>> from viff.runtime import gather_shares
>>> x = Share(None) # Test share 1
>>> y = Share(None) # Test share 2
>>> z = gather_shares([x, y]) # This will eventually be the product
We now only need to define a proper callback on z and then it will be
ready to act as the product of x and y:
>>> z.addCallback(lambda results: results[0] * results[1])
<ShareList at 0xB7F0438CL>
When we give x and y values, z gets a value too:
>>> x.callback(GF256(5))
>>> y.callback(GF256(6))
>>> z
<ShareList at 0xB7F0438CL current result: [30]>
> What is the function (and where is it located) for generating random
> values in the field?
If you need a secret shared random value, then use the
prss_share_random method in Runtime. It is used like this:
Zp = field.GF(17)
rt = Runtime(...)
x = rt.prss_share_random(Zp)
If you instead just want a random field element (not secret shared),
then use viff.util.rand. This is a standard random generator, you'll
find the documentation here:
http://docs.python.org/lib/module-random.html
In an interactive Python session it would look like this:
>>> from viff import field
>>> from viff import util
Seeding random generator with random seed 6494
>>> Zp = field.GF(17)
>>> x = Zp(util.rand.randint(0, 16))
>>> x
{3}
>>> y = Zp(util.rand.randint(0, Zp.modulus))
>>> y
{6}
When exploring a Python API, then it is good to know the pprint
package and the builtin dir function:
>>> from pprint import pprint
>>> pprint(dir(util))
['Deferred',
'__builtins__',
'__doc__',
'__file__',
'__name__',
'_indent',
'_seed',
'_trace_counters',
'clone_deferred',
'deprecation',
'dlift',
'dprint',
'gatherResults',
'os',
'println',
'rand',
'random',
'succeed',
'trace',
'warnings']
The builtin help function is also handy since it works on all objects
you can get hold on in Python:
>>> help(util)
Help on module viff.util in viff:
NAME
viff.util - Utility function.
FILE
/home/mg/src/viff/viff/util.py
DESCRIPTION
This module contains various utility functions used in all parts
of the VIFF code. The most important is the L{rand} random
generator which is seeded with a known seed each time. Using this
generator for all random numbers ensures that a protocol run can
be reproduced at a later time.
FUNCTIONS
clone_deferred(original)
Clone a Deferred.
The returned clone will fire with the same result as the
original Deferred, but will otherwise be independent.
...
So... there's something to digest :-) I hope it helps!
--
Martin Geisler
_______________________________________________
viff-devel mailing list (http://viff.dk/)
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
