viff

changeset 1047:30e34b801d65

Square-and-multiply exponentiation with known exponent.
author Marcel Keller <mkeller@cs.au.dk>
date Wed, 10 Dec 2008 20:22:20 +0100
parents b283e3136f61
children 73844d576756
files viff/passive.py viff/runtime.py viff/test/test_runtime.py
diffstat 3 files changed, 38 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/viff/passive.py	Wed Dec 10 12:43:05 2008 +0100
     1.2 +++ b/viff/passive.py	Wed Dec 10 20:22:20 2008 +0100
     1.3 @@ -179,6 +179,20 @@
     1.4          self.schedule_callback(result, share_recombine)
     1.5          return result
     1.6  
     1.7 +    def pow(self, share, exponent):
     1.8 +        """Exponentation of a share to an integer by square-and-multiply."""
     1.9 +
    1.10 +        assert isinstance(exponent, int), "Exponent must be an integer"
    1.11 +        assert exponent >= 0, "Exponent must be non-negative"
    1.12 +
    1.13 +        if exponent == 0:
    1.14 +            return 1
    1.15 +        elif exponent % 2 == 0:
    1.16 +            tmp = share ** (exponent / 2)
    1.17 +            return tmp * tmp
    1.18 +        else:
    1.19 +            return share * (share ** (exponent-1))
    1.20 +    
    1.21      @increment_pc
    1.22      def xor(self, share_a, share_b):
    1.23          field = getattr(share_a, "field", getattr(share_b, "field", None))
     2.1 --- a/viff/runtime.py	Wed Dec 10 12:43:05 2008 +0100
     2.2 +++ b/viff/runtime.py	Wed Dec 10 20:22:20 2008 +0100
     2.3 @@ -102,6 +102,10 @@
     2.4          """Multiplication (reflected argument version)."""
     2.5          return self.runtime.mul(other, self)
     2.6  
     2.7 +    def __pow__(self, exponent):
     2.8 +        """Exponentation to open integer exponents."""
     2.9 +        return self.runtime.pow(self, exponent)
    2.10 +
    2.11      def __xor__(self, other):
    2.12          """Exclusive-or."""
    2.13          return self.runtime.xor(self, other)
     3.1 --- a/viff/test/test_runtime.py	Wed Dec 10 12:43:05 2008 +0100
     3.2 +++ b/viff/test/test_runtime.py	Wed Dec 10 20:22:20 2008 +0100
     3.3 @@ -50,6 +50,26 @@
     3.4      operator = operator.mul
     3.5  
     3.6  
     3.7 +class PowTest(RuntimeTestCase):
     3.8 +    """Tests power to known integer"""
     3.9 +
    3.10 +    a = 1337
    3.11 +    b = 123
    3.12 +    
    3.13 +    def _verify(self, runtime, result, expected):
    3.14 +        self.assert_type(result, Share)
    3.15 +        opened = runtime.open(result)
    3.16 +        opened.addCallback(self.assertEquals, expected)
    3.17 +        return opened
    3.18 +
    3.19 +    @protocol
    3.20 +    def test_pow(self, runtime):
    3.21 +        share_a = Share(runtime, self.Zp, self.Zp(self.a))
    3.22 +        return self._verify(runtime,
    3.23 +                            share_a ** self.b,
    3.24 +                            pow(self.a, self.b, self.Zp.modulus))
    3.25 +
    3.26 +
    3.27  class XorTest(BinaryOperatorTestCase, RuntimeTestCase):
    3.28      a = 0
    3.29      b = 1