viff

changeset 1543:7db2fafaab44

BeDOZa: Partly implemented zero-knowledge protocol.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Tue, 21 Sep 2010 10:05:02 +0200
parents 8e06a2598579
children dae353266aa6
files viff/bedoza/zero_knowledge.py viff/test/test_bedoza_runtime.py
diffstat 2 files changed, 114 insertions(+), 1 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/viff/bedoza/zero_knowledge.py	Tue Sep 21 10:05:02 2010 +0200
     1.3 @@ -0,0 +1,84 @@
     1.4 +# Copyright 2010 VIFF Development Team.
     1.5 +#
     1.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.7 +#
     1.8 +# VIFF is free software: you can redistribute it and/or modify it
     1.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    1.10 +# published by the Free Software Foundation, either version 3 of the
    1.11 +# License, or (at your option) any later version.
    1.12 +#
    1.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.16 +# Public License for more details.
    1.17 +#
    1.18 +# You should have received a copy of the GNU Lesser General Public
    1.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.20 +
    1.21 +
    1.22 +class ZKProof(object):
    1.23 +    """Protocol proving that a player's plaintexts are of limited size.
    1.24 +    
    1.25 +    This is a zero-knowledge protocol in which player player_id inputs s
    1.26 +    ciphertexts c[i] = E(x[j], r[j]), i = 1, ..., s, created using the
    1.27 +    modified Paillier cipher and proves to the other players that the x[i]'s
    1.28 +    are of limited size, e.g. that abs(x[i]) <= 2**k.
    1.29 +    
    1.30 +    Zn is the plaintext field of player player_id's modified Paillier cipher.
    1.31 +    
    1.32 +    While player player_id must input the ciphertexts, the other players
    1.33 +    should call the method with c = None.
    1.34 +    
    1.35 +    """
    1.36 +    
    1.37 +    def __init__(self, player_id, Zn, c=None):
    1.38 +        self.player_id = player_id
    1.39 +        self.Zn = Zn
    1.40 +        self.c = c
    1.41 +        self.e = None
    1.42 +
    1.43 +    def start():
    1.44 +        
    1.45 +        pass
    1.46 +
    1.47 +    def _set_e(self, e):
    1.48 +        self.e = e
    1.49 +        self.s = len(e)
    1.50 +        self.m = 2 * len(e) - 1
    1.51 +
    1.52 +    def _generate_challenge(self):
    1.53 +        # TODO: Implement.
    1.54 +        self.e = [0, 0, 1, 0, 1]
    1.55 +        self.s = len(e)
    1.56 +        self.m = 2 * len(e) - 1
    1.57 +
    1.58 +
    1.59 +    def _E(self, row, col):
    1.60 +        """Computes the value of the entry in the matrix E at the given row
    1.61 +        and column.
    1.62 +        
    1.63 +        The first column of E consists of the bits of e followed by 0's;
    1.64 +        The next column has one zero, then the bits of e, followed by 0's,
    1.65 +        etc.
    1.66 +        """
    1.67 +        if row >= col and row < col + self.s:
    1.68 +            return self.e[row - col]
    1.69 +        else:
    1.70 +            return 0
    1.71 +
    1.72 +    def vec_add(self, x, y):
    1.73 +        return [xi + yi for x, y in zip(x,y)]
    1.74 +    
    1.75 +    def vec_mul(self, x, y):
    1.76 +        return [xi * yi for x, y in zip(x,y)]
    1.77 +
    1.78 +    def vec_pow_E(self, y):
    1.79 +        """Computes and returns the m := 2s-1 length vector y**E."""
    1.80 +        assert self.s == len(y), \
    1.81 +            "not same length: %d != %d" % (self.s, len(y))
    1.82 +        res = [self.Zn(1)] * self.m
    1.83 +        for j in range(2 * self.s - 1):
    1.84 +            for i in range(self.s):
    1.85 +                if self._E(j, i) == 1:
    1.86 +                    res[j] *= y[i]
    1.87 +        return res
     2.1 --- a/viff/test/test_bedoza_runtime.py	Mon Sep 20 21:56:39 2010 +0200
     2.2 +++ b/viff/test/test_bedoza_runtime.py	Tue Sep 21 10:05:02 2010 +0200
     2.3 @@ -34,6 +34,7 @@
     2.4  from viff.bedoza.modified_paillier import ModifiedPaillier
     2.5  from viff.bedoza.share_generators import ShareGenerator
     2.6  from viff.bedoza.bedoza_triple import TripleGenerator
     2.7 +from viff.bedoza.zero_knowledge import ZKProof
     2.8  
     2.9  # The PyPaillier and commitment packages are not standard parts of VIFF so we
    2.10  # skip them instead of letting them fail if the packages are not available. 
    2.11 @@ -524,7 +525,35 @@
    2.12          d = runtime.open_two_values(x, y)
    2.13          d.addCallback(check)
    2.14          return d
    2.15 -    
    2.16 +
    2.17 +
    2.18 +# TODO: Move to test.bedoza.test_zero_knowledge.
    2.19 +class BeDOZaZeroKnowledgeTest(RuntimeTestCase):
    2.20 +
    2.21 +    num_players = 3
    2.22 +
    2.23 +    timeout = 3
    2.24 +
    2.25 +    runtime_class = BeDOZaRuntime
    2.26 +
    2.27 +    def test_zk_matrix_entries_are_correct(self):
    2.28 +        zk = ZKProof(None, None)
    2.29 +        zk._set_e([1, 0, 0, 1, 1])
    2.30 +        for i in range(zk.s):
    2.31 +            for j in range(zk.m):
    2.32 +                if j >= i and j < i + zk.s:
    2.33 +                    self.assertEquals(zk.e[j - i], zk._E(j, i))
    2.34 +                else:
    2.35 +                    self.assertEquals(0, zk._E(j, i))
    2.36 +
    2.37 +    def test_vec_pow_is_correct(self):
    2.38 +        Zn = GF(17)
    2.39 +        y = [Zn(i) for i in range(1, 6)]
    2.40 +        zk = ZKProof(None, Zn)
    2.41 +        zk._set_e([1, 0, 1, 1, 0])
    2.42 +        y_pow_E = zk.vec_pow_E(y)
    2.43 +        self.assertEquals([Zn(v) for v in [1, 2, 3, 8, 13, 12, 3, 5, 1]],
    2.44 +                          y_pow_E)
    2.45  def skip_tests(module_name):
    2.46      BeDOZaBasicCommandsTest.skip = "Skipped due to missing " + module_name + " module."
    2.47