In the paper Fully Homomorphic Encryption over the Integers, a method is shown for doing homomorphic encryption using only integers. The basic idea is that a bit m is encoded as a large integer c.

The principle behind homomorphic encryption through bootstrapping is that after some calculations, the cyphertext is recrypted by encrypting it under a new key and then performing the decryption on the first key homomorphically. This is explained in section 1.2 of Fully Homomorphic Encryption Using Ideal Lattices.

My question: since the scheme in the first paper encrypts a bit as an integer, how is this integer encrypted under the new key? Is each bit of c encrypted using the new key?

  • 2
    $\begingroup$ Yes, that is one way to do it. Note, however, that the view of bootstrapping you reference has been refined, so that the bits of the ciphertext do not need to be encrypted at all. Instead, we think of "hard coding" the ciphertext into the decryption function, and homomorphically evaluate the induced function on the encrypted secret key. $\endgroup$ – Chris Peikert Nov 6 '15 at 18:18
  • $\begingroup$ Ooh. That's very interesting. @ChrisPeikert, would you be able to provide a link that explains in more detail the process of "hard coding" the ciphertext into the decryption function? $\endgroup$ – danxinnoble Nov 6 '15 at 18:53
  • $\begingroup$ Have a look at the first few slides here: web.eecs.umich.edu/~cpeikert/pubs/slides-heat1.pdf (Our work didn't invent the "hard coding" idea; the slides just explain how it works.) $\endgroup$ – Chris Peikert Nov 6 '15 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.