Cryptanalysis of “Fully Homomorphic Encryption over the Binary Polynomials”

Turns out, I’m not he only one who was inspired to adapt the Fully Homomorphic Encryption over the Integers scheme by van Dijk, Gentry, Halevi and Vaikuntanathan to polynomials.  Gu Chunsheng posted a pre-print on the IACR eprint server this week which essentially instantiates the integer scheme over univariate polynomials over \mathbb{F}_2.  Below is my implementation (in Sage) of his somewhat homomorphic scheme:

class BinPolySHE:
    def __init__(self, n):
        n = n
        tau = n # choice here
        P = PolynomialRing(GF(2),'x')

        x = P.gen()

        s = P.random_element(degree=2*n+1)
        while not (s.is_irreducible() and s.degree()==2*n+1):
            s = P.random_element(degree=2*n+1)

        b = []

        a0 = P.random_element(2*n+1)
        if a0.degree() < 2*n+1:
            a0 += x**(2*n+1)
        e0 = P.random_element(degree=n-1)
        b0 = a0*s + x*e0 # deg: 4*n+2

        b.append(b0)

        for i in range(1,tau):
            ai = P.random_element(degree=n) # choice here
            ei = P.random_element(degree=n-1)
            bi = ai*s + x*ei # deg 3*n+1
            bi = bi % b0
            b.append(bi)

        self.n = n
        self.pk = b
        self.sk = s
        self.P = P

    def encrypt(self, m):
        T = []

        for i in range(1, len(self.pk)):
            if random() <= 0.5: # choice here
                T.append(i)

        c = self.P(m%2)

        x = self.P.gen()

        for i in T:
            e = self.P.random_element(degree=self.n-1)
            c += self.pk[i] + x*e

        return c % self.pk[0]

    def decrypt(self, c):
        x = self.P.gen()
        return (c % self.sk) % x

Regular readers of this blog might have noticed that the scheme looks like a bit like a univariate specialisation of this PollyCracker scheme. Indeed, just like this first PollyCracker scheme, Gu’s scheme is badly broken. Below, the source code of my attack:

    def attack(self, c):

        A = Matrix(GF(2),len(self.pk),4*self.n+2)

        x = self.P.gen()

        for i,b in enumerate(self.pk):
            for j in b.exponents():
                A[i,A.ncols()-j-1] = 1
        E = A.echelon_form(reduced=False)

        pk2 = []
        for i,r in enumerate(A.rows()):
            b = 0
            for j in range(A.ncols()):
                b += E[i,A.ncols()-j-1]*x**j
            pk2.append(b)

        for b in pk2:
            if c[b.degree()]:
                c -= b
        return c % x

The attack proceeds pretty much as discussed here: we can compute a triangular basis for the span of the public key and use that to perform all eliminations. Since the noise does not grow with each addition and does not affect the constant coefficient (which holds the message), we can essentially ignore it.

Advertisements

8 thoughts on “Cryptanalysis of “Fully Homomorphic Encryption over the Binary Polynomials””

  1. Hello:
    I’m just a student.I got a problem that when I do encrypt(self,5),how can I get 5 back from decrypt(self,encrypt(self,5)).doesn’t it just return 0 or 1?
    Sorry it is easy but I just couldn’t understand.Please help me.Thanks.

    1. The scheme is only specified for messages in (0,1), i.e. bits. You have two options:

      1) either extend the scheme — which is broken anyway — to other small finite fields (e.g. GF(7) instead of GF(2))
      2) or encode your message as a bitstring, e.g. 5 = [1 0 1] in bit representation. Then, encode each bit individually.

  2. Another problem:suppose I want get the result of 2*3+2 from Dec(Enc(2)*Enc(3)+Enc(2)).Does it mean I must get Dec(Enc(0)*Enc(1)+Enc(0))=0 on low and Dec(Enc(1)*Enc(1)+Enc(0)*Enc(1)+Enc(1))=0 and Dec(Enc(1)*Enc(1))+1=0 .The highest get the carrybit 1.That finally get 1000=8.It seems a little complex when we do large-number calculation using bit caculation.Would you mind give me some suggestion to make it simple?

  3. Nope, you got it. The scheme is specified for bits and hence you have to do everything on a bit level. Of course, one can extend the message space to other moduli at the cost of extending the base field.

    1. Sorry, I mean that he express data operation by boolean circuit in Gentry’s paper. I want to know the advantage of using boolean circuit.

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