viff

changeset 1550:c8e7c5ee1583

BeDOZa: Restructured tests for better code reuse. This changeset also contains further implementation of the zero-knowledge protocol, which is, however, not working yet.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Fri, 24 Sep 2010 14:21:36 +0200
parents 9a89c3397c9a
children 38793a845e3f
files viff/bedoza/modified_paillier.py viff/bedoza/util.py viff/bedoza/zero_knowledge.py viff/test/bedoza/test_bedoza_runtime.py viff/test/bedoza/test_bedoza_triple.py viff/test/bedoza/test_zero_knowledge.py viff/test/bedoza/util.py
diffstat 7 files changed, 406 insertions(+), 163 deletions(-) [+]
line diff
     1.1 --- a/viff/bedoza/modified_paillier.py	Thu Sep 23 10:07:35 2010 +0200
     1.2 +++ b/viff/bedoza/modified_paillier.py	Fri Sep 24 14:21:36 2010 +0200
     1.3 @@ -47,15 +47,20 @@
     1.4              return y
     1.5          else:
     1.6              return y - n
     1.7 -
     1.8 -    def encrypt(self, value, player_id=None):
     1.9 -        """Encrypt using public key of player player_id.
    1.10 -
    1.11 -        Defaults to own public key.
    1.12 -        """
    1.13 +     
    1.14 +    def _verify_input(self, value, player_id):
    1.15          assert isinstance(value, int) or isinstance(value, long), \
    1.16              "paillier: encrypts only integers and longs, got %s" % \
    1.17                  value.__class__
    1.18 +
    1.19 +    def encrypt_with_randomness(self, value, randomness, player_id=None):
    1.20 +        """Encrypt using public key of player player_id using the
    1.21 +        given randomness.
    1.22 +
    1.23 +        Defaults to own public key.
    1.24 +
    1.25 +        """
    1.26 +        self._verify_input(value, player_id)
    1.27          if not player_id:
    1.28              player_id = self.runtime.id
    1.29          n = self.runtime.players[player_id].pubkey['n']
    1.30 @@ -65,8 +70,23 @@
    1.31              "paillier: plaintext %d outside legal range [-(n-1)/2 " \
    1.32              "; (n-1)/2] = [%d ; %d]"  % (value, min, max)
    1.33          pubkey = self.runtime.players[player_id].pubkey
    1.34 -        randomness = self.random.randint(1, long(n))
    1.35 -        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
    1.36 +        return randomness, pypaillier.encrypt_r(self._f(value, n), randomness, pubkey) 
    1.37 +
    1.38 +    def encrypt_r(self, value, player_id=None):
    1.39 +       """As encrypt_with_randomness, but generates its own randomness."""
    1.40 +       self._verify_input(value, player_id)
    1.41 +       if not player_id:
    1.42 +           player_id = self.runtime.id
    1.43 +       n = self.runtime.players[player_id].pubkey['n']
    1.44 +       randomness = self.random.randint(1, long(n))
    1.45 +       return self.encrypt_with_randomness(value, randomness, player_id=player_id)
    1.46 +
    1.47 +
    1.48 +    def encrypt(self, value, player_id=None):
    1.49 +        """As encrypt_r, but doesn't return randomness used, only
    1.50 +        encrypted value."""
    1.51 +        return self.encrypt_r(value, player_id=player_id)[1]
    1.52 +
    1.53  
    1.54      def decrypt(self, enc_value):
    1.55          """Decrypt using own private key."""
     2.1 --- a/viff/bedoza/util.py	Thu Sep 23 10:07:35 2010 +0200
     2.2 +++ b/viff/bedoza/util.py	Fri Sep 24 14:21:36 2010 +0200
     2.3 @@ -61,3 +61,16 @@
     2.4  
     2.5  def fast_pow(a, b, modulus):
     2.6      return long(pow(mpz(a), b, modulus))
     2.7 +
     2.8 +
     2.9 +def rand_int_signed(random, lim):
    2.10 +    """Returns a pseudo-uniformly distributed random integer a
    2.11 +    such that abs(a) <= lim.
    2.12 +
    2.13 +    random: A random generator.
    2.14 +    """
    2.15 +    # TODO: This is probably not the fastes way to do it.
    2.16 +    res = random.randint(0, lim)
    2.17 +    if random.choice([True, False]):
    2.18 +        res = -res
    2.19 +    return res
     3.1 --- a/viff/bedoza/zero_knowledge.py	Thu Sep 23 10:07:35 2010 +0200
     3.2 +++ b/viff/bedoza/zero_knowledge.py	Fri Sep 24 14:21:36 2010 +0200
     3.3 @@ -15,43 +15,160 @@
     3.4  # You should have received a copy of the GNU Lesser General Public
     3.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     3.6  
     3.7 +import gmpy
     3.8 +import hashlib
     3.9 +
    3.10 +from viff.runtime import gatherResults
    3.11 +from viff.bedoza.util import rand_int_signed
    3.12  
    3.13  class ZKProof(object):
    3.14      """Protocol proving that a player's plaintexts are of limited size.
    3.15      
    3.16 -    This is a zero-knowledge protocol in which player player_id inputs s
    3.17 -    ciphertexts c[i] = E(x[j], r[j]), i = 1, ..., s, created using the
    3.18 -    modified Paillier cipher and proves to the other players that the x[i]'s
    3.19 -    are of limited size, e.g. that abs(x[i]) <= 2**k.
    3.20 +    This is a zero-knowledge protocol in which player with prover_id
    3.21 +    inputs s ciphertexts c[i] = E(x[j], r[j]), i = 1, ..., s, created
    3.22 +    using the modified Paillier cipher and proves to the other players
    3.23 +    that the x[i]'s are of limited size, e.g. that abs(x[i]) <= 2**k.
    3.24      
    3.25 -    Zn is the plaintext field of player player_id's modified Paillier cipher.
    3.26 -    
    3.27 -    While player player_id must input the ciphertexts, the other players
    3.28 -    should call the method with c = None.
    3.29 -    
    3.30 +    Zn is the plaintext field of player prover_id's modified Paillier
    3.31 +    cipher.
    3.32      """
    3.33      
    3.34 -    def __init__(self, player_id, Zn, c=None):
    3.35 -        self.player_id = player_id
    3.36 +    def __init__(self, s, prover_id, Zn, k, runtime, c, random=None, paillier=None, x=None, r=None):
    3.37 +        """
    3.38 +        random: a random source (e.g. viff.util.Random)
    3.39 +
    3.40 +        All players must submit c, but only the player with id
    3.41 +        prover_id should submit x and r.
    3.42 +        """
    3.43 +        self.x = x
    3.44 +        self.r = r
    3.45 +        self.s = s
    3.46 +        self.m = 2 * s - 1
    3.47 +        self.prover_id = prover_id
    3.48          self.Zn = Zn
    3.49 +        self.k = k
    3.50 +        self.runtime = runtime
    3.51          self.c = c
    3.52 -        self.e = None
    3.53 +        self.paillier = paillier
    3.54 +        self.random = random
    3.55  
    3.56 -    def start():
    3.57 +
    3.58 +
    3.59 +    def start(self):
    3.60 +        if self.runtime.id == self.prover_id:
    3.61 +            self._generate_proof()
    3.62 +        deferred_proof = self._get_proof_broadcasted_by_prover()
    3.63 +        self.runtime.schedule_callback(deferred_proof, self._verify_proof)
    3.64 +        return deferred_proof
    3.65 +
    3.66 +    def _generate_proof(self):
    3.67 +        self._generate_u_v_and_d()
    3.68 +        self._generate_e()
    3.69 +        self._generate_Z_and_W()
    3.70 +
    3.71 +    def _verify_proof(self, serialized_proof):
    3.72 +        # The prover don't need to prove to himself.
    3.73 +        if self.runtime.id == self.prover_id:
    3.74 +            #print 'x', len(self.x)
    3.75 +            #print 'e', len(self.e)
    3.76 +            #print 'u', len(self.u)
    3.77 +            return
    3.78 +        self._deserialize_proof(serialized_proof)
    3.79 +        self._generate_e()
    3.80 +        q = self._vec_mul(self.d, self._vec_pow_E(self.c))
    3.81          
    3.82 -        pass
    3.83  
    3.84 -    def _set_e(self, e):
    3.85 -        self.e = e
    3.86 -        self.s = len(e)
    3.87 -        self.m = 2 * len(e) - 1
    3.88  
    3.89 -    def _generate_challenge(self):
    3.90 -        # TODO: Implement.
    3.91 -        self.e = [0, 0, 1, 0, 1]
    3.92 -        self.s = len(e)
    3.93 -        self.m = 2 * len(e) - 1
    3.94 +        #print 'Z', len(self.Z)
    3.95 +        #print 'W', len(self.W)
    3.96 +        
    3.97  
    3.98 +        for j in xrange(self.m):
    3.99 +            pass
   3.100 +            #print
   3.101 +            #print '---'
   3.102 +            #print self.runtime.id,  self.paillier.encrypt_with_randomness(self.Z[j], self.W[j])[1]
   3.103 +            #print self.runtime.id, q[j]
   3.104 +
   3.105 +            # TODO: Verify!
   3.106 +
   3.107 +
   3.108 +    def _generate_u_v_and_d(self):
   3.109 +        self.u, self.v, self.d = [], [], []
   3.110 +        for i in range(self.m):
   3.111 +            ui = rand_int_signed(self.random, 2**(2 * self.k))
   3.112 +            vi, di = self.paillier.encrypt_r(ui)
   3.113 +            self.u.append(ui)
   3.114 +            self.v.append(vi)
   3.115 +            self.d.append(di)
   3.116 +
   3.117 +    def _generate_Z_and_W(self):
   3.118 +        self.Z = self._vec_add(self.u, self._vec_mul_E(self.x))
   3.119 +        self.W = self._vec_mul(self.v, self._vec_pow_E(self.r))
   3.120 +        
   3.121 +    def _get_proof_broadcasted_by_prover(self):
   3.122 +        serialized_proof = None
   3.123 +        if self.runtime.id == self.prover_id:
   3.124 +            # TODO: Should we somehow compress message for improved performance?
   3.125 +            serialized_proof = self._serialize_proof()
   3.126 +        deferred_proof = self._broadcast(serialized_proof)
   3.127 +        return deferred_proof
   3.128 +
   3.129 +    def _serialize_proof(self):
   3.130 +        return repr([self.d, self.Z, self.W])
   3.131 +
   3.132 +    def _deserialize_proof(self, serialized_proof):
   3.133 +        # We remove quotes before evaluation in order to get a list.
   3.134 +        proof = eval(serialized_proof[1:-1])
   3.135 +        self.d = proof[0]
   3.136 +        self.Z = proof[1]
   3.137 +        self.W = proof[2]
   3.138 +
   3.139 +    def _extract_bits(self, string, no_of_bits):
   3.140 +        """Returns list of first no_of_bits from the given string."""
   3.141 +        word_size = 8 # No of bits in char.
   3.142 +        assert no_of_bits <= word_size * len(string), "Not enough bits"
   3.143 +        res = []
   3.144 +        if no_of_bits == 0:
   3.145 +            return res
   3.146 +        no_of_chars = 1 + no_of_bits / word_size
   3.147 +        for c in string[:no_of_chars]:
   3.148 +            digits = [int(v) for v in gmpy.digits(ord(c), 2).zfill(word_size)]
   3.149 +            if len(res) + word_size >= no_of_bits:
   3.150 +                return res + digits[:no_of_bits - len(res)]
   3.151 +            res += digits
   3.152 +        return res
   3.153 +
   3.154 +
   3.155 +    def _generate_e(self):
   3.156 +        """Generating an s-bit challenge e by the Fiat-Shamir heuristic.
   3.157 +        
   3.158 +        In other security models, generating the challenge requires
   3.159 +        interaction.
   3.160 +       
   3.161 +        The challenge is a list of 0's and 1's of length s.
   3.162 +        """
   3.163 +        # This can be easily fixed by using the hash as seed for a
   3.164 +        # secure prng.
   3.165 +        assert self.s <= 160, "Error: Algorithm only supports s <= 160"
   3.166 +        assert hasattr(self, 'c')
   3.167 +        assert hasattr(self, 'd')
   3.168 +        h = hashlib.sha1()
   3.169 +        for c, d in zip(self.c, self.d):
   3.170 +            h.update(repr(c))
   3.171 +            h.update(repr(d))
   3.172 +        hash = h.digest()
   3.173 +        self.e = self._extract_bits(hash, self.s)
   3.174 +
   3.175 +
   3.176 +    def _broadcast(self, values):
   3.177 +        msg = repr(values) if self.prover_id == self.runtime.id else None
   3.178 +        return self.runtime.broadcast(
   3.179 +            [self.prover_id], self.runtime.players.keys(), message=msg)
   3.180 +
   3.181 +    def _err_handler(self, err):
   3.182 +        print err
   3.183 +        return err # raise or what?
   3.184  
   3.185      def _E(self, row, col):
   3.186          """Computes the value of the entry in the matrix E at the given row
   3.187 @@ -66,18 +183,32 @@
   3.188          else:
   3.189              return 0
   3.190  
   3.191 -    def vec_add(self, x, y):
   3.192 -        return [xi + yi for x, y in zip(x,y)]
   3.193 +    def _vec_add(self, x, y):
   3.194 +        return [x + y for x, y in zip(x,y)]
   3.195 +
   3.196 +    def _vec_mul_E(self, x):
   3.197 +        """Takes an s x 1 vector x and returns the m x 1 vector xE."""
   3.198 +        # TODO: This could probably be optimized since we know the
   3.199 +        # structure of E.
   3.200 +        res = []
   3.201 +        for j in xrange(self.m):
   3.202 +            t = 0
   3.203 +            for i in xrange(self.s):
   3.204 +                t = t + x[i] * self._E(j, i)
   3.205 +            res.append(t)
   3.206 +        return res
   3.207      
   3.208 -    def vec_mul(self, x, y):
   3.209 -        return [xi * yi for x, y in zip(x,y)]
   3.210 +    def _vec_mul(self, x, y):
   3.211 +        return [x * y for x, y in zip(x,y)]
   3.212  
   3.213 -    def vec_pow_E(self, y):
   3.214 +    def _vec_pow_E(self, y):
   3.215          """Computes and returns the m := 2s-1 length vector y**E."""
   3.216          assert self.s == len(y), \
   3.217              "not same length: %d != %d" % (self.s, len(y))
   3.218 -        res = [self.Zn(1)] * self.m
   3.219 -        for j in range(2 * self.s - 1):
   3.220 +        #res = [self.Zn(1)] * self.m
   3.221 +        # TODO: Should do all computations over some field.
   3.222 +        res = [1] * self.m
   3.223 +        for j in range(self.m):
   3.224              for i in range(self.s):
   3.225                  if self._E(j, i) == 1:
   3.226                      res[j] *= y[i]
     4.1 --- a/viff/test/bedoza/test_bedoza_runtime.py	Thu Sep 23 10:07:35 2010 +0200
     4.2 +++ b/viff/test/bedoza/test_bedoza_runtime.py	Fri Sep 24 14:21:36 2010 +0200
     4.3 @@ -36,28 +36,10 @@
     4.4  from viff.bedoza.bedoza_triple import TripleGenerator
     4.5  from viff.bedoza.zero_knowledge import ZKProof
     4.6  
     4.7 -# The PyPaillier and commitment packages are not standard parts of VIFF so we
     4.8 -# skip them instead of letting them fail if the packages are not available. 
     4.9 -try:
    4.10 -    import pypaillier
    4.11 -except ImportError:
    4.12 -    pypaillier = None
    4.13 +from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
    4.14  
    4.15 -# HACK: The paillier keys that are available as standard in VIFF tests
    4.16 -# are not suited for use with pypaillier. Hence, we use NaClPaillier
    4.17 -# to generate test keys. This confusion will disappear when pypaillier
    4.18 -# replaces the current Python-based paillier implementation.
    4.19 -from viff.paillierutil import NaClPaillier
    4.20  
    4.21 -# HACK^2: Currently, the NaClPaillier hack only works when triple is
    4.22 -# imported. It should ideally work without the triple package.
    4.23 -try:
    4.24 -    import tripple
    4.25 -except ImportError:
    4.26 -    tripple = None
    4.27 -
    4.28 -
    4.29 -class BeDOZaBasicCommandsTest(RuntimeTestCase):
    4.30 +class BeDOZaBasicCommandsTest(BeDOZaTestCase):
    4.31      """Test for basic commands."""
    4.32  
    4.33      # Number of players.
    4.34 @@ -65,16 +47,6 @@
    4.35  
    4.36      timeout = 3
    4.37  
    4.38 -    runtime_class = BeDOZaRuntime
    4.39 -
    4.40 -    # TODO: During test, we would like generation of Paillier keys to
    4.41 -    # be deterministic. How do we obtain that?
    4.42 -    def generate_configs(self, *args):
    4.43 -        # In production, paillier keys should be something like 2000
    4.44 -        # bit. For test purposes, it is ok to use small keys.
    4.45 -        # TODO: paillier freezes if key size is too small, e.g. 13.
    4.46 -        return generate_configs(paillier=NaClPaillier(250), *args)
    4.47 -
    4.48      def setUp(self):
    4.49          RuntimeTestCase.setUp(self)
    4.50          self.Zp = GF(17)
    4.51 @@ -528,35 +500,4 @@
    4.52          return d
    4.53  
    4.54  
    4.55 -# TODO: Move to test.bedoza.test_zero_knowledge.
    4.56 -class BeDOZaZeroKnowledgeTest(RuntimeTestCase):
    4.57 -
    4.58 -    num_players = 3
    4.59 -
    4.60 -    timeout = 3
    4.61 -
    4.62 -    runtime_class = BeDOZaRuntime
    4.63 -
    4.64 -    def test_zk_matrix_entries_are_correct(self):
    4.65 -        zk = ZKProof(None, None)
    4.66 -        zk._set_e([1, 0, 0, 1, 1])
    4.67 -        for i in range(zk.s):
    4.68 -            for j in range(zk.m):
    4.69 -                if j >= i and j < i + zk.s:
    4.70 -                    self.assertEquals(zk.e[j - i], zk._E(j, i))
    4.71 -                else:
    4.72 -                    self.assertEquals(0, zk._E(j, i))
    4.73 -
    4.74 -    def test_vec_pow_is_correct(self):
    4.75 -        Zn = GF(17)
    4.76 -        y = [Zn(i) for i in range(1, 6)]
    4.77 -        zk = ZKProof(None, Zn)
    4.78 -        zk._set_e([1, 0, 1, 1, 0])
    4.79 -        y_pow_E = zk.vec_pow_E(y)
    4.80 -        self.assertEquals([Zn(v) for v in [1, 2, 3, 8, 13, 12, 3, 5, 1]],
    4.81 -                          y_pow_E)
    4.82 -def skip_tests(module_name):
    4.83 -    BeDOZaBasicCommandsTest.skip = "Skipped due to missing " + module_name + " module."
    4.84 -
    4.85 -if not pypaillier:
    4.86 -    skip_tests("pypaillier")
    4.87 +skip_if_missing_packages(BeDOZaBasicCommandsTest)
     5.1 --- a/viff/test/bedoza/test_bedoza_triple.py	Thu Sep 23 10:07:35 2010 +0200
     5.2 +++ b/viff/test/bedoza/test_bedoza_triple.py	Fri Sep 24 14:21:36 2010 +0200
     5.3 @@ -25,12 +25,14 @@
     5.4  
     5.5  from twisted.internet.defer import gatherResults, Deferred, DeferredList
     5.6  
     5.7 -from viff.test.util import RuntimeTestCase, protocol
     5.8 +from viff.test.util import protocol
     5.9  from viff.constants import TEXT
    5.10  from viff.runtime import gather_shares, Share
    5.11  from viff.config import generate_configs
    5.12  
    5.13 -from viff.bedoza.bedoza import BeDOZaRuntime, BeDOZaShare
    5.14 +from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
    5.15 +
    5.16 +from viff.bedoza.bedoza import BeDOZaShare
    5.17  from viff.bedoza.keylist import BeDOZaKeyList
    5.18  from viff.bedoza.bedoza_triple import TripleGenerator, ModifiedPaillier
    5.19  from viff.bedoza.share_generators import PartialShareGenerator, ShareGenerator
    5.20 @@ -41,53 +43,10 @@
    5.21  from viff.field import FieldElement, GF
    5.22  from viff.config import generate_configs
    5.23  
    5.24 -
    5.25  # Ok to use non-secure random generator in tests.
    5.26  #from viff.util import rand
    5.27  import random
    5.28  
    5.29 -# The PyPaillier and commitment packages are not standard parts of VIFF so we
    5.30 -# skip them instead of letting them fail if the packages are not available. 
    5.31 -try:
    5.32 -    import pypaillier
    5.33 -except ImportError:
    5.34 -    pypaillier = None
    5.35 -
    5.36 -# HACK: The paillier keys that are available as standard in VIFF tests
    5.37 -# are not suited for use with pypaillier. Hence, we use NaClPaillier
    5.38 -# to generate test keys. This confusion will disappear when pypaillier
    5.39 -# replaces the current Python-based paillier implementation.
    5.40 -from viff.paillierutil import NaClPaillier
    5.41 -
    5.42 -# HACK^2: Currently, the NaClPaillier hack only works when triple is
    5.43 -# imported. It should ideally work without the triple package.
    5.44 -try:
    5.45 -    import tripple
    5.46 -except ImportError:
    5.47 -    tripple = None
    5.48 -
    5.49 -
    5.50 -
    5.51 -def _log(rt, msg):
    5.52 -    print "player%d ------> %s" % (rt.id, msg)
    5.53 -
    5.54 -
    5.55 -class BeDOZaTestCase(RuntimeTestCase):
    5.56 -
    5.57 -    runtime_class = BeDOZaRuntime
    5.58 -
    5.59 -    def setUp(self):
    5.60 -        RuntimeTestCase.setUp(self)
    5.61 -        self.security_parameter = 32
    5.62 -
    5.63 -    # TODO: During test, we would like generation of Paillier keys to
    5.64 -    # be deterministic. How do we obtain that?
    5.65 -    def generate_configs(self, *args):
    5.66 -        # In production, paillier keys should be something like 2000
    5.67 -        # bit. For test purposes, it is ok to use small keys.
    5.68 -        # TODO: paillier freezes if key size is too small, e.g. 13.
    5.69 -        return generate_configs(paillier=NaClPaillier(250), *args)
    5.70 -
    5.71  
    5.72  class DataTransferTest(BeDOZaTestCase):
    5.73      num_players = 3
    5.74 @@ -615,21 +574,12 @@
    5.75          return d
    5.76          
    5.77  
    5.78 -
    5.79 -missing_package = None
    5.80 -if not pypaillier:
    5.81 -    missing_package = "pypaillier"
    5.82 -if not tripple:
    5.83 -    missing_package = "tripple"
    5.84 -if missing_package:
    5.85 -    test_cases = [ModifiedPaillierTest,
    5.86 -                  PartialShareGeneratorTest,
    5.87 -                  TripleTest,
    5.88 -                  DataTransferTest,
    5.89 -                  MulTest,
    5.90 -                  FullMulTest,
    5.91 -                  ShareGeneratorTest,
    5.92 -                  AddMacsTest
    5.93 -                  ]
    5.94 -    for test_case in test_cases:
    5.95 -        test_case.skip =  "Skipped due to missing %s package." % missing_package
    5.96 +skip_if_missing_packages(
    5.97 +    ModifiedPaillierTest,
    5.98 +    PartialShareGeneratorTest,
    5.99 +    TripleTest,
   5.100 +    DataTransferTest,
   5.101 +    MulTest,
   5.102 +    FullMulTest,
   5.103 +    ShareGeneratorTest,
   5.104 +    AddMacsTest)
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/viff/test/bedoza/test_zero_knowledge.py	Fri Sep 24 14:21:36 2010 +0200
     6.3 @@ -0,0 +1,127 @@
     6.4 +# Copyright 2010 VIFF Development Team.
     6.5 +#
     6.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     6.7 +#
     6.8 +# VIFF is free software: you can redistribute it and/or modify it
     6.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    6.10 +# published by the Free Software Foundation, either version 3 of the
    6.11 +# License, or (at your option) any later version.
    6.12 +#
    6.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    6.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    6.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    6.16 +# Public License for more details.
    6.17 +#
    6.18 +# You should have received a copy of the GNU Lesser General Public
    6.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    6.20 +
    6.21 +
    6.22 +# We don't need secure random numbers for test purposes.
    6.23 +from random import Random
    6.24 +
    6.25 +from viff.field import GF
    6.26 +from viff.bedoza.modified_paillier import ModifiedPaillier
    6.27 +from viff.bedoza.zero_knowledge import ZKProof
    6.28 +from viff.bedoza.util import rand_int_signed
    6.29 +
    6.30 +from viff.test.util import protocol
    6.31 +from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
    6.32 +
    6.33 +
    6.34 +class BeDOZaZeroKnowledgeTest(BeDOZaTestCase):
    6.35 +
    6.36 +    num_players = 3
    6.37 +
    6.38 +    def test_zk_matrix_entries_are_correct(self):
    6.39 +        s = 5
    6.40 +        zk = ZKProof(s, None, None, 0, None, None)
    6.41 +        zk.e = [1, 0, 0, 1, 1]
    6.42 +        for i in range(zk.s):
    6.43 +            for j in range(zk.m):
    6.44 +                if j >= i and j < i + zk.s:
    6.45 +                    self.assertEquals(zk.e[j - i], zk._E(j, i))
    6.46 +                else:
    6.47 +                    self.assertEquals(0, zk._E(j, i))
    6.48 +
    6.49 +    def test_vec_pow_is_correct(self):
    6.50 +        s, Zn = 5, GF(17)
    6.51 +        y = [Zn(i) for i in range(1, 6)]
    6.52 +        zk = ZKProof(s, None, Zn, 0, None, None)
    6.53 +        zk.e = [1, 0, 1, 1, 0]
    6.54 +        y_pow_E = zk._vec_pow_E(y)
    6.55 +        self.assertEquals([Zn(v) for v in [1, 2, 3, 8, 13, 12, 3, 5, 1]],
    6.56 +                          y_pow_E)
    6.57 +
    6.58 +    def test_vec_mul_E_is_correct(self):
    6.59 +        s, Zn = 5, GF(17)
    6.60 +        y = [Zn(i) for i in range(1, 6)]
    6.61 +        zk = ZKProof(s, None, Zn, 0, None, None)
    6.62 +        zk.e = [1, 0, 1, 1, 0]
    6.63 +        x = [1, 2, 0, 1, 0]
    6.64 +        x_mul_E = zk._vec_mul_E(x)
    6.65 +        self.assertEquals([v for v in [1, 2, 1, 4, 2, 1, 1, 0, 0]], x_mul_E)
    6.66 +
    6.67 +    @protocol
    6.68 +    def test_broadcast(self, runtime):
    6.69 +        zk = ZKProof(0, 2, None, 0, runtime, None)
    6.70 +        res = zk._broadcast([5, 6, 7])
    6.71 +        def verify(res):
    6.72 +            self.assertEquals(eval(res), [5, 6, 7])
    6.73 +        runtime.schedule_callback(res, verify)
    6.74 +        return res
    6.75 +
    6.76 +    @protocol
    6.77 +    def test_proof(self, runtime):
    6.78 +        k, s, random, Zn = 5, 5, Random(342344), GF(17)
    6.79 +
    6.80 +        paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
    6.81 +        x, r, c = self._generate_test_ciphertexts(paillier, random, k, s)
    6.82 +        zk = ZKProof(s, 1, Zn, k, runtime, c, paillier=paillier, random=random, x=x, r=r)
    6.83 +        zk.e = [1, 0, 0, 1, 1]
    6.84 +        deferred_proof = zk.start()
    6.85 +        return deferred_proof
    6.86 +
    6.87 +    def test_extract_bits(self):
    6.88 +        s = 5
    6.89 +        zk = ZKProof(s, None, None, 0, None, None)
    6.90 +        self.assertEquals([], zk._extract_bits('test', 0))
    6.91 +        self.assertEquals([0], zk._extract_bits('test', 1))
    6.92 +        self.assertEquals([0, 1], zk._extract_bits('test', 2))
    6.93 +        self.assertEquals([0, 1, 1, 1, 0, 1, 0], zk._extract_bits('test', 7))
    6.94 +        self.assertEquals([0, 1, 1, 1, 0, 1, 0, 0], zk._extract_bits('test', 8))
    6.95 +        self.assertEquals([0, 1, 1, 1, 0, 1, 0, 0, 0], zk._extract_bits('test', 9))
    6.96 +        self.assertEquals([0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1], zk._extract_bits('test', 14))
    6.97 +
    6.98 +    def test_generate_e_generates_e_of_right_length(self):
    6.99 +        s = 5
   6.100 +        c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
   6.101 +        zk = ZKProof(s, None, None, 0, None, c)
   6.102 +        zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
   6.103 +        zk._generate_e()
   6.104 +        self.assertEquals(5, len(zk.e))
   6.105 +
   6.106 +    def test_generate_e_is_deterministic(self):
   6.107 +        s = 5
   6.108 +        c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
   6.109 +        zk = ZKProof(s, None, None, 0, None, c)
   6.110 +        zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
   6.111 +        zk._generate_e()
   6.112 +        e1 = zk.e
   6.113 +        zk._generate_e()
   6.114 +        self.assertEquals(e1, zk.e)
   6.115 +
   6.116 +    def _generate_test_ciphertexts(self, paillier, random, k, s):
   6.117 +        xs, rs, cs = [], [], []
   6.118 +        for i in range(s):
   6.119 +            x = rand_int_signed(random, 2**k)
   6.120 +            r, c = paillier.encrypt_r(x)
   6.121 +            xs.append(x)
   6.122 +            rs.append(r)
   6.123 +            cs.append(c)
   6.124 +        return xs, rs, cs
   6.125 +            
   6.126 +
   6.127 +# TODO: Test succeeding proof.
   6.128 +# TODO: Test failing proof.
   6.129 +
   6.130 +skip_if_missing_packages(BeDOZaZeroKnowledgeTest)
     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/viff/test/bedoza/util.py	Fri Sep 24 14:21:36 2010 +0200
     7.3 @@ -0,0 +1,61 @@
     7.4 +
     7.5 +from viff.test.util import RuntimeTestCase
     7.6 +from viff.config import generate_configs
     7.7 +
     7.8 +from viff.bedoza.bedoza import BeDOZaRuntime
     7.9 +
    7.10 +# HACK: The paillier keys that are available as standard in VIFF tests
    7.11 +# are not suited for use with pypaillier. Hence, we use NaClPaillier
    7.12 +# to generate test keys. This confusion will disappear when pypaillier
    7.13 +# replaces the current Python-based paillier implementation.
    7.14 +from viff.paillierutil import NaClPaillier
    7.15 +
    7.16 +# HACK^2: Currently, the NaClPaillier hack only works when triple is
    7.17 +# imported. It should ideally work without the triple package.
    7.18 +try:
    7.19 +    import tripple
    7.20 +except ImportError:
    7.21 +    tripple = None
    7.22 +
    7.23 +# The PyPaillier and commitment packages are not standard parts of VIFF so we
    7.24 +# skip them instead of letting them fail if the packages are not available. 
    7.25 +try:
    7.26 +    import pypaillier
    7.27 +except ImportError:
    7.28 +    pypaillier = None
    7.29 +
    7.30 +
    7.31 +
    7.32 +def log(rt, msg):
    7.33 +    print "player%d ------> %s" % (rt.id, msg)
    7.34 +
    7.35 +
    7.36 +class BeDOZaTestCase(RuntimeTestCase):
    7.37 +
    7.38 +    runtime_class = BeDOZaRuntime
    7.39 +
    7.40 +    def setUp(self):
    7.41 +        RuntimeTestCase.setUp(self)
    7.42 +        self.security_parameter = 32
    7.43 +
    7.44 +    # TODO: During test, we would like generation of Paillier keys to
    7.45 +    # be deterministic. How do we obtain that?
    7.46 +    def generate_configs(self, *args):
    7.47 +        # In production, paillier keys should be something like 2000
    7.48 +        # bit. For test purposes, it is ok to use small keys.
    7.49 +        # TODO: paillier freezes if key size is too small, e.g. 13.
    7.50 +        return generate_configs(paillier=NaClPaillier(250), *args)
    7.51 +
    7.52 +
    7.53 +def skip_if_missing_packages(*test_cases):
    7.54 +    """Skipts the given list of test cases if some of the required
    7.55 +    external viff packages (tripple, pypaillier) is not available.
    7.56 +    """
    7.57 +    missing = []
    7.58 +    if not pypaillier:
    7.59 +        missing.append("pypaillier")
    7.60 +    if not tripple:
    7.61 +        missing.append("tripple")
    7.62 +    if missing:
    7.63 +        for test_case in test_cases:
    7.64 +            test_case.skip =  "Skipped due to missing packages: %s" % missing