viff

changeset 1247:cd0f4d7d135b

Added new AES inversion variant: masked exponentiation.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 17 Sep 2009 17:30:48 +0200
parents be9c8eb7b4d0
children 5ffc93111d70
files apps/aes.py viff/aes.py viff/passive.py
diffstat 3 files changed, 64 insertions(+), 6 deletions(-) [+]
line diff
     1.1 --- a/apps/aes.py	Fri Sep 11 19:11:31 2009 +0200
     1.2 +++ b/apps/aes.py	Thu Sep 17 17:30:48 2009 +0200
     1.3 @@ -120,9 +120,10 @@
     1.4      rt.schedule_complex_callback(s, encrypt, rt, key)
     1.5  
     1.6  def preprocess(rt):
     1.7 +    start = time.time()
     1.8 +    program_desc = {}
     1.9 +
    1.10      if options.active:
    1.11 -        start = time.time()
    1.12 -
    1.13          if options.exponentiation is False:
    1.14              max = 301
    1.15              js = [3 + i * 15 + j for i in range(20) for j in range(7) + [8]]
    1.16 @@ -140,13 +141,21 @@
    1.17                 for k in range(1, options.count + 1)
    1.18                 for i in range(10)
    1.19                 for j in js]
    1.20 +        program_desc[("generate_triples", (GF256,))] = pcs
    1.21  
    1.22 -        preproc = rt.preprocess({("generate_triples", (GF256,)): pcs})
    1.23 +    if options.exponentiation == 4:
    1.24 +        pcs = [(2, 18, k) + (81,) * i + (1 + j * 4, 0)
    1.25 +               for k in range(1, options.count + 1)
    1.26 +               for i in range(10)
    1.27 +               for j in range(20)]
    1.28  
    1.29 +        program_desc[("prss_powerchains", ())] = pcs
    1.30 +
    1.31 +    if program_desc:
    1.32 +        preproc = rt.preprocess(program_desc)
    1.33          def fin(_):
    1.34              print "Finished preprocessing after %f sec." % (time.time() - start)
    1.35              return rt
    1.36 -
    1.37          preproc.addCallback(fin)
    1.38          rt.schedule_complex_callback(preproc, share_key)
    1.39  
     2.1 --- a/viff/aes.py	Fri Sep 11 19:11:31 2009 +0200
     2.2 +++ b/viff/aes.py	Thu Sep 17 17:30:48 2009 +0200
     2.3 @@ -109,6 +109,8 @@
     2.4                  self.invert = self.invert_by_exponentiation_with_less_rounds
     2.5              elif (use_exponentiation == "chain_with_least_rounds"):
     2.6                  self.invert = self.invert_by_exponentiation_with_least_rounds
     2.7 +            elif (use_exponentiation == "masked"):
     2.8 +                self.invert = self.invert_by_masked_exponentiation
     2.9              else:
    2.10                  self.invert = self.invert_by_exponentiation
    2.11          else:
    2.12 @@ -120,7 +122,8 @@
    2.13      exponentiation_variants = ["standard_square_and_multiply",
    2.14                                 "shortest_sequential_chain",
    2.15                                 "shortest_chain_with_least_rounds",
    2.16 -                               "chain_with_least_rounds"]
    2.17 +                               "chain_with_least_rounds",
    2.18 +                               "masked"]
    2.19  
    2.20      def invert_by_masking(self, byte):
    2.21          bits = bit_decompose(byte)
    2.22 @@ -156,6 +159,25 @@
    2.23          result.addCallback(lambda (c, r, b): c * r - b)
    2.24          return result
    2.25  
    2.26 +    def invert_by_masked_exponentiation(self, byte):
    2.27 +        def add_and_multiply(masked_powers, random_powers):
    2.28 +            byte_powers = map(operator.add, masked_powers, random_powers)[1:]
    2.29 +            while len(byte_powers) > 1:
    2.30 +                byte_powers.append(byte_powers.pop(0) * byte_powers.pop(0))
    2.31 +            return byte_powers[0]
    2.32 +
    2.33 +        def open_and_exponentiate(random_powers):
    2.34 +            masked_byte = self.runtime.open(byte + random_powers[0])
    2.35 +            masked_powers = self.runtime.schedule_complex_callback(masked_byte,
    2.36 +                lambda masked_byte: self.runtime.powerchain(masked_byte, 7))
    2.37 +            return self.runtime.schedule_complex_callback(
    2.38 +                masked_powers, add_and_multiply, random_powers)
    2.39 +
    2.40 +        result = Share(self.runtime, GF256)
    2.41 +        self.runtime.prss_powerchain().chainDeferred(result)
    2.42 +        result = self.runtime.schedule_complex_callback(result, open_and_exponentiate)
    2.43 +        return result
    2.44 +
    2.45      def invert_by_exponentiation(self, byte):
    2.46          byte_2 = byte * byte
    2.47          byte_3 = byte_2 * byte
     3.1 --- a/viff/passive.py	Fri Sep 11 19:11:31 2009 +0200
     3.2 +++ b/viff/passive.py	Thu Sep 17 17:30:48 2009 +0200
     3.3 @@ -22,11 +22,14 @@
     3.4  import operator
     3.5  
     3.6  from viff import shamir
     3.7 -from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
     3.8 +from viff.runtime import Runtime, increment_pc, Share, ShareList, \
     3.9 +     gather_shares, preprocess
    3.10  from viff.prss import prss, prss_lsb, prss_zero, prss_multi
    3.11  from viff.field import GF256, FieldElement
    3.12  from viff.util import rand, profile
    3.13  
    3.14 +from twisted.internet.defer import succeed
    3.15 +
    3.16  
    3.17  class PassiveRuntime(Runtime):
    3.18      """The VIFF runtime.
    3.19 @@ -448,6 +451,30 @@
    3.20          # Use r_lsb to flip b as needed.
    3.21          return (b_p, b ^ r_lsb)
    3.22  
    3.23 +    def powerchain(self, share, max):
    3.24 +        """Returns the list [*share*, *share*^2, *share*^4, ...,
    3.25 +        *share*^(i^max)]."""
    3.26 +        result = [share]
    3.27 +        for i in range(max):
    3.28 +            share = share * share
    3.29 +            result.append(share)
    3.30 +        return result
    3.31 +
    3.32 +    @increment_pc
    3.33 +    @preprocess("prss_powerchains")
    3.34 +    def prss_powerchain(self, max=7):
    3.35 +        """Generate a random secret share in GF256 and returns
    3.36 +        [*share*, *share*^2, *share*^4, ..., *share*^(i^max)]."""
    3.37 +        share = self.prss_share_random(GF256)
    3.38 +        return succeed(self.powerchain(share, max))
    3.39 +
    3.40 +    def prss_powerchains(self, max=7, quantity=20):
    3.41 +        """Does *quantity* times the same as :meth:`prss_powerchain`.
    3.42 +        Used for preprocessing."""
    3.43 +        shares = self.prss_share_random_multi(GF256, quantity)
    3.44 +        return quantity, succeed([self.powerchain(share, max)
    3.45 +                                  for share in shares])
    3.46 +
    3.47      def input(self, inputters, field, number=None, threshold=None):
    3.48          """Input *number* to the computation.
    3.49