Somewhat Homomorphic Encryption

Today I read the paper “Computing Arbitrary Functions of Encrypted Data” by Craig Gentry in which he explains the basic ideas behind his work on fully homomorphic encryption. If you don’t know what homomorphic encryption is: it means that one can evaluate a function on ciphertexts which has the same result as evaluating that function on the plaintexts. Thus, one can compute with data without getting to see it. The canonical example Gentry uses in his papers is a search engine that searches through sensitive data without seeing the actual content. It is similar to secure multi-party computation except that it is not interactive at all, i.e. you send your query and get the result back without any interaction in between. In the above mentioned paper Gentry gives a simplified version of a recent integer based fully homomorphic scheme. This simplified version is symmetric and only somewhat homomorphic (more on this below). Since the basic idea of the scheme is so simple, it is quickly implemented. The code below is actually some slight generalisation such that b isn’t always forced to be two.

class IntegerHomomorphic:
    def __init__(self, l, b=2):
        self.b = b
        self.l = l  # lambda is out security parameter
                    # these parameters determine the size
                    # of various numbers and are chosen such that
                    # the approximate GCD is assumed to be hard.
        self.N = 2**(l)
        self.P = 2**(l**2)
        self.Q = 2**(l**5)
        self.key_gen()

    def key_gen(self):
        # the secret key is simply an odd number of P bits.
        p = ZZ.random_element(0, self.P-1)
        if p%self.b == 0:
            p += ZZ.random_element(1, self.b)
        self.p = p

    def encrypt(self, m):
        # we want to encrypt 0 <= m < b, thus we pick some m'
        # for which m' % b == m % b holds to avoid having
        # known bits (== 0) in the computation below.
        mprime = ZZ.random_element(0,self.N-1)
        mprime = mprime - mprime%self.b + m%self.b
        # the ciphertext is this m' with some multiple of p
        # added to mask it.
        q = ZZ.random_element(0,self.Q-1)
        return mprime + self.p*q

    def decrypt(self, c):
        # if we now p decryption is easy since we can simply
        # mod out p and then recover the value mod b
        return ZZ((c % self.p) % self.b)

To see that this scheme is somewhat homomorphic observe that as long as the noise is small enough such that things don’t wrap around we have and for some number .

Here is a toy example:

sage: IH = IntegerHomomorphic(3,)
sage: IH.encrypt(0)
1269419566719153208598601566220616500605965999\
730518673686683244436179224382
sage: IH.encrypt(0) + IH.encrypt(1)
61002356472659294938919367702545237501719846898\
35782651710838758570047089506
sage: IH.decrypt(IH.encrypt(0) + IH.encrypt(1))
1
sage: IH.decrypt(IH.encrypt(0) + IH.encrypt(1)*IH.encrypt(1))
1

However, there is only a limited number of operations we can perform before we overflow, hence the “somewhat homomorphic” in the title:

sage: IH.decrypt(prod(IH.encrypt(1) for _ in range(1000)))
0
sage: IH.decrypt(prod(IH.encrypt(1) for _ in range(1000)))
1

The security of this construction can be reduced (according to the paper, I didn’t check it) to the approximate GCD problem, that is: given and , compute or in and . The problem hasn’t received much attention so far. Currently it is assumed to be hard if and have bits, has bits and has bits.

Thus, the size of the scheme is both bounded by the gap between and which dictates how much computations one can fit before wrapping around and the sizes required for the approximate GCD to be hard. Of course, if you spent more than three years starring at multivariate polynomial ideals you will have noticed by now that this whole scheme can be instantiated using multivariate polynomial ideals as well:

class PolynomialHomomorphic:
    def __init__(self, l, b=2):
        self.l = l
        K = GF(127)  # pick some field
        # we choose a ring with l unknowns, which
        # should make any GB computation at least
        # as hard as 2\^l if we pick the ideal sufficiently
        # random.
        R = PolynomialRing(K, l, 'x', order='degrevlex')
        self.K = K
        self.R = R
        # our small ideal, defines the message space.
        self.b = Ideal([x for x in R.gens()])

    # these parameters are pretty arbitrary from a
    # security perspective!
        self.N = 1
        self.P = 2
        self.Q = 5
        self.key_gen()

    def key_gen(self):
        b, l = self.b, self.l
        K, R = self.K, self.R
        # we pick a random ideal with l element of degree P
        p = [R.random_element(degree=self.P) for _ in range(l)]
        self.p = Ideal(p)

    def encrypt(self, m):
        # we pick some m' which encodes the
        # same plaintext but is bigger
        m = self.R(m)
        mprime = self.R.random_element(degree=self.N)
        mprime -= mprime - mprime.reduce(self.b)
        mprime += m.reduce(self.b)

        # adding a random ideal element
        for f in self.p.gens():
            mprime += self.R.random_element(degree=self.Q)*f
        return mprime

        def decrypt(self, c):
            # decryption is just as in the integer case.
            return c.reduce(self.p).reduce(self.b)

This scheme looks a bit similar to PolyCracker where the security was also related to normal form computations. PolyCracker was broken because normal forms are simpler than Gröbner bases, that is you don’t necessarily need a Gröbner basis to compute them. However, in this scheme you must find the ideal first, before you can start thinking about whether you need a Gröbner basis of it or not. Of course, I assume that my adaptation above can still be broken somehow since that’s what tends to happen with multivariate crypto schemes. Also, I’m really really not an expert on public-key cryptography. Hey, this is a blog post, not a research paper … so break it in the comments 🙂

Anyway, here’s a toy example:

sage: PH = PolynomialHomomorphic(2)
sage: f = PH.encrypt(3) * PH.encrypt(2) * PH.encrypt(1) + PH.encrypt(2)
sage: PH.decrypt(f)
8

Of course, this is just the first step. The really cool stuff happens after this simple step. Gentry constructs a fully homomorphic scheme from such a somewhat homomorphic scheme … if you want to know how, go read the paper 🙂

Update: See this post for a break of this scheme and corrected Sage code.

Advertisements

14 thoughts on “Somewhat Homomorphic Encryption”

  1. Here is a recent paper on an implementation of the original scheme (using ideal lattices):

    https://researcher.ibm.com/researcher/files/us-shaih/fhe-implementation.pdf

    For the polynomial ring generalisation: what would be the appropriate parameters to make it secure (if any)? Would it be more efficient that the original version?

    By the way, for the bootstrapable version addition and multiplication are a bit more involved and Eval will need their its own subroutine.

  2. About the polynomial generalisation: I haven’t looked into parameter sizes. I guess one motivation could be to maybe reduce the security to a more well know problem than “approximate gcd”.

  3. To be precise homomorphic encryption mans that You know function f1 which applied to cipher-text gives You results which is the same as You apply known function f2 on data. F1 may be completely different than f2, crucial is that by apply You mean computing in cipher-text space without decrypting data. It is far more general than case where f1=f2, for example when You add cipher-text to add data. Yo may imagine that You have to multiply encrypted data to obtain sum of decrypted data for example. Please note Goldwasser-Micali, or Benaloh or Paillier in wikipedia article: http://en.wikipedia.org/wiki/Homomorphic_encryption

  4. Carlo Traverso mentioned in his talk at SCC 2010 that his scheme — which is a Polly Cracker variant using binomial ideals IIRC — is homomorphic. I think it isn’t fully homomorphic though since the ciphertext grows with the number of gates, which is a feature a fully homomorphic scheme is not supposed to have. The trouble with Polly Cracker style schemes seems to be to turn a secure symmetric scheme into a secure asymmetric scheme.

  5. I assume that it is quite easy to construct a symmetric Polly Cracker scheme which is homomorphic. However, turning this into a secure public-key scheme is not so easy despite the fact that there are several proposals around how to turn a secure symmetric homomorphic scheme into a secure public-key homomorphic scheme, cf. “Why You Cannot Even Hope to Use Gröbner Bases in Public-Key Cryptography?”

  6. It is interesting indeed. Moreover the question of algebraically homomorphic scheme (i.e. supporting both multiplication and addition) is of importance and there is no good proposal up to now. I’m wondering if Polly-like scheme would suit here (let it even be symmetric first).

  7. I tried running your code for PolynomialHomomorphic and the given example, but i didn’t get the answer “8” as expected. Is there anything missing?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s