Abstract
This lecture began with a review of encryption algorithms and how to specify and demonstrate their security. We then introduced the notion of semi-homomorphic ciphers: ciphers that are homomorphic for addition or multiplication of plaintext, but not for both operations. We showed four examples: RSA, ElGamal, exponential ElGamal and Paillier ciphers. But the ultimate goal is to obtain a cipher that is homomorphic for addition and multiplication, which would enable arbitrary Boolean circuits to be evaluated homomorphically, via polynomial encoding of logic gates.
As a first step in this direction, we introduced the notion of weakly homomorphic encryption, i.e. homomorphic for a limited number of additions and multiplications. We presented the construction, due to van Dijk, Gentry, Halevy and Vaikuntanathan (2010), of such a cipher using integers only. This cipher can be made fully homomorphic by combining it with the bootstrap procedure introduced by Gentry in 2009. This procedure relies on the homomorphic evaluation of a circuit that performs the decryption. It removes the limit on the number of successive additions and multiplications, and therefore allows arbitrary circuits to be evaluated, provided the decryption circuit is simple enough to be evaluated by a weakly homomorphic cipher, which is difficult to achieve.
